Kapitel2.1

Das Divide-and-Conquer-Prinzip geht davon aus, dass große Probleme gelöst werden können, indem sie in mehrere kleinere (möglichst disjunkte) Teilprobleme aufgeteilt werden. Aus den Lösungen der Teilprobleme kann dann die Lösung des großen Problems zusammengefügt werden. Es sind also drei Schritte auszuführen:

Zerlegung des Gesamtproblems in kleine Probleme, solange bis man direkt lösbare Primärprobleme erhält
Lösung dieser Teilprobleme
Zusammensetzung der Gesamtlösung aus den Teillösungen

Ein Verfahren, welches sich dieses Prinzips bedient, ist die Rekursion. Als Rekursion ganz allgemein kann man einen Vorgang verstehen, der sich auf sich selbst bezieht, bei dem also eine Wiederholung durch Schachtelung auftritt. Der Rekursionsalgorithmus bietet sich nun im Verständnis des Divide-and-Conquer-Prinzips immer dann an, wenn alle (oder zumindest mehrere) Teilprobleme von derselben Art wie das Ursprungsproblem sind, da dann auch die Lösung dieser Probleme auf dieselbe Art möglich ist. Es kann also eine Lösung "von innen heraus", d.h. vom letzten Teilproblem bis zum Ursprungsproblem erfolgen.
Für die Programmierung bedeutet das, Prozeduren bzw. Funktionen in sich selbst auszuführen. Voraussetzungen zur Erarbeitung der Rekursion im Informatikunterricht der Sekundarstufe II sind Kenntnisse und Fähigkeiten, die im Berreich Algorithmisches Problemlösen des Rahmenplanes aufgeführt sind. Insbesondere sollten die Schüler sicher mit Prozeduren und Funktionen und der Übergabe von Parametern umgehen können.
Zu erwähnen ist an dieser Stelle noch, dass den Schülern in der Abiturstufe das Rekursionsprinzip auch aus dem Mathematikunterricht bekannt ist, da hier in der Klassenstufe 11 im Stoffgebiet Folgen und Reihen mit rekursiven Bildungsvorschriften für Folgen gearbeitet wird.

Anfang

vor

zurück

2.1 Das HERON-Verfahren und seine Umsetzung als Rekursionsalgorithmus

2.1.1 Heron von Alexandria und das Verfahren zum Berechnen von Quadratwurzeln

Heron lebte um 100 n.Chr. wahrscheinlich in Alexandria, da er sich in seinem Werk "Dioptria" auf Beobachtungen der Sonnenfinsternis von 62 n.Chr. in Alexandria beruft. Er arbeitete vor allem auf den Gebieten der angewandten Geometrie und der Mechanik, beschäftigte sich ausführlich mit Flächeninhaltsberechnungen und schrieb über die Anfertigung und Benutzung von Messinstrumenten und Maschinen. In seinem Werk "Metrika" (Vermessungslehre in drei Bänden, fast unverändert erhalten) gibt er das nach ihm benannte Näherungsverfahren zur Berechnung von Quadratwurzeln an, welches Gegenstand des von uns ausgewählten Rekursionsbeispiels sein soll. Man weiß heute, dass dieses Verfahren auch schon den babylonischen Mathematikern um 2000 v.Chr. bekannt war. Es gibt in der Geschichte der Mathematik übrigens viele Anhaltspunkte dafür, daß griechische und hellenistische Mathematiker sehr stark auf babylonische Traditionen zurückgegriffen haben. In Erstaunen sollte uns und unsere Schüler versetzen, daß dieses Verfahren "nichts weiter" ist als das NEWTON-Verfahren (zur näherungsweise Bestimmung von Nullstellen) angewandt auf die Funktion f(x) = x² - a ,wir werden unter 2.1.3 näher darauf eingehen. Nun wurde aber bekanntlich die Differentialrechnung, auf der das NEWTON-Verfahren basiert, erst gegen Ende des 17.Jahrhunderts entwickelt. Heron hat die Zulässigkeit seines Näherungsverfahrens mit geometrischen Methoden nachgewiesen. Er gab an, dass die (nichtrationale) Wurzel einer Zahl a durch wiederholtes Anwenden der Formel
a_n+1 = (a_n+a/a_n)/2 mit hoher Genauigkeit angenähert werden kann. Als Startwert für das Verfahren setze man: a₀ := a

Anfang

vor

zurück

2.1.2 Die Umsetzung als Rekursionsalgorithmus und seine Programmierung in Turbo Pascal

Für die Umsetzung des HERON-Verfahrens in einem Rekursionsalgorithmus sind folgende Gedanken wichtig:

dieselbe Berechnung soll i-mal ausgeführt werden, allerdings mit sich ändernden Parameterwerten
i ist dabei beliebig vorzugeben oder vom Nutzer des Algorithmus selbst zu wählen
da jede folgende Berechnung mit dem Ergebnis der vorhergehenden ausgeführt wird, kann auf diesen Wert über den (fortlaufenden) Index der Ergebnisse zurückgegriffen werden
damit ist genau dieser Index, nämlich unser i, als Parameter für die Berechnung der geeignete
i wird durch den Algorihmus vom vorgegebenen Wert aus sozusagen heruntergezählt
dann werden die Berechnungen beim ersten i, welches größer als Null ist, begonnen und durch Selbstaufrufen (Reursion!) der Funktion oder Prozedur so lang wiederholt, bis das vorgegebenen i erreicht ist

In einem Turbo - Pascal - Programm sieht die Funktion zur rekursiven Ermittlung der Quadratwurzel folgendermaßen aus:

Function Wurzel(i:byte):extended;

Var w:extended;

Begin

If i=0 Then w := a

Else w := (Wurzel(i-1) + a / Wurzel(i-1)) / 2;

Wurzel := w

End;

vollständiges Programm
(TurboPascal 7.0 für DOS)

Anfang

vor

zurück

2.1.3 Fächer übergreifende Aspekte (Verbindung zum Mathematikunterricht)

Wenn man das HERON-Verfahren als Beispiel für den Rekursionsalgorithmus im Informatikunterricht wählt, kann man sowohl in der Sekundarstufe I als auch in der Sekundarstufe II auf Gegenstände des Mathematikunterrichts zurückgreifen.

Zur Sekundarstufe I:
Die Frage, wie man Quadratwurzeln ohne Taschenrechner berechnet, wird im Mathematikunterricht meist mit dem Verfahren mittels Intervallschachtelung beantwortet. Da dieses Verfahren für Schüler i.a. wenig attraktiv ist, kann man an dem schneller zum Ziel führenden HERON-Verfahren (ggf. im Informatikunterricht) Interesse wecken und an einem einfachen Beispiel das Prinzip der Rekursion erläutern. Der Einsatz von Rechentechnik ist dann natürlich nur unter dem Aspekt der Arbeitserleichterung zu sehen und zu demonstrieren. Die Programmierung des Algorithmus wird in der Sekundarstufe I i.a. noch zu hohe Anforderungen an die Schüler stellen.

Zur Sekundarstufe II:
Sobald die Schüler Kenntnisse in der Differentialrechnung besitzen und das NEWTON-Verfahren zur näherungsweisen Bestimmung von Nullstellen kennen gelernt haben, erlangt der historische Aspekt bei der Behandlung des HERON-Verfahrens besonderes Interesse. In wenigen Schritten kann (ggf. im Mathematikunterricht) die HERONsche Formel aus der NEWTONschen hergeleitet werden:

_n+1

An dieser Stelle kann die Leistung der babylonischen bzw. griechischen Mathematiker gewürdigt werden, die die Rekursionsformel ohne jegliche Kenntnisse der Differentialrechnung gefunden haben, bevor man sich dem Rekursionsalgorithmus genauer widmet und ein Programm dazu erarbeitet.

Anfang

vor

zurück

2.1.4 Das HERON-Verfahren - geeignet zur ERARBEITUNG der Rekursion im Unterricht der Sekundarstufe I/II?

Sicherlich wird man die Behandlung der Rekursion stets mit Beispielen aus dem Alltag beginnen:

Bilder, die sich selbst als Bild enthalten - u.s.w. bis das Auflösungsvermögen versagt;
die Matrjoscka (bei der man allerdings schnell zum Ende der Rekursion kommt);
Geschichten in Geschichten...;
ein Gegenstand zwischen parallelen Spiegeln;
...

... und nach diesen anschaulichen Alltagsbeispielen trockene Mathematik???

PRO

dass man mit einem derartigen Verfahren Wurzel "ohne Taschenrechner" ziehen kann, sollte in Erstaunen versetzen
die Formel ist leicht handhabbar (auch ohne Kenntnisse der höheren Mathematik) und führt schnell zu beachtlichen Werten
interessanter historischer Hintergrund
Fächer übergreifender Aspekt
die Programmierung (in Sek.II) erfordert nur geringen Aufwand

KONTRA

in mathemüden oder gar mathefeindlichen Kursen ist Abwehr zu erwarten

!!! Wir sind offen für weitere PRO UND KONTRA, gefragt ist Euere Meinung !!!

Anfang

zurück

2.1.5 Quellen

Ottmann, "Prinzipien des Algorithmenentwurfs" Freiburg 1997

Wussing, "Mathematik in der Antike" B.G.Teubner Verlagsgesellschaft, Leipzig

Baumann, "Informatik für die Sekundarstufe II", Band 2, Ernst Klett Schulbuchverlag

Anfang

Benutzer: gast • Besitzer: seminar • Zuletzt ge�ndert am: