Programmieren

Entwurf von Programmschleifen in Python

 aufwärts

Wie entwirft man eine Programm­schleife? Im Folgenden wird eine systematische Methode hierzu angegeben. Diese beruht auf der Erstellung eines Iterations­schemas, aus welchem Iterations­gleichungen abgeleitet werden. Diese wiederum lassen sich unmittelbar in eine Programm­schleife umsetzen.

Hierbei besteht ein Unterschied zwischen einem sequentiellen und einem parallelen Iterations­schema. Die ent­sprechenden Iterations­gleichungen, die aus einem sequentiellen Iterations­schema abgeleitet werden, lassen sich unmittelbar in Programme von imperativen Programmier­sprachen wie Java oder Visual Basic oder auch Python umsetzen.

Aber auch das parallele Iterations­schema eignet sich für Python, aufgrund der Möglichkeit, parallele Wert­zuweisungen in Tupel-Schreibweise durch­zuführen. Im Folgenden wird eine ganze Reihe von ent­sprechenden Python-Funktionen mit Iterationen in Form von While-Schleifen angegeben. Der Schleifen­körper einer solchen While-Schleifen besteht nur aus einer einzigen paralllen Wert­zuweisung. Diese ergibt sich unmittelbar aus den Iterations­gleichungen, die aus einem parallelen Iterations­schema abgeleitet werden.

Die ent­sprechenden Programme stehen auch als Java-Version, als Visual-Basic-Version und als Haskell-Version zur Verfügung.

Iterationsschema

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.

Beispiel:  Ein mögliches Iterations­schema für die Berechnung von an ist das folgende:

i01234...n
p1aa·aa·a·aa·a·a·a...an

Die Variable i dient zum Zählen der Iterationen, die Variable p enthält das jeweilige Zwischen­ergebnis nach jeder Iteration. Für die Variable a ist keine Zeile im Iterations­schema 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.

Iterationsgleichungen

Aus dem Iterations­schema werden Iterations­gleichungen abgeleitet. Für jede Variable des Iterations­schemas wird eine Iterations­gleichung 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 Iterations­gleichungen für das obige Iterations­schema lauten

Hierbei bezeichnen Variablen "mit Strich" die Werte der ent­sprechenden 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 Iterations­gleichungen gelten in diesem Beispiel für alle Spalten des Iterations­schemas außer der ersten Spalte. Die Werte der ersten Spalte werden durch Initialisierung festgesetzt:

Sequentielles und paralleles Iterationsschema

Ein Iterations­schema, das sich für den Entwurf von While-Schleifen in imperativen Programmier­sprachen eignet, wird als sequentielles Iterations­schema bezeichnet. In einem sequentiellen Iterations­schema 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 Iterations­schema wird als sequentielles Iterations­schema bezeichnet, wenn sich daraus Iterations­gleichungen ableiten lassen, die für jede Variable v auf der rechten Seite nur folgende Variablen enthalten:

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

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

 

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

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

Ein Iterations­schema kann gleichzeitig ein sequentielles und ein paralleles Iterations­schema 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 Iterations­schema. Den Wert einer Variablen v aus der vorherigen Spalte bezeichnen wir mit v'. In den Iterations­gleichungen, 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 Iterations­schemas und nicht um sonstige Variablen handelt).

Anwendung

Das Iterations­schema zur Berechnung von an aus dem obigen Beispiel ist ein paralleles Iterations­schema, denn in den Iterations­gleichungen kommen auf der rechten Seite nur Variablen "mit Strich" vor, es werden also nur Werte aus der vorherigen Spalte verwendet:

Das Iterations­schema 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 Schleifen­körper der While-Schleife werden in Form einer parallelen Wert­zuweisung die Iterations­gleichungen 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ück­geliefert.

Weitere Beispiele

Das folgende Beispiel berechnet die Fakultäts­funktion.

Beispiel:  (Fakultäts­funktion n!)

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

i0123...
p11·11·1·21·1·2·3...

 

Die Iterations­gleichungen und ent­sprechenden Initialisierungen für i und p lauten:

 

Das Iterations­schema erfüllt die Bedingungen eines parallelen Iterations­schemas. Auf der rechten Seite der Iterations­gleichungen kommen nur Variablen "mit Strich" vor, es werden also nur Werte aus der vorherigen Spalte verwendet. Das Iterations­schema 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

 

Zu Beginn wird die Initialisierung der Variablen i und p vorgenommen. Im Schleifen­körper der While-Schleife werden in Form einer parallelen Wert­zuweisung die Iterations­gleichungen 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ück­geliefert.

 

Beispiel:  (n-te Fibonacci-Zahl)

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

f0  =  1

f1  =  1

fn  =  fn-2 + fn-1

 

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

 

Ein Iterations­schema für die Berechnung der Fibonacci-Zahlen ist das folgende:

i0123456...
f11235813...
g0112358...

 

Die Iterations­gleichungen und ent­sprechenden Initialisierungen für i, f und g lauten:

 

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

 

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

 

 

Beispiel:  (Binomial­koeffizienten)

Der Binomial­koeffizient n über k ist definiert als

Binomialkoeffizient Klammer auf nBinomialkoeffizient Klammer zu
 k
  =  
n!
k! · (n-k)!

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

Binomialkoeffizient Klammer auf nBinomialkoeffizient Klammer zu
 k
  =  
n · ... · (n-k+1)
1 · ... · k

Als Beispiel ist etwa

Binomialkoeffizient Klammer auf49Binomialkoeffizient Klammer zu
6
  =  
49 · 48 · 47 · 46 · 45 · 44
1· 2 · 3 · 4 · 5 · 6
  =  13983816

 

Ein Iterations­schema für dieses Beispiel ist das folgende:

i494847464544 
j1234567
p1· 49/1· 48/2· 47/3· 46/4· 45/5· 44/6

 

Die Schreibweise beispiels­weise · 49/1 bedeutet, dass der Wert in der vorherigen Spalte dieser Zeile mit 49 multi­pliziert 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.

 

 

Die Iterations­gleichungen lassen sich unmittelbar in ein ent­sprechendes 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:  (Sinus­funktion)

Ein etwas komplizierteres Beispiel ist die Berechnung der Sinus­funktion nach folgender Formel:

sin(x)  =   Summe n = 0, ..., unendlich  (-1)n
x2n+1
(2n+1)!

 

Das ent­sprechende Iterations­schema 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.

 

i1357...
v1-11-1...
sx1/1!x3/3!x5/5!x7/7!...
p0+ s'- s'+ s'...

 

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

 

 

 

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 hinzu­kommende Summand s kleiner als 10-14 geworden ist.

 

Aufgaben

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 Iterations­schema für die Berechnung von π/4 auf. Leiten Sie daraus die zugehörigen Iterations­gleichungen und Initialisierungen ab und setzen Sie diese in ein Python-Programm um. Brechen Sie die Berechnung ab, wenn der neu hinzu­kommende Summand betragsmäßig kleiner als 10-4 ist.

 

Aufgabe 2:  (Berechnung von ln(2))

Eine schnell kon­vergierende Reihe zur Berechnung des natürlichen Logarithmus von 2 ist folgende:

ln(2)  =  
2
1 · 31
  +  
2
3 · 33
  +  
2
5 · 35
  +   ...

Entwerfen Sie ein paralleles Iterations­schema für die Berechnung. Leiten Sie daraus die Iterations­gleichungen ab. Programmieren Sie ein ent­sprechendes Python-Programm zur Berechnung von ln(2).

 

 

 

up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©  
Valid HTML 4.01 Transitional

Hochschule Flensburg
Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik