Suche Home Einstellungen Anmelden Hilfe  


 
Standardalgorithmen
 
  
Anfang
vor
  

2. Das Divide-and-Conquer-Prinzip 

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 
 
an+1 = (an+a/an)/2
 
mit hoher Genauigkeit angenähert werden kann. Als Startwert für das Verfahren setze man:   a0 := 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: 

    NEWTON:   an+1 = an-f(an)/f '(an
          = an-(an²-a)/2an 
          = (2an²-an²+a)/2an 
          = (an+a/an)/2         :HERON 
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: