3Algorithmenparadigmen

Paradigmen für Algorithmen

Unter einem Paradigma versteht man unter anderem in der Wissenschaftstheorie ein »Denkmuster, welches das wissenschaftliche Weltbild einer Zeit prägt« – ein Algorithmenparadigma sollte daher ein Denkmuster darstellen, das die Formulierung und den Entwurf von Algorithmen und damit letztendlich von Programmiersprachen grundlegend prägt. Es wundert daher nicht, dass es keine einheitliche Auffassung über die Anzahl existierender Algorithmenparadigmen und deren Abgrenzung gibt.

3.1Überblick über Algorithmenparadigmen

Ein Algorithmenparadigma legt die Denkmuster fest, die einer Beschreibung eines Algorithmus zugrunde liegen. Ein Algorithmus ist eine Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-)Schritte (vergl. Abschnitt 2.1).

Wir werden zwei grundlegende Arten kennen lernen, Schritte von Algorithmen zu notieren:

Applikative Algorithmen

• Applikative Algorithmen sind eine Verallgemeinerung der Funktionsauswertung mathematisch notierter Funktionen. In ihnen spielt Rekursion eine wesentliche Rolle.

Imperative Algorithmen

• Imperative Algorithmen basieren auf einem einfachen Maschinenmodell mit gespeicherten und änderbaren Werten. Hier werden primär Schleifen und Alternativen als Kontrollbausteine eingesetzt.

In der Informatik werden weitere Paradigmen diskutiert: logisch, objektorientiert, agentenorientiert, parallel sind einige der bekannteren Stichwörter in diesem Zusammenhang.

Logisches Paradigma

Wir werden das logische Paradigma ebenfalls vorstellen, obwohl es streng genommen kein Algorithmenparadigma gemäß unserer intuitiven Begriffsbildung ist (wohl aber ein Programmierparadigma, doch dazu später) – ein logisches Programm ergibt erst zusammen mit einem von mehreren möglichen Interpretationsalgorithmen und einer Anfrage einen ausführbaren Algorithmus im engeren Sinne.

Objektorientiertes Paradigma

Auch das objektorientierte Paradigma ist kein Algorithmenparadigma im engeren Sinne, da es sich um ein Paradigma zur Strukturierung von Algorithmen handelt, das sowohl mit applikativen, imperativen und logischen Konzepten zusammen eingesetzt werden kann. Wir werden es im Zusammenhang mit der Programmiersprache Java intensiver diskutieren.

Paradigmen von Java

Zu den Paradigmen korrespondieren jeweils Programmiersprachen, die diesen Ansatz realisieren. Moderne Programmiersprachen vereinen oft Ansätze mehrerer Paradigmen. Die Sprache Java kann als objektorientiert und imperativ zusammen mit Elementen von applikativen Algorithmen charakterisiert werden.

3.2Applikative Algorithmen

Die Idee applikativer Algorithmen besteht darin, eine Definition zusammengesetzter Funktionen durch Terme mit Unbestimmten vorzunehmen. Eine einfache Funktionsdefinition in diesem Sinne kann wie folgt mathematisch notiert werden:

Streng genommen erfüllt die Funktionsdefinition erst zusammen mit dem bereits skizzierten Auswertungsalgorithmus für Terme unsere Anforderungen an eine Algorithmensprache – erst die Termauswertung legt die Reihenfolge der atomar auszuführenden Berechnungsschritte fest.

In diesem Abschnitt beschränken wir uns zur Vereinfachung der Definitionen auf Funktionen über int und bool, obwohl die Konzepte natürlich für beliebige Datentypen gelten.

Bevor wir eine Sprache zur Formulierung applikativer Algorithmen einführen, müssen einige grundlegende Konzepte definiert werden.

3.2.1Terme mit Unbestimmten

Unbestimmte

Gegeben sind im Folgenden zwei (unendliche, abzählbare) Mengen von Symbolen (als »Unbestimmte« bezeichnet):

• x, y, z, … vom Typ int
• q, p, r, … vom Typ bool

Terme mit Unbestimmten

Wir müssen nun unsere bisherige Definition von Termen (siehe Definition 2.1 für int-Terme) auf Terme mit Unbestimmten erweitern. Ein Term mit Unbestimmten wird analog zu Termen ohne Unbestimmte gebildet, so sind

x, x − 2, 2x + 1, (x + 1)(y − 1)

Terme vom Typ int und

p, p ∧ true, (p ∨ true) = ⇒ (q ∨ false)

Terme vom Typ bool.

3.2.2Funktionsdefinitionen

Basierend auf der erweiterten Termdefinition, können wir nun eine Notation für Funktionsdefinitionen festlegen.

Definition 3.1 Funktionsdefinitionen

Sind v₁, …, v_n Unbestimmte vom Typ τ₁, …, τ_n (bool oder int) und ist t(v₁, …, v_n) ein Term, so heißt

f(v₁, …, v_n) = t(v₁, …, v_n)

eine Funktionsdefinition der Funktion f vom Typ τ. τ ist dabei der Typ des Terms t(v₁, …, v_n).

Wir werden die folgende Sprechweise verwenden: f heißt Funktionsname, die v₁, …, v_n heißen formale Parameter und der Term t(v₁, …, v_n) heißt Funktionsausdruck.

Beispiel 3.1 Beispiele für Funktionsdefinitionen

Die folgenden drei Definitionen sind einfache Beispiele für Funktionsdefinitionen:

1. f(p, q, x, y) =if p ∨ q then 2x + 1 else 3y − 1 fi
2. g(x) =if even(x) then x ÷ 2 else 3x − 1 fi
3. h(p, q) =if p then q else false fi

Bevor wir zur eigentlichen Definition applikativer Algorithmen kommen, müssen wir unsere Verfahren der Termauswertung auf die Auswertung definierter Funktionen ausweiten.

3.2.3Auswertung von Funktionen

Definierte Funktionen können mit konkreten Werten aufgerufen und ausgewertet werden. Eine Funktionsdefinition gemäß Definition 3.1 definiert eine Funktion der folgenden Signatur:

f : τ₁ × … × τ_n → τ

Sind nun a₁, .., a_n Werte vom Typ τ₁, .., τ_n, so ersetzt man bei der Auswertung von f(a₁, .., a_n) im definierenden Term jedes Vorkommen der Unbestimmten v_i durch den Wert a_i und wertet dann den entstehenden Term t(a₁, .., a_n) aus.

Aufruf und Auswertung von Funktionen

Die konkreten Werte a₁, …, a_n heißen aktuelle Parameter. Den Ausdruck f(a₁, …, a_n) bezeichnen wir als Funktionsaufruf.

Beispiel 3.2 Funktionsaufrufe

In Erweiterung des Beispiels 3.1 führen wir einige Aufrufe und die resultierenden Ergebnisse auf:

1. f(p, q, x, y) =if p ∨ q then 2x + 1 else 3y − 1 fi
   Die resultierende Funktion hat die folgende Signatur:

   f : bool × bool × int × int → int

   Der Aufruf f (true, true, 3, 4) wird zu 7 ausgewertet.

2. g(x) =if even(x) then x ÷ 2 else 3x − 1 fi

   Die resultierende Funktion hat die folgende Signatur:

   g : int → int

   Die Ergebnisse zweier Aufrufe lauten:

   g(2) = 1, g(3) = 8

   Beim ersten Aufruf g (2) wurde dabei folgender Term ausgewertet:

   if even(2) then 2 ÷ 2 else 3 · 2 − 1 fi

3. h(p, q) =if p then q else false fi definiert eine boolesche Funktion mit zwei Parametern:

   h: bool × bool → bool

   Die Beispielauswertung h(false, false) = false gibt uns einen Hinweis auf die Semantik der neu definierten Funktion: h(p, q) = p ∧ q, unser Beispiel realisiert das logische Und nur mithilfe der Implikation und der Konstanten false.

3.2.4Erweiterung der Funktionsdefinition

Erweiterung der Funktionsdefinition

Als nächsten Schritt führen wir eine Erweiterung der Klassen der Terme und Funktionsdefinitionen durch, indem wir Aufrufe definierter Funktionen als Terme verwenden.

Beispiel 3.3 Erweiterte Funktionsdefinition

Als Beispiel für eine derartig erweiterte Funktionsdefinition betrachten wird die folgenden vier Definitionen:

Die Funktion h ruft die Funktion j zweimal auf. Ein Beispiel für die Auswertung derartiger erweiterter Terme zeigt der Aufruf f (1, 2):

Die Auswertung erfolgt dadurch, dass jeweils ein Funktionsaufruf durch den ihn definierenden Term ersetzt wird.

Mit der abkürzenden Notation * bezeichnen wir die konsekutive Ausführung mehrerer elementarer Termauswertungsschritte.

Eine Funktionsdefinition f heißt rekursiv, wenn direkt (oder indirekt über andere Funktionen) ein Funktionsaufruf f(..) in ihrer Definition auftritt.

Beispiel 3.4 Rekursive Funktionsdefinition

Ein Beispiel für eine Rekursion zeigt folgende Definition:

Die bisherige Auswertungsstrategie kann auf rekursive Funktionsdefinitionen ebenfalls angewandt werden, so dass wir folgende Auswertungen erhalten:

Unsere rekursive Definition realisiert also die Addition nur mithilfe der Successor-Funktion »+1«.

3.2.5Applikative Algorithmen

Wir haben nun alle Vorbereitungen zusammen, um die Klasse der applikativen Algorithmen definieren zu können.

Definition 3.2 Applikativer Algorithmus

Ein applikativer Algorithmus ist eine Liste von Funktionsdefinitionen:

Die erste Funktion f₁ wird wie beschrieben ausgewertet und ist die Bedeutung (Semantik) des Algorithmus.

Applikative Algorithmen sind die Grundlage einer Reihe von universellen Programmiersprachen, wie APL, Lisp, Scheme, Haskell oder Scala etc. Diese Programmiersprachen werden als funktionale Programmiersprachen bezeichnet.

Ein applikativer Algorithmus muss nicht für alle Eingabewerte zu einem definierten Ergebnis führen. Das folgende Beispiel verdeutlicht dies.

Beispiel 3.5 Undefinierte Ergebnisse

Eine Funktion muss nicht für alle Eingaben definiert sein:

f(x) = if x = 0 then 0 else f(x − 1) fi

Wir betrachten einige Auswertungen:

Eine nicht terminierende Berechnung führt als Vereinbarung zum Ergebnis ⊥ für undefiniert. Also gilt

Die Funktion f hat somit nur für positive Zahlen ein definiertes Ergebnis.

Partielle Funktionen

Eine (möglicherweise) für einige Eingabewertekombinationen undefinierte Funktion heißt partielle Funktion.

Im folgenden Abschnitt werden wir einige Aspekte applikativer Algorithmen anhand einfacher Beispiele erläutern und damit gleichzeitig die bereits vorgestellten Konzepte an konkreten Beispielen verdeutlichen.

3.2.6Beispiele für applikative Algorithmen

Wir beginnen mit dem »klassischen« Beispiel für rekursive Funktionsdefinitionen, das wir schon in Abschnitt 2.1.5 kurz eingeführt haben: Die Fakultätfunktion n!.

Beispiel 3.6 Fakultätfunktion n!

Die Fakultätfunktion ist mathematisch wie folgt definiert:

x! = x(x − 1)(x − 2) … 2 · 1 für x > 0

Die bekannte rekursive mathematische Definition lautet 0! = 1 und x! = x · (x − 1)!. Das nahe liegende Problem bei dieser Definition ist die Behandlung negativer Eingabewerte.

Unsere erste Lösung überträgt die gegebene mathematische Gleichung direkt in den Formalismus der applikativen Algorithmen:

fac(x) = if x = 0 then 1 else x · fac(x − 1) fi

Die Bedeutung dieser Funktionsdefinition kann wie folgt angegeben werden:

Eine zweite Lösungsvariante versucht die Undefiniertheit im negativen Bereich zu vermeiden:

fac(x) = if x ≤ 0 then 1 else x · fac(x − 1) fi

Die Bedeutung ist nun:

Welche Lösung ist nun die bessere? Diese Frage lässt sich nicht einfach beantworten. Die erste Variante ist mathematisch korrekt, führt aber bei einer Eingabe von − 1 zu einer nicht abbrechenden rekursiven Berechnung – im praktischen Einsatz ein unschönes Verhalten. Die zweite vermeidet diesen Effekt, hält sich aber nicht an die Vorgabe der mathematischen Definition – allerdings ist das Ergebnis immer korrekt, wenn der Definitionsbereich der Fakultätsfunktion eingehalten wird.

Fibonacci-Zahlen

Ein weiteres bekanntes mathematisches Beispiel für Rekursion sind die Fibonacci-Zahlen. Entwickelt wurde diese Zahlenreihe, um zum Beispiel die Progression bei der Vermehrung von Tieren darzustellen. Ein vereinfachtes Modell wäre folgendes:

Fruchtbare Kaninchen

Dieses Verhalten kann direkt in die Definition der Fibonacci-Zahlen umgesetzt werden:

Beispiel 3.7 Fibonacci-Zahlen

Die Fibonacci-Zahlen sind wie folgt definiert:

f₀ = f₁ = 1, f_i = f_i−1 + f_i−2 für i > 0

Man erkennt direkt die Umsetzung der informellen Beschreibung unserer idealisierten Kaninchenwelt: f_i−1 ist die Anzahl der Kaninchenpaare vor einem Monat (kein Kaninchen stirbt – wie gesagt, eine ideale Kaninchenwelt), und alle Paare, die schon mindestens zwei Monate alt sind, bekommen Nachwuchs, also f_i−2 neue Paare.

Als applikativer Algorithmus schreibt sich die Definition wie folgt:

Die Bedeutung ist wieder einfach festzulegen:

Da die Auswertung der Fibonacci-Zahlen bereits für kleine Zahlen sehr aufwendig wird und die Ergebnisse exponentiell wachsen, wird uns diese Funktion noch öfter als Beispiel für rekursives Verhalten begegnen.

Die bisherigen Beispiele waren von eher mathematischem Interesse. Das folgende Beispiel ist für die Informatiksichtweise interessant: Nehmen wir an, wir hätten einen Rechner, der nur die Addition beherrscht. Wie können wir trotzdem eine Multiplikation realisieren? Derartige Fragestellungen spielen bei der Umsetzung von Programmen auf einfachere Hardware eine wichtige Rolle.

Beispiel 3.8 Produkt nur unter Verwendung der Addition

Ziel ist die Berechnung des Produkts zweier Zahlen nur unter Verwendung der Addition. Wir können dabei folgende Regeln ausnutzen:

Diese Regeln lassen sich wieder direkt in einen applikativen Algorithmus umsetzen:

Analog ließe sich die Exponentialfunktion auf die Multiplikation zurückführen.

Das folgende Beispiel ist sozusagen der Prototyp aller mathematischen Algorithmen in der abendländischen Geschichte. Es handelt sich um die exakte Formulierung des euklidischen Algorithmus zur Berechnung des größten gemeinsamen Teilers zweier Zahlen.

Beispiel 3.9 Größter gemeinsamer Teiler ggT

Berechnet wird der größte gemeinsamer Teiler ggT zweier natürlicher Zahlen.

Für x > 0 und y > 0 gelten folgende Zusammenhänge:

Basierend auf diesen Gesetzmäßigkeiten, können wir folgenden applikativen Algorithmus formulieren:

Die definierte Funktion ggT ist korrekt für positive Eingaben, bei negativen Eingaben und Null ergeben sich nicht abbrechende Berechnungen (partiell undefinierte Funktion).

Die folgende Beispielauswertung verdeutlicht die Arbeitsweise des applikativen Algorithmus:

Dieses Schema ist eine Formalisierung des Originalverfahrens von Euklid (Euklid: Elemente, 7. Buch, Satz 2; ca. 300 v.Chr.).

Das folgende Beispiel demonstriert den Einsatz mehrerer Funktionen in einem applikativen Algorithmus:

Beispiel 3.10 Applikativer Algorithmus mit mehreren Funktionen

Realisiert werden soll der Test, ob eine Zahl gerade ist: even (x). Wir bedienen uns wieder einiger mathematischer Regeln:

Diese Regeln lassen sich nun wie folgt direkt in den gewünschten Testalgorithmus umsetzen:

Einen Algorithmus für den Test auf ungerade Zahlen odd erhalten wir einfach durch Vertauschen der Reihenfolge der Funktionsdefinitionen.

Bisher konnten wir jeweils einfache mathematische Regeln direkt in Funktionsterme umsetzen. Dass dieses nicht immer so einfach ist, zeigt das folgende Beispiel: der Primzahltest. Am Beispiel dieses Verfahrens werden wir auch erstmals die Frage des Aufwandes der Berechnung eines applikativen Funktionsaufrufs betrachten und uns Gedanken über die Effizienz eines Verfahrens machen.

Beispiel 3.11 Primzahltest

Der folgende applikative Algorithmus realisiert einen Primzahltest mithilfe einer Hilfsfunktion.

Die Hilfsfunktion pr(x, y) liefert genau dann den Wert true für wahr, wenn die Zahl y durch keine Zahl z, x ≤ z < y teilbar ist. Unter dieser Voraussetzung gilt sicher folgender Zusammenhang:

prim(x) (x > 1) ∧ pr (2, x)

Die applikative Lösung setzt diese Formel nun direkt um in einen Algorithmus. An zwei einfachen Beispielen kann man sich das Prinzip klar machen: Für prim (5) wird zunächst pr(2, 5) aufgerufen. Da 5 mod 2 = 1 ist, wird im nächsten Schritt pr(3, 5) aufgerufen, gefolgt von pr(4, 5) und schließlich pr(5, 5). Wegen 5 ≥ 5 ist die Abarbeitung beendet und pr(2, 5) liefert true. Betrachtet man dagegen prim(6), so liefert bereits der Aufruf von pr(2, 6) das Ergebnis false, da 6 mod 2 = 0.

Optimierung des Aufwandes des Primzahltests

Diese Lösung ist nicht sehr effizient, da unnötig viele Zahlen getestet werden. Bereits durch kleine Modifikationen kann man den Aufwand des Primzahltests deutlich verringern:

• Ersetze x ≥ y durch x · x > y. Der kleinster Teiler einer Nichtprimzahl ist sicher nie größer als deren Quadratwurzel!
• Ersetze pr(x + 1, y) durch if x = 2 then pr(3, y) else pr(x + 2, y) fi. Dies funktioniert, da 2 die einzige gerade Zahl sein kann, die kleinster Teiler einer Nichtprimzahl ist. Für das obige Beispiel wird nach pr(3, 5) also direkt pr(5, 5) ausgeführt.

Unendliche Berechnungen bei der Termauswertung führen zu undefinierten Werten. Das folgende Beispiel zeigt, dass mit undefinierten Werten vorsichtig umgegangen werden muss, um nicht widersprüchliche Aussagen zu bekommen.

Beispiel 3.12 Terminierung und undefinierte Funktionen

Als ein Beispiel für die Problematik der Terminierung und undefinierter Funktionen betrachten wir folgenden Algorithmus:

f(x) = if f(x) = 0 then 1 else 0 fi

Man sieht sofort, dass eine Auswertung des Tests aufgrund der Rekursion zu einer unendlichen Berechnung führt:

f(x) = ⊥für allex ∊ int

Nun könnte man auf die Idee kommen, folgenden Schluss zu ziehen: Da f(x) = ⊥, gilt etwa f(7) ≠ 0, und damit wird der zweite Zweig der Auswahl ausgewählt: f(7) = 0. Dies ist nun ein Widerspruch, den man auflösen muss.

Vorsicht beim »Rechnen« mit ⊥!

Also gilt: Vorsicht beim »Rechnen« mit ⊥! Sowohl 0 = ⊥ als auch 0 ≠ ⊥ werden beide zu ⊥ ausgewertet. Des Weiteren gilt immer die folgende Auswertung:

if ⊥ then t else u fi= ⊥

Diese Festlegung passt auch zu der Auffassung von ⊥ als »unendlich lange Berechnung«.

Bedeutung von Algorithmen

Wir hatten bisher immer ein Problem vorgegeben und dazu einen Algorithmus ausgeführt, der die Lösung des Problems als Semantik hatte. Wie ist es aber nun umgekehrt – gegeben sei ein Algorithmus, kann man einfach daraus die Bedeutung ablesen? Dieses Problem hat zwei Aspekte: Kann man die mathematische Funktion bestimmen, die berechnet wird, und kann man diese Funktion dann auch semantisch interpretieren, also mit einer sinnvollen Problemstellung verknüpfen? Wir betrachten wieder einige Beispiele.

Beispiel 3.13 McCarthys 91-Funktion

Das erste Beispiel soll zeigen, dass die Bestimmung der Bedeutung keine einfache Aufgabe ist. Wir betrachten folgenden Algorithmus:

f(x) = if x > 100 then x − 10 else f(f(x + 11)) fi

Um einen ersten Eindruck zu bekommen, betrachten wir ein paar Beispielberechnungen:

Tatsächlich gilt die folgende Äquivalenz:

f(x) = if x > 100 then x − 10 else 91 fi

Aufgrund dieser Äquivalenz und seines »Erfinders« ist dieser Algorithmus auch als McCarthys 91-Funktion bekannt. Der Beweis dieser Äquivalenz ist allerdings nicht ganz einfach! In Abschnitt 7.2 werden wir anhand dieser Funktion die Korrektheit applikativer Algorithmen behandeln (Beispiel 7.7 auf Seite 207).

Dieses Beispiel zeigt ein erstes Problem auf, mit dem wir uns später noch intensiver beschäftigen werden: Wie kann bewiesen werden, dass ein gegebener applikativer Algorithmus eine gegebene mathematische Funktion als Semantik hat, oder auch wie kann man die Äquivalenz zweier applikativer Algorithmen beweisen?

Das folgende Beispiel zeigt, dass bereits bei einfachen Funktionen diese Beweisführung kritisch ist.

Beispiel 3.14 Algorithmus mit kniffeliger Bedeutung

Algorithmen können durchaus eine «kniffelige Bedeutung« haben. Wir betrachten die folgenden beiden Funktionsdefinitionen:

Da g eine negative Zahl immer auf eine andere negative Zahl abbildet, gilt sicher für alle negativen Zahlen (und für die 0, die wieder auf 0 abgebildet wird):

f(x) = ⊥fürx ≤ 0

Betrachten wir also den Bereich der positiven ganzen Zahlen. Wenn die Berechnung überhaupt terminiert, kann als Ergebnis nur der Wert 1 herauskommen. Einige Beispielberechnungen bestätigen dies:

Allerdings wissen wir nicht, ob die Berechnung von f tatsächlich für alle positiven Zahlen terminiert! Es ist bisher unbewiesen, ob die folgende Äquivalenz gilt:

f(x) =if x > 0 then 1 else ⊥ fi

Dies zeigt, dass das Problem, ob man entscheiden kann, ob zwei Algorithmen äquivalent sind, d.h. dasselbe berechnen, durch die Existenz von unendlichen Berechnungen einen weiteren Schwierigkeitsgrad erhält – wenn wir im Beispiel die Terminierung gezeigt haben sollten, ist die Gleichheit der Ergebniswerte trivial.

Neben der Äquivalenz von Algorithmen wird uns später der Aufwand bei deren Berechnung intensiv beschäftigen. Der folgende Algorithmus zeigt, dass der Berechnungsaufwand bei relativ einfachen Algorithmenbeschreibungen förmlich explodieren kann.

Beispiel 3.15 Ackermannn-Funktion

Die Ackermann-Funktion ist durch folgenden Algorithmus definiert:

Die Werte der Ackermann-Funktion wachsen unglaublich schnell an:

Da die Berechnung dieser Werte durch Addieren der Zahl 1 erfolgt, wächst natürlich auch der Berechnungsaufwand extrem an. Die Ackermann-Funktion ist durch ihr ungewöhnlich schnelles Wachstum insbesondere relevant in Komplexitätsbetrachtungen von Algorithmen.

Genau genommen handelt es sich bei der dargestellten Funktion um eine vereinfachte Variante, die auch als Ackermann-Peter-Funktion bezeichnet wird.

Mit diesen Beispielen schließen wir vorerst die Behandlung applikativer Algorithmen ab. Wir werden die Grundkonzepte in späteren Kapiteln wiederholt aufgreifen, z.B. bei der Korrektheit von Algorithmen und der Umsetzung von rekursiven Funktionsdefinitionen in Java-Programme.

3.3Imperative Algorithmen

Imperative Algorithmen

Die imperativen Algorithmen bilden die verbreitetste Art, Algorithmen für Computer zu formulieren, da sie auf einem abstrakten Modell eines üblichen Rechners basieren. Wir hatten trotzdem zuerst applikative Algorithmen betrachtet, da diese mathematisch einfacher zu formalisieren und zu analysieren sind.

Imperative Algorithmen basieren auf den Konzepten Anweisung und Variable. Das imperative Paradigma ist sehr nah mit dem intuitiven Algorithmenbegriff aus Abschnitt 2.1 verwandt und wird durch viele Programmiersprachen wie C, Pascal, Fortran, COBOL oder auch von Java realisiert. Wir werden hier nur die Darstellung der Grundprinzipien betrachten.

3.3.1Grundlagen imperativer Algorithmen

Imperative Algorithmen basieren auf einem abstrakten Modell eines Rechners, der Werte speichern und diese dann schrittweise bearbeiten kann. Wir beginnen mit denjenigen Konzepten, die für die Speicherung von Werten notwendig sind.

Definition 3.3 Variablen

Variablen bilden die Speicherplätze für Werte:

• Eine Variable besteht aus einem Namen (z.B. X) und einem veränderlichen Wert. Jeder Variablen ist ein Typ zugeordnet.

Wertzuweisungen

• Ist t ein Term ohne Unbestimmte und w (t) sein Wert, dann bezeichnet man das Paar X :=t als Wertzuweisung. Ihre Bedeutung ist festgelegt durch:

Nach Ausführung von X :=t gilt: X = w(t).

Die folgenden Beispiele zeigen einige Wertzuweisungen:

Basierend auf Variablen, können wir die gespeicherten Werte in unserem abstrakten Rechner als Zustand des Rechners zusammenfassen.

Definition 3.4 Zustände

Die möglichen Zustände eines Rechners werden wie folgt festgelegt:

• Ist X = {X₁, X₂, …} eine Menge von Variablen(namen), von denen jede Werte aus der Wertemenge W annehmen kann (alle Variablen vom gleichen Typ), dann ist ein Zustand Z eine partielle Abbildung:

  Z : X → W (Zuordnung des momentanen Wertes).

Transformierte Zustände

• Ist Z : X → W ein Zustand und wählt man eine Variable X ∊ X und einen Wert w vom passenden Typ, so ist der transformierte Zustand Z_{X ← w} wie folgt definiert:

  

Alter und neuer Zustand

Nach der Definition der Zustände und der Wertzuweisungen müssen wir nun die atomaren und komplexen Anweisungen der Bearbeitung von Zuständen festlegen.

Anweisungen

Mit einer Anweisung α wird ein Zustand Z in einen (anderen) Zustand α(Z) überführt. Bei einer Wertzuweisung X := t ist der neue Zustand:

X := t(Z) = Z_X←w(t)

Die Notation X := t mit den doppelten Klammern ist die übliche Notation für eine Semantikfestlegung. Die Semantik einer Anweisung ist jeweils eine Funktion, die einen Zustand in einen neuen Zustand überführt.

Ausdrücke mit Variablen

Um Werte, die Variablen als Zwischenergebnisse zugewiesen wurden, später wiederverwenden zu können, muss man Werte aufrufen bzw. auslesen können.

Definition 3.5 Ausdrücke

Ausdrücke entsprechen im Wesentlichen den Termen einer applikativen Sprache, jedoch stehen an der Stelle von Unbekannten Variablen.

Die Auswertung von Termen mit Variablen ist zustandsabhängig. An der Stelle der Variablen wird ihr Wert im gegebenen Zustand gesetzt.

Beispiel 3.16 Zustand

Für einen gegebenen Term 2X + 1 ist der Wert im Zustand Z durch 2 · Z (X) + 1 festgelegt.

Der so bestimmte Wert eines Ausdrucks t(X₁, …, X_n) wird mit Z(t(X₁, …, X_n)) bezeichnet.

Beispiel 3.17 Berechnung eines Wertes

Das folgende Beispiel verdeutlicht die Berechnung des Wertes eines Terms in einem Zustand Z :

Z(2 · X + 1) = 2 · Z (X) + 1

Wertzuweisungen mit Variablen

Durch diese Festlegung kann man nun auch Wertzuweisungen verwenden, auf deren rechter Seite ein Ausdruck mit Variablen steht:

X := t(X₁, …, X_n)

Der transformierte Zustand ist wie folgt festgelegt:

X := t(X₁, …, X_n)(Z) = Z_{X ← Z(t(X1, …,Xn))}

Beispiel 3.18 Transformation von Anweisungen

Zur Verdeutlichung von Anweisungen zeigen wir die Transformationen für zwei elementare Anweisungen α₁ und α₂.

Bei der letzten Anweisung handelt es sich nicht um eine rekursive Gleichung für X – eine Zuweisung mit der Variablen X auf der rechten und linken Seite definiert keine Rekursion!

Die eingeführten Wertzuweisungen bilden die einzigen elementaren Anweisungen imperativer Algorithmen. Aus ihnen werden komplexe Anweisungen zusammengesetzt, die dann komplette Algorithmen definieren können.

3.3.2Komplexe Anweisungen

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 α₁ und α₂ Anweisungen, so ist α₁;α₂ auch eine Anweisung.

   Die Bedeutung der Sequenz ist durch die folgende Zustandstransformation festgelegt:

   α₁;α₂(Z) = α₂(α₁(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 α₁ und α₂ 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:

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.

Definition 3.6 Semantik imperativer Algorithmen

Die Bedeutung oder Semantik eines imperativen Algorithmus ist eine partielle Funktion, die wie folgt definiert ist:

Hierbei gelten die folgenden Abkürzungen und Konventionen:

Der Algorithmentext definiert also eine Transformation auf dem gesamten, durch die Eingaben initialisierten Zustand, aus dem als Bedeutung dann die Werte der Ausgabevariablen ausgelesen werden.

Man beachte, dass die Funktion Z nicht definiert ist, falls die Auswertung von nicht terminiert.

Kurz gefasst lassen sich imperative Algorithmen wie folgt charakterisieren:

Diese Konzepte sollen anhand der folgenden Beispiele verdeutlicht werden.

3.3.3Beispiele für imperative Algorithmen

Wir beginnen die Beispiele für imperative Algorithmen mit demselben Beispiel, das wir bei applikativen Algorithmen genutzt hatten.

Beispiel 3.19 Fakultätfunktion

Die Fakultätfunktion, definiert durch 0! = 1 und x! = x · (x − 1)! für x > 0, kann wie folgt realisiert werden:

In dieser Realisierung gilt:

Setzt man als Bedingung für die while-Schleife »X ≠ 0«, so erhält man als Semantik des modifizierten Algorithmus FAC 2 die folgende Funktion:

Wie auch bei applikativen Algorithmen sind die booleschen Tests wichtig zur Kontrolle des Definitionsbereichs.

Für Leser mit Programmiererfahrung ist der imperative Algorithmus sicherlich sofort verständlich und auch die Vorgehensweise des Algorithmus sofort klar. Er setzt die Problemstellung in ein Berechnungsverfahren um, indem eine Variable beginnend mit dem Eingabewert in einer Schleife jeweils um 1 erniedrigt wird und die dadurch erhaltenen Folge n, (n − 1), (n − 2) … 3, 2, 1 in einer zweiten Variablen aufmultipliziert wird.

Zustandstransformation

Die formale Semantik in Form der Zustandstransformation ist sicherlich nicht sofort einsichtig. Wir werden daher die Semantik imperativer Algorithmen anhand dieses einfachen Beispiels erläutern.

Die folgenden Ausführungen verdeutlichen anhand des imperativen Algorithmus FAC aus Beispiel 3.19 die Festlegungen der Definition der formalen Semantik. Gesucht ist hierbei das Ergebnis des Aufrufs FAC (3).

Wir verwenden die Abkürzung while β für die Zeile

Signatur

Die Signatur der Semantikfunktion ist wie folgt, da es je eine Eingabe- und Ausgabevariable gibt:

FAC : int → int

Die Funktion selbst ist durch Lesen des Wertes von Y im Endzustand Z definiert:

FAC(w) = Z(Y)

Der Endzustand Z ist dabei laut Definition definiert durch folgende Gleichung:

Z = α(Z₀)

wobei α die Folge aller Anweisungen des Algorithmus ist. Der initiale Zustand Z₀ ist definiert als Z₀ = (X = w, Y = ⊥). Zustände werden wir im Folgenden abkürzend ohne Variablennamen notieren, also Z₀ = (w, ⊥).

Auswertung von FAC(3)

Gesucht sei nun FAC(3). Dazu müssen wir den Endzustand Z bestimmen. Die Bestimmung von Z, die den Definitionen der einzelnen Bausteine imperativer Algorithmen folgt, ist in Abbildung 3–1 ausführlich dargestellt. Die doch etwas umfangreiche Ableitung der Erläuterungen zur Auswertung von FAC(3) in Abbildung 3–1 bedarf einiger Bemerkungen:

• Der Übergang von der 3. auf die 4. Zeile folgt der Definition der Sequenz, indem der Sequenzoperator in einen geschachtelten Funktionsaufruf umgesetzt wird.
• Nur in der 5. Zeile wurde eine Wertzuweisung formal umgesetzt, später sind sie einfach verkürzt direkt ausgerechnet.
• In der 7. Zeile haben wir die Originaldefinition der Iteration eingesetzt (nur mit dem Kürzel α′ statt α, da α bereits verwendet wurde). Im Beispiel gilt

  α′ = {Y := Y · X; X : X − 1}

• Das Z in der 7. und 8. Zeile steht für den Zustand (3,1) (in späteren Zeilen analog für den jeweils aktuellen Zustand).
• Bei diesem Beispiel sieht man Folgendes sehr deutlich: Die Ausführung einer While-Schleife erfolgt analog einer rekursiven Funktionsdefinition!

Damit gilt:

FAC(3) = Y(Z) = Y(X = 1, Y = 6) = 6

Abb. 3–1 Semantik imperativer Algorithmen am Beispiel

Die Umsetzung in einen imperativen Algorithmus entspricht in der Regel nicht der direkten applikativen Realisierung, da Zwischenergebnisse in Variablen vorgehalten werden können. Dieses Prinzip lässt sich sehr gut an folgendem Beispiel darstellen.

Beispiel 3.20 Fibonacci-Zahlen

Der folgende Algorithmus zeigt eine imperative Umsetzung der Fibonacci-Zahlen.

Die Bedeutung des Algorithmus, in der auch der Definitionsbereich der partiellen Funktion festgelegt wird, ist wie folgt:

Der Vergleich mit der applikativen Realisierung in Beispiel 3.7 auf Seite 64 zeigt die unterschiedliche Vorgehensweise: Zwei Variablen werden genutzt, um jeweils die zwei letzten berechneten Fibonacci-Zahlen zwischenzuspeichern. Diese Verfahren ist effizienter als der doppelte rekursive Aufruf des applikativen Algorithmus.

Die Frage der Effizienz von imperativen Algorithmen spielt auch im nächsten Beispiel eine Rolle, in dem ein weiterer »Klassiker« der Algorithmenbeispiele realisiert wird.

Beispiel 3.21 Größter gemeinsamer Teiler (euklidischer Algorithmus)

Ziel ist die Berechnung des größten gemeinsamen Teilers ggT. Die erste Version formulieren wir wie folgt:

Die Vorgehensweise verdeutlicht eine Beispielauswertung von ggT(19, 5), bei der wir für jeden Schleifendurchlauf die Werte der Variablen notieren:

Die Berechnung erfolgt im Wesentlichen durch die Subtraktion des jeweils kleineren Parameters.

Die Berechnung allein durch Subtraktion ist nicht sehr effizient, wenn man etwa an das Beispiel ggT(2, 1000) denkt. Wir entwickeln daher eine zweite Variante, die mittels der Division vorgeht.

Beispiel 3.22 ggT mittels Division

Die Berechnung des größten gemeinsamen Teilers in der zweiten Version mittels Division nutzt die ganzzahlige Division und die Modulofunktion zur Bestimmung des Restes bei der Division.

Auch hier betrachten wir einige Berechnungen, um die Vorgehensweise zu verdeutlichen:

Abschließend betrachten wir das Verhalten für negative X oder Y.

Intuitiv ist GGT2 effizienter als die erste Version – doch wie zeigt man eine derartige Eigenschaft?

Das Beispiel des ggT bereitet die spätere detaillierte Betrachtung von Effizienzeigenschaften vor. Der folgende Algorithmus spielt eine ähnliche Rolle bei Überlegungen zur Korrektheit.

Beispiel 3.23 Bestimmung der Semantik eines imperativen Algorithmus

Ein Beispiel soll verdeutlichen, dass die Bestimmung der Semantik eines imperativen Algorithmus nicht immer einfach ist. Beantwortet werden soll die Frage: Was berechnet der folgende Algorithmus?

Einige Berechnungen für XYZ helfen hier vielleicht weiter:

Aber auch die folgende Berechnung, die übrigens den Wert 2 ergibt, hilft uns hier nicht viel weiter, da man nicht direkt ein mathematisches Prinzip aus dem Algorithmus ablesen kann.

Der Algorithmus XYZ wird uns in Abschnitt 7.2 wieder begegnen. Dort wird auch die Bedeutung des Algorithmus verraten, die übrigens eine sehr einfache mathematische Eigenschaft ausdrückt.