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 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, etwa Quicksort, die nichtdeterministisch sind, aber determiniert.
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)