Determinismus (Algorithmus) - LinkFang.de





Determinismus (Algorithmus)


Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Die fraglichen Angaben werden daher möglicherweise demnächst entfernt. Bitte hilf der Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst. Näheres ist eventuell in der Versionsgeschichte angegeben. Bitte entferne zuletzt diese Warnmarkierung.

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Für die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen. Zu jedem Zeitpunkt ist der nachfolgende Abarbeitungsschritt des Algorithmus eindeutig festgelegt. Das bedeutet auch, dass alle Zwischenergebnisse innerhalb des Algorithmus immer gleich sind.

Umgangssprachlich könnte man sagen: „Auf eine Anweisung im Algorithmus folgt unter den gleichen Voraussetzungen immer die gleiche Anweisung.“ Bei dieser Formulierung ist jedoch zu beachten, dass unter „gleichen Voraussetzungen“ exakt gleiche Zwischenergebnisse und Daten in jedem diskreten Verarbeitungsschritt gemeint ist.

Der Begriff Determinismus ist vom Begriff Determiniertheit zu unterscheiden: Ein deterministischer Algorithmus ist immer determiniert, d. h., er liefert bei gleicher Eingabe immer die gleiche Ausgabe. Die Umkehrung aber gilt nicht: So gibt es Algorithmen, die nicht-deterministisch, aber trotzdem determiniert sind (d. h. das gleiche Ergebnis liefern).

Im Umkehrschluss können bei einem nichtdeterministischen, randomisierten Algorithmus nicht reproduzierbare und undefinierte Zustände auftreten. Zum Beispiel hat ein Algorithmus, der eine (theoretische) Zufallszahl liefert, ein nichtdeterministisches Verhalten.

Nichtdeterministische Turingmaschinen spielen in der Theoretischen Informatik eine große Rolle: Sie ermöglichen es einem Algorithmus quasi zu „raten“. Damit werden viele Probleme mit sehr viel weniger Aufwand lösbar. Solche Turingmaschinen definieren in der Komplexitätstheorie eine eigene Komplexitätsklasse.

Weitere Eigenschaften eines Algorithmus sind

  • Endlichkeit (statisch: endliche Beschreibung, dynamisch: endlich viele Ressourcen bei der Ausführung)
  • Komplexität (Aufwand an Rechenzeit und Speicherplatz, hoch oder niedrig)
  • Terminiertheit (Ergebnis nach endlich vielen Schritten. Ausprägung: terminierend/nicht terminierend)
  • Determiniertheit (Bei gleicher Eingabe gleiches Ergebnis, Ausprägung: determiniert, nicht determiniert)

Determinismus als Eigenschaft der Welt als ganzes behandelt der philosophische Determinismus. Die Frage, ob die physikalischen Abläufe in der Welt deterministisch sind, hat weitreichende Konsequenzen unter anderem für das Verständnis von freiem Willen und den Gottes­begriff.

Siehe auch

Referenzen


Kategorien: Algorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Determinismus (Algorithmus) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.