Programmieren

Entwurf von Programmschleifen in Python

Wie entwirft man eine Programmschleife? Im Folgenden wird eine systematische Methode hierzu angegeben. Diese beruht auf der Erstellung eines Iterationsschemas, aus welchem Iterationsgleichungen abgeleitet werden. Diese wiederum lassen sich unmittelbar in eine Programmschleife umsetzen.

Hierbei besteht ein Unterschied zwischen einem sequentiellen und einem parallelen Iterationsschema. Die entsprechenden Iterationsgleichungen, die aus einem sequentiellen Iterationsschema abgeleitet werden, lassen sich unmittelbar in Programme von imperativen Programmiersprachen wie Java oder Visual Basic oder auch Python umsetzen.

Aber auch das parallele Iterationsschema eignet sich für Python, aufgrund der Möglichkeit, parallele Wertzuweisungen in Tupel-Schreibweise durchzuführen. Im Folgenden wird eine ganze Reihe von entsprechenden Python-Funktionen mit Iterationen in Form von While-Schleifen angegeben. Der Schleifenkörper einer solchen While-Schleifen besteht nur aus einer einzigen paralllen Wertzuweisung. Diese ergibt sich unmittelbar aus den Iterationsgleichungen, die aus einem parallelen Iterationsschema abgeleitet werden.

Die entsprechenden Programme stehen auch als Java-Version und als Haskell-Version zur Verfügung.

Ein Iterationsschema 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 Tabellenzeile vorgesehen.

Beispiel: Ein mögliches Iterationsschema für die Berechnung von aⁿ ist das folgende:

`i`	0	1	2	3	4	...	`n`
`p`	1	`a`	`a`·`a`	`a`·`a`·`a`	`a`·`a`·`a`·`a`	...	`a`ⁿ

Die Variable i dient zum Zählen der Iterationen, die Variable p enthält das jeweilige Zwischenergebnis nach jeder Iteration. Für die Variable a ist keine Zeile im Iterationsschema vorgesehen, da sie ihren Wert im Verlauf der Berechnung nicht ändert. Das Ergebnis der Berechnung ist der Wert von p in der Spalte, in der i = n ist.

Aus dem Iterationsschema werden Iterationsgleichungen abgeleitet. Für jede Variable des Iterationsschemas wird eine Iterationsgleichung aufgestellt. Diese gibt an, wie der Wert der Variablen in jeder Spalte des Schemas ab der zweiten Spalte zu berechnen ist. Die Werte in der ersten Spalte werden durch Initialisierung festgesetzt.

Beispiel: Die Iterationsgleichungen für das obige Iterationsschema lauten

i = i' + 1
p = p' · a

Hierbei bezeichnen Variablen "mit Strich" die Werte der entsprechenden Variablen in der vorherigen Spalte.

So ergibt sich der Wert von i in jeder Spalte als Wert von i in der vorherigen Spalte plus 1. Der Wert von p ergibt sich als Wert von p in der vorherigen Spalte mal a.

Die Iterationsgleichungen gelten in diesem Beispiel für alle Spalten des Iterationsschemas außer der ersten Spalte. Die Werte der ersten Spalte werden durch Initialisierung festgesetzt:

i = 0
p = 1

Ein Iterationsschema, das sich für den Entwurf von While-Schleifen in imperativen Programmiersprachen eignet, wird als sequentielles Iterationsschema bezeichnet. In einem sequentiellen Iterationsschema werden die Werte aller Variablen in einer Spalte sequentiell, also einer nach dem anderen von oben nach unten berechnet. Die sequentielle Berechnung hat zur Folge, dass sobald eine Variable v in der aktuellen Spalte einen neuen Wert erhalten hat, der alte Wert dieser Variablen, also deren Wert v' aus der vorherigen Spalte, nicht mehr zur Verfügung steht.

Definition: Ein Iterationsschema wird als sequentielles Iterationsschema bezeichnet, wenn sich daraus Iterationsgleichungen ableiten lassen, die für jede Variable v auf der rechten Seite nur folgende Variablen enthalten:

Variablen w, die im Iterationsschema in derselben Spalte oberhalb von v stehen,
Variablen w', die im Iterationsschema in der vorherigen Spalte auf gleicher Höhe oder unterhalb von v stehen,
sonstige Variablen und Konstanten.

Im Gegensatz zum sequentiellen Iterationsschema steht das parallele Iterationsschema. In einem parallelen Iterationsschema werden die Werte der Variablen in einer Spalte parallel berechnet. Demzufolge stehen für die Berechnung dieser Werte ausschließlich die Werte der Variablen aus der vorherigen Spalte zur Verfügung (dafür aber alle).

Definition: Ein Iterationsschema wird als paralleles Iterationsschema bezeichnet, wenn sich daraus Iterationsgleichungen ableiten lassen, die für jede Variable v auf der rechten Seite nur folgende Variablen enthalten:

Variablen w', die im Iterationsschema in der vorherigen Spalte stehen (ganz gleich in welcher Zeile),
sonstige Variablen und Konstanten .

Anschaulich gesehen können für die Berechnung des Wertes einer Variablen an Position X im Iterationsschema alle Werte herangezogen werden, die im Iterationsschema an den Positionen x stehen (Bild 1: sequentielles Iterationsschema (a), paralleles Iterationsschema (b)).

x

x

x X

x

x

x

x

x X

x

x

(a) (b)

Bild 1: Zugriff auf Werte an Position x: sequentielles Iterationsschema (a), paralleles Iterationsschema (b).

Ein Iterationsschema kann gleichzeitig ein sequentielles und ein paralleles Iterationsschema sein, nämlich dann, wenn für die Berechnung des Wertes einer Variablen an Position X nur Werte herangezogen werden, die in der vorherigen Spalte nicht oberhalb der Position X stehen, also an Positionen x aus dem Durchschnitt der Positionen x von Bild 1 a und 1 b.

Für die Entwicklung von iterativen Python-Programmen verwenden wir hier das parallele Iterationsschema. Den Wert einer Variablen v aus der vorherigen Spalte bezeichnen wir mit v'. In den Iterationsgleichungen, die wir in den folgenden Beispielen entwickeln, kommen auf der rechten Seite also nur Variablen "mit Strich" vor (jedenfalls wenn es sich um Variablen des Iterationsschemas und nicht um sonstige Variablen handelt).

Das Iterationsschema zur Berechnung von aⁿ aus dem obigen Beispiel ist ein paralleles Iterationsschema, denn in den Iterationsgleichungen kommen auf der rechten Seite nur Variablen "mit Strich" vor, es werden also nur Werte aus der vorherigen Spalte verwendet:

Iterationsgleichungen:
i = i' + 1
p = p' · a
Initialisierung:
i = 0
p = 1
Abbruchbedingung:
i = n

Das Iterationsschema lässt sich unmittelbar in folgendes Python-Programm überführen:

def power(a, n):
    i, p = 0, 1
    while i<n:
        i, p = i+1, p*a
    return p

Zu Beginn wird die Initialisierung der Variablen i und p vorgenommen. Im Schleifenkörper der While-Schleife werden in Form einer parallelen Wertzuweisung die Iterationsgleichungen ausgeführt. Die Iteration wird wiederholt, solange der Spaltenindex i < n ist. Als Ergebnis wird der Wert von p in der Spalte i = n zurückgeliefert.

Das folgende Beispiel berechnet die Fakultätsfunktion.

Beispiel: (Fakultätsfunktion n!)

In folgendem Iterationsschema ergibt sich das Ergebnis n! als Wert der Variablen p in der Spalte, in der i = n gilt.

`i`	0	1	2	3	...
`p`	1	1·1	1·1·2	1·1·2·3	...

Die Iterationsgleichungen und entsprechenden Initialisierungen für i und p lauten:

Iterationsgleichungen:
i = i' + 1
p = p'· (i'+1)
Initialisierung:
i = 0
p = 1
Abbruchbedingung:
i = n

Das Iterationsschema erfüllt die Bedingungen eines parallelen Iterationsschemas. Auf der rechten Seite der Iterationsgleichungen kommen nur Variablen "mit Strich" vor, es werden also nur Werte aus der vorherigen Spalte verwendet. Das Iterationsschema lässt sich unmittelbar in folgendes Python-Programm überführen:

def fakultaet(n):
    i, p = 0, 1
    while i<n:
        i, p = i+1, p*(i+1)
    return p

Beispiel: (n-te Fibonacci-Zahl)

Die Folge der Fibonacci-Zahlen f = 1, 1, 2, 3, 5, 8, 13, ... ist definiert durch die Rekursionsgleichungen

f₀ = 1

f₁ = 1

f_n = f_n-2 + f_n-1

Es stellt sich heraus, dass für die rekursive Berechnung der n-ten Fibonacci-Zahl mithilfe der obigen Rekursionsgleichungen mindestens f_n Schritte erforderlich sind, also exponentiell viele. Bei iterativer Berechnung sind dagegen höchstens n Schritte erforderlich, also nur linear viele.

Ein Iterationsschema für die Berechnung der Fibonacci-Zahlen ist das folgende:

`i`	0	1	2	3	4	5	6	...
`f`	1	1	2	3	5	8	13	...
`g`	0	1	1	2	3	5	8	...

Die Iterationsgleichungen und entsprechenden Initialisierungen für i, f und g lauten:

Iterationsgleichungen:
i = i' + 1
f = f ' + g'
g = f '
Initialisierung:
i = 0
f = 1
g = 0
Abbruchbedingung:
i = n

Dies führt zu folgendem Python-Programm, in ähnlicher Weise wie in den vorangegangenen Beispielen:

def fib(n):
    i, f, g = 0, 1, 0
    while i<n:
        i, f, g = i+1, f+g, f
    return f

Beispiel: (Binomialkoeffizienten)

Der Binomialkoeffizient n über k ist definiert als

n

k

n!

k! · (n-k)!

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

n

k

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

1 · ... · k

Als Beispiel ist etwa

49 · 48 · 47 · 46 · 45 · 44

1· 2 · 3 · 4 · 5 · 6

= 13983816

Ein Iterationsschema für dieses Beispiel ist das folgende:

`i`	49	48	47	46	45	44
`j`	1	2	3	4	5	6	7
`p`	1	· 49/1	· 48/2	· 47/3	· 46/4	· 45/5	· 44/6

Die Schreibweise beispielsweise · 49/1 bedeutet, dass der Wert in der vorherigen Spalte dieser Zeile mit 49 multipliziert und dann durch 1 geteilt wird.

Das Ergebnis n über k ist der Wert der Variablen p in der Spalte, in der j = k+1 gilt.

Iterationsgleichungen:
i = i' – 1
j = j' + 1
p = p' · i' div j'
Initialisierung:
i = n
j = 1
p = 1
Abbruchbedingung:
j = k + 1

Die Iterationsgleichungen lassen sich unmittelbar in ein entsprechendes iteratives Python-Programm umsetzen:

def binom(n, k):
    i, j, p = n, 1, 1
    while j<k+1:
        i, j, p = i-1, j+1, p*i//j
    return p

Bemerkung: Das Progamm lässt sich noch optimieren, indem vor die While-Schleife die Anweisung k=min(k, n-k) gesetzt wird , denn es gilt, dass binom(n, k) gleich binom(n, n-k) ist.

Beispiel: (Sinusfunktion)

Ein etwas komplizierteres Beispiel ist die Berechnung der Sinusfunktion nach folgender Formel:

sin(x) = Summe

_{n = 0, ...,} (-1)ⁿ

x²ⁿ⁺¹

(2n+1)!

Das entsprechende Iterationsschema enthält Variablen für den Index i = 2n+1, für den jeweiligen Summanden s und das zugehörige Vorzeichen v sowie für die jeweilige Partialsumme p.

`i`	1	3	5	7	...
`v`	1	-1	1	-1	...
`s`	`x`¹/1!	`x`³/3!	`x`⁵/5!	`x`⁷/7!	...
`p`	0	+ `s'`	- `s'`	+ `s'`	...

Die Schreibweise + s' bedeutet, dass s' zum Wert in der vorherigen Spalte dieser Zeile addiert wird.

Iterationsgleichungen:
i = i' + 2
v = -v'
s = s' · x² / (i'+1) / (i'+2)
p = p' + v' · s'
Initialisierung:
i = 1
v = 1
s = x
p = 0
Abbruchbedingung:
s < 10^-14

Dies führt zu folgendem Python-Programm:

def sinus(x):
    i, v, s, p = 1, 1, x, 0
    while s>=1e-14:
        i, v, s, p = i+2, -v, s*x*x/(i+1)/(i+2), p+v*s
    return p

Die Iteration wird beendet, sobald der neu hinzukommende Summand s kleiner als 10^-14 geworden ist.

Aufgabe 1: (Berechnung von π/4)

Die Leibniz-Reihe konvergiert (allerdings sehr langsam) gegen den Grenzwert π/4:

π/4 = 1 – 1/3 + 1/5 – 1/7 + 1/9 – 1/11 + 1/13 – ...

Stellen Sie ein paralleles Iterationsschema für die Berechnung von π/4 auf. Leiten Sie daraus die zugehörigen Iterationsgleichungen und Initialisierungen ab und setzen Sie diese in ein Python-Programm um. Brechen Sie die Berechnung ab, wenn der neu hinzukommende Summand betragsmäßig kleiner als 10^-4 ist.

Aufgabe 2: (Berechnung von ln(2))

Eine schnell konvergierende Reihe zur Berechnung des natürlichen Logarithmus von 2 ist folgende:

ln(2) =

1 · 3¹

3 · 3³

5 · 3⁵

+ ...

Entwerfen Sie ein paralleles Iterationsschema für die Berechnung. Leiten Sie daraus die Iterationsgleichungen ab. Programmieren Sie ein entsprechendes Python-Programm zur Berechnung von ln(2).

[up]

H.W. Lang mail@hwlang.de Impressum Datenschutz
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden

Programmieren

Entwurf von Programmschleifen in Python

Iterationsschema

Iterationsgleichungen

Sequentielles und paralleles Iterationsschema

Anwendung

Weitere Beispiele

Aufgaben