Inhaltsverzeichnis:
- Definition - Was bedeutet nicht deterministischer Algorithmus?
- Techopedia erklärt den nicht deterministischen Algorithmus
Definition - Was bedeutet nicht deterministischer Algorithmus?
Ein nicht deterministischer Algorithmus kann bei verschiedenen Ausführungen unterschiedliche Ausgaben für dieselbe Eingabe bereitstellen. Im Gegensatz zu einem deterministischen Algorithmus, der auch bei verschiedenen Läufen nur eine einzige Ausgabe für dieselbe Eingabe erzeugt, bewegt sich ein nicht deterministischer Algorithmus auf verschiedenen Wegen, um zu den unterschiedlichen Ergebnissen zu gelangen.
Nicht deterministische Algorithmen sind nützlich, um ungefähre Lösungen zu finden, wenn es schwierig oder teuer ist, eine genaue Lösung mit einem deterministischen Algorithmus abzuleiten.
Techopedia erklärt den nicht deterministischen Algorithmus
Ein Beispiel für einen nicht deterministischen Algorithmus ist die Ausführung von gleichzeitigen Algorithmen mit Race-Bedingungen, die bei verschiedenen Läufen unterschiedliche Ausgaben aufweisen können. Im Gegensatz zu einem deterministischen Algorithmus, der einen einzelnen Pfad von der Eingabe zur Ausgabe zurücklegt, kann ein nicht deterministischer Algorithmus viele Pfade zurücklegen, wobei einige an denselben Ausgängen ankommen und andere an unterschiedlichen Ausgängen ankommen. Diese Funktion wird mathematisch in nicht deterministischen Berechnungsmodellen wie dem nicht deterministischen endlichen Automaten verwendet.
Ein nicht deterministischer Algorithmus kann auf einem deterministischen Computer ausgeführt werden, der über eine unbegrenzte Anzahl von Parallelprozessoren verfügt. Ein nicht deterministischer Algorithmus hat normalerweise zwei Phasen und Ausgabeschritte. Die erste Phase ist die Erraten-Phase, in der beliebige Zeichen zum Ausführen des Problems verwendet werden.
Die zweite Phase ist die Überprüfungsphase, die für die ausgewählte Zeichenfolge true oder false zurückgibt. Es gibt viele Probleme, die mit Hilfe nicht deterministischer Algorithmen konzeptualisiert werden können, einschließlich des ungelösten Problems von P vs NP in der Computertheorie.
Nicht deterministische Algorithmen werden zur Lösung von Problemen verwendet, die mehrere Ergebnisse ermöglichen. Jedes Ergebnis, das der nicht deterministische Algorithmus erzeugt, ist gültig, unabhängig von den Entscheidungen, die der Algorithmus während der Ausführung getroffen hat.
