Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 94
Definition 3.6 Semantik imperativer Algorithmen
ОглавлениеDie Bedeutung oder Semantik eines imperativen Algorithmus ist eine partielle Funktion, die wie folgt definiert ist:
| [[PROG]]: | W1 × … × Wn V1 × … × Vm | |
| PROG(w1, …, wn) | = | (Z(Y1), …, Z(Ym)) |
| wobei Z | = | α(Z0), |
| Z0(Xi) | = | wi, i = 1, …, n, |
| und Z0(Y) | = | ⊥ für alle Variablen |
| Y ≠ Xi, i = 1, …, n |
Hierbei gelten die folgenden Abkürzungen und Konventionen:
| PROG | Programmname |
| W1, …, Wn | Wertebereiche der Typen von X1, …, Xn |
| V1, …, Vm | Wertebereiche der Typen von Y1, …, Ym |
Der Algorithmentext definiert also eine Transformation auf dem gesamten, durch die Eingaben initialisierten Zustand, aus dem als Bedeutung dann die Werte der Ausgabevariablen ausgelesen werden.
Man beachte, dass die Funktion Z nicht definiert ist, falls die Auswertung von nicht terminiert.
Kurz gefasst lassen sich imperative Algorithmen wie folgt charakterisieren:
Die Algorithmenausführung besteht aus einer Folge von Basisschritten, genauer von Wertzuweisungen. Diese Folge wird mittels Selektion und Iteration basierend auf booleschen Tests über dem Zustand konstruiert. Jeder Basisschritt definiert eine elementare Transformation des Zustands. Die Semantik des Algorithmus ist durch die Kombination all dieser Zustandstransformationen zu einer Gesamttransformation festgelegt.
Diese Konzepte sollen anhand der folgenden Beispiele verdeutlicht werden.
