Kurs:Algorithmen und Datenstrukturen/Vorlesung/Anweisungen
Anweisungen Bearbeiten
In diesem Kapitel behandelt wir das Thema Anweisungen.
Arten von Anweisungen Bearbeiten
Dabei unterscheiden wir in zwei verschiedene Anweisungsarten. Zum einen die elementaren Anweisungen wie Wertezuweisungen und zum anderen die komplexen Anweisungen.
Semantik einer Anweisung Bearbeiten
Funktion, die einen Zustand in einen neuen Zustand überführt.
![{\displaystyle [\![\alpha ]\!](z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb848426592d90f105ae6d3b79d42d3e75697043)
Allgemein gesagt ist es die Wirkungsweise von auf den Zustand Z
Beispiele Zuweisung als Anweisung Bearbeiten
Beispiel 1 Bearbeiten
Ein Beispiel ist die Wertezuweisung:
ist eine elementare Anweisung
Diese Wertezuweisung transformiert in eine Funktion auf Zustände sieht wie folgt aus:
![{\displaystyle [\![\alpha _{1}]\!](Z)=Z\langle X\leftarrow 2\cdot Z(Y)+1\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/c8f7294a5cfa1ea817926c3190ea90e9d8c72ab1)
Die Zuweisung berechnet den neuen Zustand.
Der alte Zustand ist und der neue Zustand ist
![{\displaystyle [\![\alpha _{1}]\!](Z)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91da70633e63d59300681dea9b52e66bc2791800)
Beispiel 2 Bearbeiten
Ein weiteres Beispiel ist die Zuweisung mit gleichen Variablen auf beiden Seiten.
Die Transformation in eine Funktion auf Zustände lautet:
![{\displaystyle [\![\alpha _{1}]\!](Z)=Z\langle X\leftarrow 2\cdot Z(X)+1\rangle }](https://wikimedia.org/api/rest_v1/media/math/render/svg/e3a0b3d96b21cabd8be76f2413adca8544380a6e)
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 Bearbeiten
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 Bearbeiten
Sequenzen, oder auch Folgen, sind und Anweisungen, so ist auch eine Anweisung. Die Zustandstransformation beschreibt die Semantik der Sequenz.
![{\displaystyle [\![\alpha _{1};\alpha _{2}]\!](Z)=[\![\alpha _{2}]\!]([\![\alpha _{1}]\!](Z))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df4c1d381be508c4b405cda244729414af6df43a)
Die Semantik ist das Schachteln der Funktionsaufrufe und das daraus folgende hintereinander ausführen der beiden Funktionen.
Selektion Bearbeiten
Eine Selektion, bzw. eine Auswahl, liegt beispielsweise vor, wenn und Anweisungen sind und B ein boolescher Ausdruck ist, dann ist auch
eine Anweisung.
Die zugehörige Zustandstransformation ist:
![{\displaystyle [\![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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c534c8d30a5bc312f117ae28faf7a8c614ec34a)
Voraussetzung ist, dass Z(B) definiert ist, sonst ist die Bedeutung der Auswahlanweisung undefiniert.
Iteration Bearbeiten
Wiederholung (Iteration, Schleife):
Ist α eine Anweisung und B ein boolescher Ausdruck, so ist: while B do α auch eine Anweisung
Zustandstransformation:
![{\displaystyle [\![while~B~do~\alpha ]\!](Z)=\left\{{\begin{array}{ll}Z&falls~Z(B)=false\\\,[\![while~B~do~\alpha ]\!]([\![\alpha ]\!](Z))&sonst\end{array}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0912c6c9b25944bd7bc4495d308a007b15d20556)
Ist Z(B) undefiniert, so ist die Bedeutung dieser Anweisung ebenfalls undefiniert.
Literatur Bearbeiten
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.
