Ursachen für nicht-determinismus

Ursachen dafür, dass ein Algorithmus nicht Deterministisch ist
Ein deterministischer Algorithmus muss an jeder Stelle eindeutig sein. Das Ergebniss jeder einzelnen Anweisung ist eindeutig und an jeder einzelnen Stelle des Ablaufs liegt fest, welcher Schritt als nächstes ausgeführt wird. Eine deterministischer Algorithmus überlässt also nichts dem Zufall.

Wenn ein Algorithmus jedoch nicht deterministisch ist, kann es dafür mehrere Ursachen geben:

-       Elementaroperationen sind nicht eindeutig, d.h. das Ergebnis einer oder mehrerer Operationen ist nicht eindeutig festgelegt

-       Ablaufstrukturen sind nicht eindeutig, d.h. die Ausführungsreihenfolge von Anweisungen ist nicht eindeutig festgelegt.

-       Ein rekursiver Algorithmus ist nicht deterministisch

Nichtdeterminismus als Konzept der Informatik

Ein nichtdeterministischer Algorithmus können nicht nur eine bestimmte Berechnung zu einer bestimmten Eingabe ausführen, sondern eine von mehreren Möglichkeiten wählen. Nichtdeterministische Algorithmen werden oft in der theoretischen Informatik und deren Analyse von Algorithmen verwendet, um die Komplexität von Algorithmen nach Oben abzuschätzen.
Es gibt zahlreiche Beispiele dafür, dass es durchaus einfacher sein kann, einen nichtdeterministischen Algorithmus zu finden, als einen Algorithmus, der deterministisch ist.