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

Komplexe Anweisungen

Die komplexen Anweisungen imperativer Algorithmen bilden eine Untermenge der intuitiven Algorithmenbausteine aus dem vorigen Kapitel.

Sequenz

1 Die Folge oder Sequenz bildet den ersten Baustein imperativer Algorithmen: Sind α1 und α2 Anweisungen, so ist α1;α2 auch eine Anweisung.Die Bedeutung der Sequenz ist durch die folgende Zustandstransformation festgelegt:α1;α2(Z) = α2(α1(Z))Anders formuliert, entspricht eine Sequenz der geschachtelten (Hintereinander-)Ausführung der beiden Funktionen, die die einzelnen Schritte definieren.

Selektion

1 2. Die Auswahl oder Selektion bildet den zweiten Baustein: Sind α1 und α2 Anweisungen und B ein boolescher Ausdruck, so ist

if B then α₁ else α₂ fi

eine Anweisung.

Die Semantik der Selektion ist wiederum durch eine Transformation definiert:

In dieser Definition wird vorausgesetzt, dass Z(B) definiert ist. Ansonsten ist die Bedeutung der Auswahlanweisung undefiniert.

Iteration

1 3. Die letzte und für imperative Algorithmen charakteristische Kontrollstruktur ist die Wiederholung oder Iteration : Ist eine Anweisung und B ein boolescher Ausdruck, so ist

while B do α od

eine Anweisung. Die Iteration wird wie bei den intuitiven Algorithmen oft als Schleife bezeichnet.

Die Bedeutung ist durch folgende Transformation festgelegt:

Ist Z(B) undefiniert, so ist die Bedeutung dieser Anweisung ebenfalls undefiniert. Man beachte, dass diese Definition rekursiv ist.

Die rekursive Definition der Iterationstransformation ist ein Hinweis darauf, dass die Iteration das Gegenstück zu rekursiven Funktionsaufrufen bei applikativen Algorithmen ist. Tatsächlich werden wir sehen, dass beide Sprachkonstrukte dieselbe Ausdrucksfähigkeit bezüglich formulierbarer Algorithmen aufweisen.

Imperative Algorithmen sind die Grundlage der sogenannten imperativen Programmiersprachen. Die Umsetzung in diese Programmiersprachen gibt Anlass zu einigen Bemerkungen:

 In realen imperativen Programmiersprachen gibt es fast immer diese Anweisungen, meistens jedoch viel mehr.

 while-Schleifen sind rekursiv definiert, ihre rekursive Auswertung braucht nicht zu terminieren.

 Die Verwendung von if-fi ist wegen der klaren Klammerung der Variante ohne abschließendes Schlüsselwort vorzuziehen, da eine Fehlerquelle eliminiert wird.

 Programmiersprachen nur mit diesen Sprachelementen sind bereits universell in dem Sinne, dass alle Algorithmen formulierbar sind (siehe weiter unten).

Wir beschränken uns im Folgenden auch bei den imperativen Algorithmen auf die Datentypen bool und int.

Syntax imperativer Algorithmen

Nach den bisherigen Festlegungen können wir nun die komplette Syntax imperativer Algorithmen festlegen. Imperative Algorithmen haben folgenden Aufbau:

< Programmname >:
var X, Y, … : int;P, Q, … : bool	⇐ Variablendeklaration
input X1, …, Xn;	⇐ Eingabevariablen
α;	⇐ Anweisung(en)
output Y1, …, Ym.	⇐ Ausgabevariablen

Die Festlegung einer formalen Bedeutung für imperative Algorithmen ist komplexer als für applikative Algorithmen. Auch hier soll ein Algorithmentext eine Funktion als Semantik festlegen. Diese Semantikfestlegung basiert auf den bereits eingeführten Transformationsfunktionen der einzelnen Anweisungstypen.