Determinismus (Algorithmus)


Determinismus (Algorithmus)

Ein deterministischer Algorithmus oder auch determinierter 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. Das bedeutet auch, dass alle Zwischenergebnisse innerhalb des Algorithmus immer gleich sind. 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 nichtdeterministisch, aber trotzdem determiniert sind.

Im Umkehrschluss 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.

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 Gottesbegriff.

Siehe auch

Referenzen


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Determinismus (Begriffsklärung) — Determinismus steht für: eine philosophische Denkrichtung, siehe Determinismus speziell in der Technik, siehe Technikdeterminismus einen Begriff in der Theoretischen Informatik, siehe Determinismus (Algorithmus). einen Begriff aus der Linguistik …   Deutsch Wikipedia

  • Algorithmus — Al Chwarizmi, der Namensgeber des Algorithmus, auf einer sowjetischen Briefmarke anlässlich seines 1200 jährigen Geburtsjubiläums. Ein Algorithmus ist eine aus endlich vielen Schritten bestehende eindeutige Handlungsvorschrift zur Lösung eines… …   Deutsch Wikipedia

  • Determinismus — Vorherbestimmung; Vorbestimmung * * * De|ter|mi|nịs|mus 〈m.; ; unz.; Philos.〉 Lehre, dass der menschl. Wille von äußeren Ursachen bestimmt u. daher nicht frei sei; Ggs Indeterminismus [zu lat. determinare „begrenzen, bestimmen“] * * *… …   Universal-Lexikon

  • Algorithmus — (genau definierte) Handlungsvorschrift; Rechenvorschrift * * * Al|go|rịth|mus 〈m.; , men; Math.; EDV〉 ein Verfahren, bei dem aufgrund eines Systems von Regeln gegebene Größen (Eingabeinformationen, Aufgaben) in andere Größen… …   Universal-Lexikon

  • Determinismus — De|ter|mi|nis|mus der; <zu ↑...ismus>: 1. Lehre von der kausalen [Vor]bestimmtheit alles Geschehens. 2. die der Willensfreiheit widersprechende Lehre von der Bestimmung des Willens durch innere od. äußere Ursachen (Ethik); Ggs.… …   Das große Fremdwörterbuch

  • Terminierender Algorithmus — Terminiertheit (auch: Terminierung, Termination) ist ein Begriff aus der Berechenbarkeitstheorie, einem Teilgebiet der theoretischen Informatik. Man sagt, ein Algorithmus terminiert (hält) für die Eingabe a, wenn er für die Eingabe a nach endlich …   Deutsch Wikipedia

  • Determinierter 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 Voraussetzungen immer die gleiche… …   Deutsch Wikipedia

  • Deterministischer 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 Voraussetzungen immer die gleiche… …   Deutsch Wikipedia

  • Nicht-deterministischer 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 Voraussetzungen immer die gleiche… …   Deutsch Wikipedia

  • stochastischer Algorithmus —   [griech. stochasis »Vermutung«] (probabilistischer Algorithmus), Algorithmus, der mit Zufallszahlen arbeitet. Sowohl die Reihenfolge der Abarbeitung der einzelnen Anweisungen als auch die Bereitstellung von Zahlenwerten können dem Zufall… …   Universal-Lexikon