Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 27
Beispiel 2.3 Nichdeterministischer Ablauf
ОглавлениеEin Beispiel für einen nichtdeterministischen Ablauf bildet die folgende Bearbeitungsvorschrift für das Sortieren eines Stapels von Karteikarten:
Sortieren: Wähle zufällig eine Karte, bilde zwei Stapel (lexikographisch vor der Karte, lexikographisch nach der Karte), sortiere diese (kleineren) Stapel, füge die sortierten Stapel wieder zusammen.
Das Ergebnis ist auf jeden Fall ein korrekt sortierter Stapel, das Verfahren ist somit determiniert.
Das folgende Beispiel zeigt ein nichtdeterminiertes Ergebnis:
Wähle zufällig eine Karte.
Determinierte Algorithmen
Wir bezeichnen nichtdeterministische Algorithmen mit determiniertem Ergebnis als determiniert. Die folgenden Beispiele sollen diese Begriffe noch einmal verdeutlichen:
