Kurs:Algorithmen und Datenstrukturen/Vorlesung/Ausdrücke

Ausdrücke

Ausdrücke entsprechen im Wesentlichen den Termen einer funktionalen/logischen Sprache, jedoch stehen an der Stelle von Unbestimmten nun Variablen. Die Auswertung von Termen ist zustandsabhängig:

Gegebener Term:  $2\cdot X+1$
Wert im Zustand Z ist durch $2\cdot Z(X)+1$ bestimmt

Wert eines Ausdrucks

Der Wert eines Ausdrucks $t(X_1,...,X_n)$ wird mit $Z(t(X_1,...,X_n))$ bezeichnet:

$Z(2\cdot X+1)=2\cdot Z(X)+1$

Damit ist auch die Wertzuweisung mit Variablen möglich

$X:=t(X_1,...,X_n)$

Der Transformierte Zustand ist definiert als:

$[[X:=t(X_1,...,X_n)]](Z)=Z⟨X\leftarrow Z(t(X_1,...,X_n))⟩$

Den Zustand liest man so, dass X dem Wert des Ausdrucks $t(X_1,...,X_n)$ zugeordnet wird. Die Semantikklammern bedeuten, dass eine Anweisung als eine Funktion auf Zuständen definiert ist.

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 3.3.1 zu finden.