Determinismus (Algorithmus)
aus Wikipedia, der freien Enzyklopädie
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 Voraussetzungen 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 die nichtdeterministisch sind, aber determiniert.
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
- Finitheit (statisch: endliche Beschreibung, dynamisch: endlich viele Ressourcen bei der Ausführung)
- Komplexität (Aufwand an Rechenzeit und Speicherplatz, hoch oder niedrig)
- Terminierung (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 Gottesbegriff.
Siehe auch: Probabilistischer Algorithmus, Stochastischer Algorithmus, randomisierter Algorithmus, Nichtdeterminismus, Kausalität
[Bearbeiten] Referenzen
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium. 2002. ISBN 3-8273-7020-5.
