Formulierung des Algorithmus

Die Schülerinnen und Schüler testen einen vorgegebenen Algorithmus an einem einfachen Hamilton-Pfad-Problem und erkennen, dass er für das Finden eines komplexeren Hamilton-Zyklus nicht geeignet ist. Daher muss nach anderen Methoden gesucht werden.

Vorstellung des Algorithmus

Im Lehrer-Schüler-Gespräch wird erarbeitet, dass man alle möglichen Kombinationen ausprobieren müsste, um zu beweisen, dass der zuvor untersuchte Graph (siehe Abb. 3) keinen Hamilton-Zyklus enthält. An dieser Stelle ist es schwierig, die Schülerinnen und Schüler selbst einen Algorithmus entwickeln zu lassen. Es ist daher sinnvoll, diesen vorzugeben und ihn von den Lernenden nachvollziehen zu lassen. Die Lehrerin oder der Lehrer stellt den folgenden Algorithmus auf dem Overhead-Projektor kurz vor, bevor ihn die Lernenden in Partnerarbeit nachvollziehen:

  • S1: Man erstellt sich alle möglichen Wege des Graphen G. (Vorgehen: Erzeuge alle Knoten-Permutationen und überprüfe, ob sie einen gültigen Weg darstellen.)
  • S2: Dann überprüft man jeweils, ob

    (a) jede Stadt genau einmal vorkommt. (Vorgehen: Überprüfe auf Anzahl der Städte und das Vorhandensein jeder Stadt.)

    (b) der Weg zum Ausgangsknoten zurückführt. (Vorgehen: Überprüfe, ob Start- und Endknoten verbunden sind.)

  • S3*: Sobald man einen Weg gefunden hat, der beide Eigenschaften hat, so stoppen wir und geben aus: "Es gibt *einen Rundweg, der jeden Knoten genau einmal besucht." Sonst gehe zu S4.
  • S4*: Falls alle Folgen abgearbeitet sind, so gebe aus: "Es gibt *keinen Rundweg, der jeden Knoten genau einmal besucht."

Arbeit mit dem Algorithmus

Mithilfe eines Arbeitsblattes vollziehen die Schülerinnen und Schüler den Algorithmus an einem kleinen Beispiel nach und entwickeln dabei ein Gefühl für den Begriff der Permutation. Die Fakultätsfunktion sollte in der anschließenden Besprechung durch die Lehrkraft eingeführt werden. Außerdem wird das "GünstigAir"-Problem unseres Geschäftsmannes Peter Müller mittels des Algorithmus gelöst, damit die Schülerinnen und Schüler erkennen, dass er korrekt arbeitet. Schließlich kann die Schwierigkeit des Findens eines Hamilton-Zyklus und die Ineffizienz des obigen Algorithmus' mithilfe des Programms "Graphenspiele" eindrucksvoll demonstriert werden: Versucht man dort Graphen mit dreißig oder mehr Knoten auf die Hamilton-Eigenschaften zu testen, kommt das Programm nicht über die Meldung hinaus, dass die Berechnung der Möglichkeiten noch andauert. Die Lernenden sollen nun erklären, warum die Berechnung so viel Zeit erfordert, und warum der Algorithmus praktisch nicht umgesetzt werden kann: Es ist einfach zu viel Arbeit, alle möglichen Kombinationen in S1 zu überprüfen!

Download

Die Eine-Million-Dollar-Frage

Nun wird dem Kurs mitgeteilt, dass es bisher nicht gelungen ist, einen effizienten Algorithmus für die Suche nach einem Hamilton-Zyklus zu finden. Die Wissenschaft geht davon aus, dass es ein einfaches Kriterium nicht gibt. Für besonderes Interesse dürfte bei den Jugendlichen der Hinweis sorgen, dass derjenige, der eine effiziente Charakterisierung findet oder beweist, dass es eine solche nicht gibt, eine Million Dollar erhält! Diese Prämie wurde zur Lösung der schwierigsten mathematischen Probleme unserer Zeit ausgesetzt. Diese Informationen können in eine spannende Geschichte verpackt werden - angefangen von David Hilberts dreiundzwanzig Problemen bis hin zu Andrew Wiles Beweis des letzten Satzes von Fermat.

    Suche nach anderen Möglichkeiten

    Im folgenden Unterrichtsgespräch wird der Kurs motiviert, sich nicht damit abzufinden, dass es nur Algorithmen gibt, die mit sehr viel Aufwand das Hamilton-Problem lösen könnten. Die Aufgabe besteht nun darin, Alternativen zu finden, wie man das Problem mit vertretbarem Aufwand lösen kann - und dazu soll das DNA-Computing behilflich sein.

    Einführung der Heuristik

    An dieser Stelle lässt sich sehr gut eine Heuristik für das Hamilton-Pfad-Problem einführen. Die Schwierigkeit in dem betrachteten Algorithmus liegt im ersten Schritt (S1). Die Lehrkraft soll mit den Schülerinnen und Schülern überlegen, welche Alternativen es zu einem Durchprobieren aller Möglichkeiten gibt. Sehr viele andere Wege gibt es leider nicht, aber zu diskutieren wäre der Versuch, in S1 eine zufällig ausgewählte Menge von möglichen Pfaden zu untersuchen. Ideal ist diese Methode allerdings nicht, denn leider kann es sein, dass die richtige Lösung nicht unter den zufällig gewählten Pfaden ist. Es besteht also die Möglichkeit, dass der geänderte Algorithmus nicht die richtige Lösung liefern würde (solche Algorithmen nennt man Heuristiken). Diese Heuristik ist aber für den DNA-Rechner wichtig. Denn man kann beim DNA-Algorithmus nicht garantieren, dass wirklich alle Möglichkeiten getestet werden. Auf Grund der sehr, sehr hohen Anzahl von erzeugten DNA-Pfaden ist die Wahrscheinlichkeit jedoch fast gleich Null, dass die gesuchte Lösung nicht dabei ist. Deswegen schränkt uns die Heuristik beim DNA-Computing auch nicht sehr ein.

    Frei nutzbares Material
    Die von Lehrer-Online angebotenen Materialien können frei für den Unterricht genutzt und an die eigene Zielgruppe angepasst werden.