Nicht-deterministischer Algorithmus

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

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

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

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

  • 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

  • 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

  • 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… …   Deutsch Wikipedia

  • Probabilistischer Algorithmus — Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) verwendet im Gegensatz zu einem deterministischen Algorithmus Zufallsbits um seinen Ablauf zu steuern. Es wird nicht verlangt, dass ein randomisierter… …   Deutsch Wikipedia

  • Stochastischer Algorithmus — Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) verwendet im Gegensatz zu einem deterministischen Algorithmus Zufallsbits um seinen Ablauf zu steuern. Es wird nicht verlangt, dass ein randomisierter… …   Deutsch Wikipedia

  • Polynomialzeit-Algorithmus — In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die benötigte Rechenzeit einer deterministischen, sequentiellen Rechenmaschine mit der Problemgröße nicht stärker als mit einer Polynomfunktion wächst. Die… …   Deutsch Wikipedia

  • Polynomieller Algorithmus — In der Komplexitätstheorie bezeichnet man ein Problem als in Polynomialzeit lösbar, wenn die benötigte Rechenzeit einer deterministischen, sequentiellen Rechenmaschine mit der Problemgröße nicht stärker als mit einer Polynomfunktion wächst. Die… …   Deutsch Wikipedia

  • Genetischer Algorithmus — Genetische Algorithmen (GA) sind Algorithmen, die auch nicht analytisch lösbare Probleme behandeln können, indem sie wiederholt verschiedene „Lösungsvorschläge“ generieren, dabei verändern sowie miteinander kombinieren und einer Auslese… …   Deutsch Wikipedia

  • Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… …   Deutsch Wikipedia

  • Hardwarezufallszahlengenerator — Zufallszahlengenerator fehlen folgende wichtige Informationen: Güte wird nur mangelhaft behandelt Überschneidung mit spezielleren Artikeln sind zu dürftig oder zu ausschweifend Hard und Softwaretechnische Realisierung ist sehr dürftig Du kannst… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”