Programmieren

Wie entwerfen Sie eine Programm­schleife? Eine systematische Methode hierfür durchläuft die folgenden drei Schritte:

Die Programm­schleifen sind hier zunächst in der Programmier­sprache Java angegeben; zusätzlich ist auch jeweils noch eine Version in der Programmier­sprache Python angegeben.

Iterative Berechnungen

Ein wichtiges Anwendungs­gebiet für Programm­schleifen ist die iterative Berechnung von Funktions­werten.

Iterationsschema aufstellen

Ein Iterations­schema ist eine Tabelle, die für jede Iteration die Werte der beteiligten Variablen enthält. Für jede Variable, die während der Iteration ihren Wert ändert, ist eine Tabellen­zeile vorgesehen.

Iterationsgleichungen ableiten

Aus dem Iterations­schema leiten Sie Iterations­gleichungen ab. Für jede Variable des Iterations­schemas stellen Sie eine Iterations­gleichung auf. Darin geben Sie an, wie der Wert dieser Variablen ab der zweiten Spalte zu berechnen ist. Den Wert in der ersten Spalte legen Sie durch Initialisierung fest.

Regeln für die Aufstellung der Iterationsgleichungen

Die Iterations­gleichungen können Sie unmittelbar in ein Programm umsetzen, wenn Sie die folgenden Regeln einhalten.

1. Die Reihenfolge der Variablen im Iterations­schema bestimmt die Reihenfolge der Iterations­gleichungen
2. Die Iterations­gleichung für eine Variable v darf auf der rechten Seite nur folgende Variablen enthalten:
   1. Variablen w, die im Iterations­schema in derselben Spalte oberhalb von v stehen,
   2. Variablen w', die im Iterations­schema in der vorherigen Spalte auf gleicher Höhe oder unterhalb von v stehen,
   3. sonstige Variablen und Konstanten.
3. Alle Variablen v, die in der Form v' auf­treten, müssen initialisiert werden.

Anschaulich gesehen dürfen Sie für die Berechnung eines Wertes im Iterations­schema nur die darüber­liegenden Werte oder die direkt links daneben und darunter liegenden Werte des Iterations­schemas benutzen. So dürfen Sie für die Berechnung des Wertes an Position X nur Werte aus den mit x gekenn­zeichneten Feldern verwenden (und natürlich Werte von sonstigen Variablen und Konstanten).

Iterationsgleichungen in ein While-Programm umsetzen

Nachdem Sie die Iterations­gleichungen nach den obigen Regeln aufgestellt haben, setzen Sie diese direkt in eine While-Schleife um. Vor die While-Schleife fügen Sie noch die Initialisierung der beteiligten Variablen ein. Als Schleifen­bedingung wählen Sie eine Bedingung, die im Iterations­schema für alle Spalten vor der Spalte gilt, in der Sie das Ergebnis der Berechnung erwarten.

Wo sind die Striche geblieben? Aus der Iterations­gleichung i = i' +1 ist die Wert­zuweisung i=i+1 geworden. In der Wert­zuweisung wird auf der rechten Seite auf den alten Wert von i zugegriffen. Dieser Wert plus 1 wird dann der Variablen i als neuer Wert zugewiesen. In der Iterations­gleichung dagegen müssen alter und neuer Wert unter­schiedlich bezeichnet sein.

Schleifeninvariante aus dem Iterationsschema ermitteln

Für die formale Programm­verifikation benötigen Sie eine Schleifen­invariante; dies ist eine Bedingung, die beim Eintritt in den Schleifen­körper gilt und zum Schluss des Schleifen­körpers wiederum gilt.

Aus dem oben angegebenen Iterations­schema lesen Sie eine solche Schleifen­invariante P als Bedingung ab, die für alle Spalten vor und einschließ­lich der Spalte gilt, in der Sie das Ergebnis erwarten. Die Bedingung lautet:

P :  p = aⁱ  ∧  i ≤ n

Weiteres Beispiel

Berechnung von ln(2) durch alternierende Reihe

Die alternierende harmonische Reihe konvergiert (allerdings sehr langsam) gegen den Grenzwert ln(2).

ln(2)  =  1 – 1/2 + 1/3 – 1/4 + 1/5 – 1/6 + ...

Für die Berechnung der Reihe verwenden Sie folgendes Iterations­schema:

Die Variable n zählt die Iterationen, s enthält jeweils das nächste Reihenglied, v das zugehörige Vorzeichen und p die jeweils aufgelaufene Partialsumme.

Aus dem Iterations­schema gewinnen Sie folgende Iterations­gleichungen:

• n  =  n' + 1
• s  =  1/n
• v  =  –v'
• p  =  p' + v · s

Auf den rechten Seiten der Iterations­gleichungen benutzen Sie nur Variablen, die nach dem Schema von Bild 1 zulässig sind.

Die Iterations­gleichungen gelten ab der zweiten Spalte. Für die erste Spalte initialisieren Sie die Variablen wie folgt:

• n = 0
• v = -1
• p = 0

Die Iterations­gleichungen und Initialisierungen setzen Sie in folgendes While-Programm um. Die Schleife wird 1000-mal durchlaufen. Das Ergebnis ist der Wert von p nach Ende der Iteration.

Paralleles Iterationsschema

Das Iterations­schema in der Form, wie Sie es bisher kennen­gelernt haben, ist in sequenzielles Iterations­schema. Denn es ist gedacht für die sequenzielle Ausführung von Programm­schritten. So stehen etwa Variablen "mit Strich", deren Werte bereits durch neue Werte über­schrieben worden sind, nicht mehr zur Verfügung. Im Gegensatz dazu stehen in einem parallelen Iterations­schema alle Variablen "mit Strich", also die Werte aus der vorherigen Spalte, uneingeschränkt zur Verfügung. Es ist gedacht für Programmier­sprachen, in denen parallele Wert­zuweisungen möglich sind. In Python haben Sie diese Möglichkeit durch Tupel-Wert­zuweisungen.

Eine ent­sprechende Ver­anschaulichung zeigt das folgende Bild 2.

Anschaulich gesehen können Sie für die Berechnung eines Wertes an Position X im Iterations­schema alle in der linken Spalte daneben liegenden Werte x benutzen.

Das oben angegebene Iterations­schema für die Berechnung von aⁿ lässt sich mit den zugehörigen Iterations­gleichungen auch als paralleles Iterations­schema auf­fassen. Umgesetzt in ein Python-Programm­stück mit Tupel-Wert­zuweisung erhalten Sie

Vielfach ist es aber einfacher, sequenziell zu programmieren. In dem obigen sequenziellen Iterations­schema für die Berechnung von ln(2) beispiels­weise ermitteln Sie zunächst in aller Ruhe den Wert 1/n und das neue Vorzeichen v, um diese dann in der letzten Zeile des Programms zu verwenden.

Beispiel: Berechnung von ln(2) mit parallelem Iteratonsschema

Bei der Umsetzung eines rein parallelen Iterations­schemas erhalten Sie ein Python-Programm, bei dem der Schleifen­körper der While-Schleife nur aus einer einzigen Tupel-Wert­zuweisung besteht.

Für die oben angegebene Berechnung von ln(2) verwenden Sie das folgende parallele Iterations­schema:

Aus dem Iterations­schema gewinnen Sie folgende Iterations­gleichungen:

• n  =  n' + 1
• v  =  –v'
• p  =  p' + v' / n'

Beachten Sie, dass auf der rechten Seite der Iterations­gleichungen nur Variablen "mit Strich" vorkommen. Die Werte in der ersten Spalte des Iterations­schemas legen Sie wie gewohnt durch Initialisierung fest.

Die Iterations­gleichungen und Initialisierungen setzen Sie anschließend in ein Python-Programm mit einer einzigen Tupel-Wert­zuweisung im Schleifen­körper der While-Schleife um:

Python

Endrekursion in funktionalen Programmiersprachen

In funktionalen Programmier­sprachen wie etwa Haskell treten endrekursive Funktionen an die Stelle von Iterationen. Auch hier lassen sich mithilfe eines parallelen Iterations­schemas in systematischer Weise Iterations­gleichungen gewinnen, die unmittelbar in ent­sprechende endrekursive Funktions­definitionen umgesetzt werden können.

Das Iterations­schema für die Berechnung von aⁿ lässt sich beispiels­weise unmittelbar in folgendes Haskell-Programm überführen:

Die Funktion iterate bildet genau die Iterations­gleichungen nach. Der Aufruf von iterate zu Beginn enthält die Anfangswerte für i und p. Die Iteration endet, wenn der Spaltenindex i = n erreicht ist; dann wird als Ergebnis der Wert von p in dieser Spalte zurück­geliefert. Ansonsten ruft die Funktion iterate sich rekursiv selber auf, mit Parametern, die den rechten Seiten der Iterations­gleichungen entsprechen. Somit werden in den jeweiligen Aufrufen der Funktion iterate die Werte des Iterations­schemas von links nach rechts berechnet: iterate 0 1, iterate 1 a, iterate 2 a·a usw.

In diesem Fall lässt sich zwar aⁿ in direkter Weise mit einer end­rekursiven Funktion berechnen, aber mithilfe des oben angegebenen Schemas überführen Sie beliebige Iterations­gleichungen in eine endrekursive Funktion.

Aufgaben

Aufgabe 1:  (Berechnung der eulerschen Zahl e)

Die folgende Reihe konvergiert gegen die eulersche Zahl e = 2,71828...:

e  =   _{n = 0, ...,}   

1

n!

  =  

1

0!

  + 

1

1!

  + 

1

2!

  + 

1

3!

  + 

1

4!

  +  . . .

Stellen Sie ein Iterations­schema für die Berechnung von e auf. Leiten Sie daraus die zugehörigen Initialisierungen und Iterations­gleichungen ab und setzen Sie diese in eine While-Schleife um. Brechen Sie die While-Schleife ab, wenn der neu hinzu­gekommene Summand kleiner als 10^-14 ist.

Aufgabe 3:  (Berechnung von Binomial­koeffizienten)

Der Binomial­koeffizient ist definiert als

n

k

  =  

n!

k! · (n-k)!

Da der Bruch durch (n-k)! gekürzt werden kann, gilt

n

k

  =  

(n-k+1) · ... · n

1 · ... · k

Als Beispiel ist etwa

49

6

  =  

44 · 45 · 46 · 47 · 48 · 49

1· 2 · 3 · 4 · 5 · 6

  =  13983816

 

Stellen Sie ein Iterations­schema für die Berechnung von auf. Leiten Sie daraus die zugehörigen Initialisierungen und Iterations­gleichungen ab und setzen Sie diese in eine While-Schleife um.