Nichtdeterminismus ist ein Konzept aus der theoretischen Informatik, in dem Maschinen (meist Turingmaschinen oder endliche Automaten) nicht nur genau eine Berechnung zu einer bestimmten Eingabe durchlaufen können (deterministisch), sondern es bei gleicher Eingabe mehrere Möglichkeiten für den Übergang in den nachfolgenden Zustand gibt.
Diese Maschinen werden meist verwendet, um formale Sprachen zu erkennen, also für eine Eingabe zu entscheiden, ob sie zur Sprache der Maschine gehört oder nicht. Beim Verarbeiten der Eingabe "rät" die nichtdeterministische Maschine nun einen der Übergänge, wobei man annimmt, dass die Maschine "gut raten" kann und dadurch häufig, wenn auch nicht immer, der richtige nachfolgende Zustand erreicht wird, so dass die Berechnung der Maschine letztendlich erfolgreich ist, also die korrekte Antwort bzgl. der Sprachzugehörigkeit ausgegeben wird.
Der Unterschied zu randomisierten Algorithmen besteht darin, dass diese zufällig einen der möglichen Übergänge auswählen. Damit liegt die Wahrscheinlichkeit, dass der richtige Übergang ausgewählt wird, bei
n Möglichkeiten bei 1/n. Somit ist die Wahrscheinlichkeit, dass eine randomisierte Maschine eine erfolgreiche Berechnung durchführt, ungleich viel geringer: Beispielsweise rät ein nichtdeterministischer Algorithmus für die Zerlegung einer Zahl n=pq einfach p und q, und überprüft anschließend nur pq=n. Dieses Verfahren läßt sich offensichtlich nicht für einen randomisierten Algorithmus verwenden.
Warum werden dann in der Praxis trotzdem randomisierte und keine nichtdeterministischen Algorithmen verwendet? Wenn man wüsste, wie die nichtdeterministische Maschine rät, dann könnte man natürlich solche Algorithmen konstruieren, die "fast immer" richtig liegen, und es wäre P = NP (siehe P/NP-Problem). Aber genau dieses wie weiß man natürlich nicht.
Das Konzept wurde von Michael O. Rabin und Dana Scott eingeführt.
Dieser Beitrag ist aus der XML-Version der deutschen WikiPedia® entwickelt worden und unterliegt inhaltlich den GNU FDL-Lizenzbestimmungen. Linkziele außerhalb der wikipedia-Inhalte unterliegen den Urheberrechten der jeweiligen Anbieter
( DirectDownloads ) Kalenderblätter druckfertig aufbereitet für Schmuckblätter zum Selbstdrucken im Word DOC6/RTF Format, je Euro 5 über Click&BuyJAN | FEB | MÄRZ APRIL | MAI | JUNI JULI | AUG | SEPT OKT | NOV | DEZ
Das Geschenk für jeden Anlass, nicht nur bei 'runden' Jubiläen Andere Einzeltage oder Zahlungsarten bitte HIER bestellen
Diese Web Site verdient ihr Geld durch Produktverkäufe (CD-ROM, downloads) und in erster Linie durch Anzeigen. Wenn Sie als Webmaster zuverlässige Partner suchen für Ihr eigenes Anzeigenschäft, dürfen Sie sich gerne auf unsere Empfehlungen stützen:
z.B.: GigaCash & ProfiWin
