Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 28

Die folgende Berechnungsvorschrift bildet ein Beispiel für einen nichtdeterminierten Algorithmus:

1 Nehmen Sie eine beliebige Zahl x.

2 Addieren Sie 5 hinzu und multiplizieren Sie mit 3.

3 Schreiben Sie das Ergebnis auf.

Hingegen ist die folgende Berechnungsvorschrift ein Beispiel für einen determinierten, allerdings nichtdeterministischen Algorithmus:

1 Nehmen Sie eine Zahl x ungleich 0.

2 Entweder: Addieren Sie das Dreifache von x zu x und teilen das Ergebnis durch x(3x +x)/xOder: Subtrahieren Sie 4 von x und subtrahieren das Ergebnis von xx − (x − 4)

3 Schreiben Sie das Ergebnis auf.

Nach einigem Nachdenken sieht man, dass dieses Verfahren immer das Ergebnis 4 liefert (im ersten Fall durch Herauskürzen von x), egal welche Variante man in Schritt 2 gewählt hat.

Diese Beispiele zeigen, dass man Nichtdeterminiertheit und Nichtdeterminismus nur durch eine im gewissen Sinne »freie Wahlmöglichkeit« bekommen kann, ein Konzept, das einem »mechanisch« arbeitenden Computer natürlich prinzipiell fremd ist.

Ein-/Ausgabefunktion

Eine wichtige Klasse für unsere späteren Überlegungen sind daher deterministische, terminierende Algorithmen. Diese definieren jeweils eine Ein-/Ausgabefunktion:

f : Eingabewerte → Ausgabewerte

Genau genommen betrachten wir mit dieser Funktionsdefinition determinierte, terminierende Algorithmen. Algorithmen geben eine konstruktiv ausführbare Beschreibung dieser Funktion an.

Bedeutung / Semantik von Algorithmen

Die Ein-/Ausgabefunktion bezeichnen wir als Bedeutung (oder Semantik) des Algorithmus. Es kann mehrere verschiedene Algorithmen mit der gleichen Bedeutung geben.