Determinismus (Algorithmus)

Definition und Bedeutung

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Bei gleicher Eingabe liefert er immer die gleiche Ausgabe, durchläuft dieselbe Folge von Zuständen und erzeugt dieselben Zwischenergebnisse. Zu jedem Zeitpunkt ist der nächste Verarbeitungsschritt eindeutig festgelegt.

Vereinfacht gesagt folgt unter exakt gleichen Voraussetzungen auf eine Anweisung immer dieselbe nächste Anweisung. Mit „gleichen Voraussetzungen“ sind dabei identische Daten und Zwischenergebnisse in jedem diskreten Verarbeitungsschritt gemeint.

Determinismus und Determiniertheit

Determinismus und Determiniertheit sind nicht dasselbe. Ein deterministischer Algorithmus ist immer determiniert: Gleiche Eingabe bedeutet gleiches Endergebnis. Umgekehrt kann ein Algorithmus nichtdeterministisch, aber dennoch determiniert sein.

Quicksort ist ein Beispiel: Eine vorgegebene Liste wird in Teillisten aufgeteilt, deren Größe zufällig gewählt werden kann. Deshalb können sich Zwischenergebnisse unterscheiden und der Ablauf ist nichtdeterministisch. Das sortierte Endergebnis bleibt jedoch stets gleich; Quicksort ist daher determiniert.

Nichtdeterministische Algorithmen

Bei einem nichtdeterministischen, randomisierten Algorithmus können nicht reproduzierbare und undefinierte Zustände auftreten. Ein theoretischer Algorithmus, der eine Zufallszahl liefert, verhält sich beispielsweise nichtdeterministisch.

Nichtdeterministische Turingmaschinen sind in der Theoretischen Informatik wichtig. Sie ermöglichen einem Algorithmus gewissermaßen zu „raten“, sodass viele Probleme mit deutlich weniger Aufwand lösbar werden. In der Komplexitätstheorie bilden solche Turingmaschinen eine eigene Komplexitätsklasse.

Weitere Eigenschaften von Algorithmen

Neben Determinismus beziehungsweise Determiniertheit werden Algorithmen auch durch weitere Eigenschaften beschrieben:

• Endlichkeit: Statisch besitzt der Algorithmus eine endliche Beschreibung; dynamisch benötigt seine Ausführung nur endlich viele Ressourcen.
• Komplexität: Aufwand an Rechenzeit und Speicherplatz; sie kann hoch oder niedrig sein.
• Terminiertheit: Der Algorithmus liefert nach endlich vielen Schritten ein Ergebnis oder terminiert nicht.
• Determiniertheit: Bei gleicher Eingabe entsteht dasselbe Ergebnis; ein Algorithmus kann determiniert oder nicht determiniert sein.

Der philosophische Determinismus behandelt dagegen Determinismus als Eigenschaft der Welt insgesamt. Ob physikalische Abläufe deterministisch sind, beeinflusst unter anderem das Verständnis von freiem Willen und des Gottesbegriffs.