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

Terme

Die Frage nach komplexeren Berechnungen kann man wie folgt umformulieren: Wie setzt man Grundoperationen zusammen? In der Mathematik führt dies zur Bildung von Termen, etwa dem folgenden Term

7 + (9 + 4) · 8− 14

oder

13 − sign(−17) · 15

als Beispiele für ganzzahlige Terme. Der folgende Term zeigt, dass Terme natürlich auch für andere Datentypen, etwa bool, gebildet werden können:

¬true ∨ (false ∨ (¬false ∧ true))

Diese Beispiele veranschaulichen, dass bei der Termbildung Klammern und Prioritäten zur Festlegung der Auswertungsreihenfolge der Operationen genutzt werden – beim ersten Beispiel wären sonst mehrere Auswertungen (mit jeweils unterschiedlichem Ergebnis!) möglich.

Bedingte Terme

Für Algorithmensprachen werden wir eine weitere Art von Termen kennen lernen, die in normaler Arithmetik nicht eingesetzt werden. Bedingte Terme erlauben – analog dem Auswahloperator in der Pseudocode-Notation – die Auswahl zwischen zwei Alternativen basierend auf dem Test eines Prädikats. Notiert wird ein bedingter Term wie folgt:

if b then t else u fi

Hierbei ist b ein boolescher Term und die beiden Terme t und u sind zwei Terme gleicher Sorte.

Auswertung bedingter Terme

Die Auswertung bedingter Terme folgt einer bestimmten Regel bezüglich undefinierter Werte. Die folgenden Beispiele zeigen einige Auswertungen:

if true then t else u fi		t
if false then t else u fi		u
if true then 3 else ⊥ fi		3
if false then 3 else ⊥ fi		⊥

Im Gegensatz zu allen bisherigen Operationen erzwingt in bedingten Termen ein Teilausdruck, der undefiniert ist, nicht automatisch die Undefiniertheit des Gesamtterms! Dies ist motiviert durch die Auswertungsstrategie, dass nach einem Test nur die ausgewählte Alternative weiter bearbeitet werden sollte – man weiß also gar nicht, ob die andere Alternative eventuell undefiniert ist. Eine tiefer gehende Motivation für diese Regel werden wir allerdings erst im nächsten Kapitel bei der Diskussion applikativer Algorithmen kennen lernen.

Formalisierung von Termen

Um eine eindeutige Syntax für die Termauswertung vorzugeben, ist eine Formalisierung der Bildung und Auswertung von Termen notwendig. Wir zeigen dies für int-Terme in Form einer mathematischen Definition, die erst die erlaubten Konstrukte festlegt und dann alle weiteren Bildungen verbietet.