Anweisungen

In diesem Kapitel behandelt wir das Thema Anweisungen.

Arten von Anweisungen

Dabei unterscheiden wir in zwei verschiedene Anweisungsarten. Zum einen die elementaren Anweisungen wie Wertezuweisungen und zum anderen die komplexen Anweisungen.

Semantik einer Anweisung

Funktion, die einen Zustand in einen neuen Zustand überführt. $[\![\alpha ]\!](z)$

Allgemein gesagt ist es die Wirkungsweise von $\alpha$ auf den Zustand Z

Beispiele Zuweisung als Anweisung

Beispiel 1

Ein Beispiel ist die Wertezuweisung:

 $\alpha _{1}=(X:=2\cdot Y+1)$

$\alpha _{1}$ ist eine elementare Anweisung

Diese Wertezuweisung transformiert in eine Funktion auf Zustände sieht wie folgt aus:

 $[\![\alpha _{1}]\!](Z)=Z\langle X\leftarrow 2\cdot Z(Y)+1\rangle$

Die Zuweisung berechnet den neuen Zustand.

Der alte Zustand ist $Z$ und der neue Zustand ist $[\![\alpha _{1}]\!](Z)$

Beispiel 2

Ein weiteres Beispiel ist die Zuweisung mit gleichen Variablen auf beiden Seiten.

 $\alpha _{1}=\langle X:=2\cdot X+1\rangle$

Die Transformation in eine Funktion auf Zustände lautet:

 $[\![\alpha _{1}]\!](Z)=Z\langle X\leftarrow 2\cdot Z(X)+1\rangle$

Bei der letzten Anweisung handelt es sich nicht um eine rekursive Gleichung! An dieser Stelle sei vermerkt, dass Wertezuweisungen die einzigen elementaren Anweisungen sind.

Komplexe Anweisungen

Bisher haben wir elementare Anweisungen (Wertzuweisungen) als Funktionen auf Zustände verstanden. Komplexe Anweisungen nehmen Konstrukte bzw. Bausteine von imperativen Algorithmen. Diese Bausteine sind

Sequenz
Auswahl/Selektion
Iteration

Die Semantik wird wiederum durch Konstruktion von Funktionen definiert. Iteration ist das Gegenstück zu rekursiven Funktionsaufrufen bei funktionalen Algorithmen

Sequenz

Sequenzen, oder auch Folgen, sind $\alpha _{1}$ und $\alpha _{2}$ Anweisungen, so ist $\alpha _{1};\alpha _{2};$ auch eine Anweisung. Die Zustandstransformation beschreibt die Semantik der Sequenz.

 $[\![\alpha _{1};\alpha _{2}]\!](Z)=[\![\alpha _{2}]\!]([\![\alpha _{1}]\!](Z))$

Die Semantik ist das Schachteln der Funktionsaufrufe und das daraus folgende hintereinander ausführen der beiden Funktionen.

Selektion

Eine Selektion, bzw. eine Auswahl, liegt beispielsweise vor, wenn $\alpha _{1}$ und $\alpha _{2}$ Anweisungen sind und B ein boolescher Ausdruck ist, dann ist auch

 $if~B~then~\alpha _{1}~else~\alpha _{2}$

eine Anweisung.

Die zugehörige Zustandstransformation ist: $[\![if~B~then~\alpha _{1}~else~\alpha _{2}]\!](Z)=\left\{{\begin{array}{ll}[\![\alpha _{1}]\!](Z)&\quad falls~Z(B)=true\\\,[\![\alpha _{2}]\!](Z)&\quad falls~Z(B)=false\end{array}}\right.$

Voraussetzung ist, dass Z(B) definiert ist, sonst ist die Bedeutung der Auswahlanweisung undefiniert.

Iteration

Wiederholung (Iteration, Schleife):

Ist α eine Anweisung und B ein boolescher Ausdruck, so ist:
while B do α
auch eine Anweisung

Zustandstransformation: $[\![while~B~do~\alpha ]\!](Z)=\left\{{\begin{array}{ll}Z&falls~Z(B)=false\\\,[\![while~B~do~\alpha ]\!]([\![\alpha ]\!](Z))&sonst\end{array}}\right.$

Ist Z(B) undefiniert, so ist die Bedeutung dieser Anweisung ebenfalls undefiniert.

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 und 3.3.2 zu finden.

Kurs:Algorithmen und Datenstrukturen/Vorlesung/Anweisungen

Inhaltsverzeichnis