Determinismus (Algorithmus)

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Anders gesprochen heißt das, auf eine Anweisung im Algorithmus folgt unter den gleichen Voraussetzung immer die gleiche Anweisung. Zu jedem Zeitpunkt ist der nachfolgende Abarbeitungsschritt des Algorithmus eindeutig festgelegt. Der Begriff Determinismus ist vom Begriff Determiniertheit (Algorithmus) zu unterscheiden.

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

Ein deterministischer Algorithmus ist folglich auch immer determiniert, d. h. er liefert bei gleicher Eingabe immer die gleiche Ausgabe. Die Umkehrung aber gilt nicht: So gibt es Algorithmen die nichtdeterministisch sind, aber determiniert.

Nichtdeterministische Automaten spielen in der Theoretischen Informatik eine grosse Rolle: sie ermöglichen es einem Algorithmus quasi zu "raten". Damit werden viele Probleme mit sehr viel weniger Aufwand lösbar. So definieren solche Automaten in der Komplexitätstheorie eigene Komplexitätsklassen. Jedoch ist in einigen wichtigen Fällen noch ungeklärt, ob die nichtdeterministischen Automaten tatsächlich mächtiger sind als ihr deterministisches Äquivalent, so zum Beispiel bei den beiden wichtigen Klassen P und NP (siehe P/NP-Problem).

Weitere Eigenschaften eines Algorithmus sind

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

Siehe auch: Probabilistischer Algorithmus, Stochastischer Algorithmus, randomisierter Algorithmus, Nichtdeterminismus