5 Unterschied zwischen deterministischen und nicht-deterministischen Algorithmen

Was ist ein deterministischer Algorithmus?

Ein deterministischer Algorithmus ist der Algorithmus, der bei einer bestimmten Eingabe immer die gleiche Ausgabe erzeugt, wobei die zugrunde liegende Maschine immer die gleiche Folge von Zuständen durchläuft. Mit anderen Worten, der deterministische Algorithmus wird bei den gleichen Eingaben immer das gleiche Ergebnis liefern.

Deterministische Algorithmen sind bei weitem die am besten untersuchte und bekannte Art von Algorithmen sowie eine der praktischsten, da sie effizient auf realen Maschinen ausgeführt werden können. Formal berechnet ein deterministischer Algorithmus eine mathematische Funktion; eine Funktion hat einen eindeutigen Wert für jede Eingabe in ihrem Bereich, und der Algorithmus ist ein Prozess, der diesen bestimmten Wert als Ausgabe erzeugt.

Deterministische Algorithmen können in Form einer Zustandsmaschine definiert werden: Ein  Zustand  beschreibt, was eine Maschine zu einem bestimmten Zeitpunkt tut. Zustandsautomaten gehen auf diskrete Weise von einem Zustand in einen anderen über. Unmittelbar nach der Eingabe befindet sich die Maschine in ihrem  Anfangszustand  oder  Startzustand . Wenn die Maschine deterministisch ist, bedeutet dies, dass ihr aktueller Zustand ab diesem Zeitpunkt ihren nächsten Zustand bestimmt; sein Verlauf durch die Zustandsmenge ist vorbestimmt. Beachten Sie, dass eine Maschine deterministisch sein kann und dennoch niemals stoppt oder endet und daher kein Ergebnis liefert.

Beispiele für bestimmte abstrakte Maschinen, die deterministisch sind, umfassen die  deterministische Turing-Maschine  und den  deterministischen endlichen Automaten .

Was Sie über deterministischen Algorithmus wissen müssen

• Ein deterministischer Algorithmus ist der Algorithmus, der bei einer bestimmten Eingabe immer die gleiche Ausgabe erzeugt, wobei die zugrunde liegende Maschine immer die gleiche Folge von Zuständen durchläuft.  
• Beim deterministischen Algorithmus ist der Ausführungspfad für den Algorithmus bei jeder Ausführung gleich.
• Auf der Grundlage der Ausführung und des Ergebnisses im Fall des deterministischen Algorithmus werden sie auch als zuverlässige Algorithmen klassifiziert, da die Maschine für einen bestimmten Eingabebefehl immer die gleiche Ausgabe liefert.
• Bei der Ausführung deterministischer Algorithmen führt die Zielmaschine denselben Befehl aus und führt zu demselben Ergebnis, das nicht von der Art oder dem Prozess abhängt, in dem der Befehl ausgeführt wird.
• Da das Ergebnis bekannt ist und bei verschiedenen Ausführungen konsistent ist, benötigt der deterministische Algorithmus polynomielle Zeit für ihre Ausführung.

Was ist ein nicht-deterministischer Algorithmus?

Ein nichtdeterministischer Algorithmus ist ein Algorithmus, der selbst für dieselbe Eingabe bei verschiedenen Durchläufen unterschiedliche Verhaltensweisen zeigen kann. Mit anderen Worten, es ist ein Algorithmus, bei dem das Ergebnis jedes Algorithmus nicht eindeutig definiert ist und das Ergebnis zufällig sein kann.

Ein Algorithmus, der ein Problem in nichtdeterministischer polynomialer Zeit löst, kann in polynomialer oder exponentieller Zeit ausgeführt werden, abhängig von den Entscheidungen, die er währenddessen trifft. Die nichtdeterministischen Algorithmen werden oft verwendet, um eine Annäherung an eine Lösung zu finden, wenn die genaue Lösung mit einer deterministischen zu teuer wäre.

Ein nichtdeterministischer Algorithmus unterscheidet sich von seinem bekannteren deterministischen Gegenstück darin, dass er über verschiedene Wege zu Ergebnissen gelangen kann. Wenn ein deterministischer Algorithmus einen einzelnen Weg von einer Eingabe zu einem Ergebnis darstellt, stellt ein nichtdeterministischer Algorithmus einen einzelnen Weg dar, der in viele Wege führt, von denen einige zu derselben Ausgabe und andere zu einzigartigen Ausgaben gelangen können. 

Was macht einen Algorithmus nicht deterministisch?

Eine Vielzahl von Faktoren kann dazu führen, dass sich ein Algorithmus nicht deterministisch oder nicht deterministisch verhält:

• Wenn ein anderer externer Zustand als die Eingabe verwendet wird, z. B. eine Benutzereingabe, eine globale Variable, ein Hardware-Timerwert, ein Zufallswert oder gespeicherte Festplattendaten.
• Wenn es zeitabhängig arbeitet, beispielsweise wenn mehrere Prozessoren gleichzeitig auf dieselben Daten schreiben. In diesem Fall beeinflusst die genaue Reihenfolge, in der jeder Prozessor seine Daten schreibt, das Ergebnis.
• Wenn ein Hardwarefehler zu einer unerwarteten Zustandsänderung führt.

Was Sie über nicht-deterministischen Algorithmus wissen müssen

• Nicht-deterministischer Algorithmus ist der Algorithmus, bei dem das Ergebnis jedes Algorithmus nicht eindeutig definiert ist und das Ergebnis zufällig sein kann.
• Beim nicht-deterministischen Algorithmus ist der Ausführungspfad nicht für jeden Algorithmus bei jeder Ausführung gleich und kann einen beliebigen zufälligen Pfad für seine Ausführung nehmen.
• Nicht deterministische Algorithmen werden als nicht zuverlässige Algorithmen für eine bestimmte Eingabe klassifiziert, die die Maschine bei verschiedenen Ausführungen unterschiedlich ausgibt.
• Bei nicht-deterministischen Algorithmen darf die Maschine, die jede Operation ausführt, jedes dieser Ergebnisse abhängig von einer später zu definierenden Bestimmungsbedingung auswählen.
• Da das Ergebnis nicht bekannt ist und bei verschiedenen Ausführungen nicht konsistent ist, konnte der nicht-deterministische Algorithmus nicht in polynomieller Zeit ausgeführt werden.

Lesen Sie auch : Unterschied zwischen NP Hard und NP Complete Problem

Unterschied zwischen deterministischen und nicht-deterministischen Algorithmen in Tabellenform