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

Eine Reihe von Algorithmen in diesem engeren Sinne sind den meisten aus der elementaren Schulmathematik und dem Organisieren von Unterlagen bekannt:

1 Die Addition zweier positiver Dezimalzahlen (mit Überträgen) ist einer der ersten Algorithmen, die in der Schule gelehrt werden:33+48181

2 Ein komplexerer Algorithmus beschreibt den Test, ob eine gegebene natürliche Zahl eine Primzahl ist.

3 Auch das Sortieren einer unsortierten Kartei (etwa lexikographisch) kann als Algorithmus beschrieben werden.

4 Die Berechnung der dezimalen Darstellung der Zahl e = 2.7182 … hingegen ist ein Spezialfall, auf den wir später noch eingehen werden.

Terminierung

Bevor wir uns die Beschreibung von Algorithmen genauer anschauen, werden erst einige grundlegende Begriffe eingeführt. Der erste ist der Begriff der Terminierung:

Ein Algorithmus heißt terminierend, wenn er (bei jeder erlaubten Eingabe von Parameterwerten) nach endlich vielen Schritten abbricht.

Unser erster Algorithmus zur Addition zweier Dezimalzahlen bestimmt das Ergebnis auch sehr großer Zahlen in endlich vielen Schritten, da er ja jede Stelle der Zahlen (von hinten nach vorne) nur einmal betrachtet und den Übertrag sozusagen »vor sich her schiebt«.

Determinismus

Ein weiterer, ähnlich klingender, aber völlig anders gearteter Begriff ist der Begriff des Determinismus. Der Determinismus legt im gewissen Sinne die »Wahlfreiheit« bei der Ausführung eines Verfahrens fest. Er begegnet uns dabei in zwei Spielarten:

 Ein deterministischer Ablauf bedeutet, dass der Algorithmus eine eindeutige Vorgabe der Schrittfolge der auszuführenden Schritte festlegt.

 Ein determiniertes Ergebnis wird von Algorithmen dann geliefert, wenn bei vorgegebener Eingabe ein eindeutiges Ergebnis geliefert wird – auch bei mehrfacher Durchführung des Algorithmus (natürlich mit denselben Eingabeparametern).

Von Rechnern ausgeführte Programme erfüllen in der Regel beide Eigenschaften – man muss sich sogar Mühe geben, um nichtdeterminierte Effekte zu simulieren, zum Beispiel bei einem Programm, das ein zufälliges Ergebnis etwa beim Würfeln nachbildet. Während nichtdeterminierte Ergebnisse in der Regel unerwünscht sind, sind nichtdeterministische Abläufe gerade beim Entwurf von Algorithmen ein häufig eingesetztes Konzept.