Vorstellung des Problems
Die Schülerinnen und Schüler lernen das Problem kennen, das sie mithilfe des DNA-Computing lösen sollen. Dabei geht es um die Planung einer Flugroute.
Definitionen
Einige der im Folgenden recht häufig verwendeten Begriffe werden hier vorab kurz erläutert:
Hamilton-Pfad
Ein Hamilton-Pfad ist ein Weg in einem Graphen, der jeden Knoten genau einmal besucht.Hamilton-Zyklus
Ein Hamilton-Zyklus ist ein Rundweg (endet also am Ausgangspunkt) in einem Graphen, der jeden Knoten genau einmal besucht.Euler-Tour
Eine Euler-Tour ist eine Runde durch einen Graphen, welche jede Kante genau einmal enthält.
Die Suche nach einem Hamilton-Pfad
Der Einstieg in die Stunde erfolgt über die Präsentation des folgenden Problems:
Der Geschäftsmann Peter Müller möchte gerne von seinem Firmensitz in Aachen aus seine Schwester in Berlin besuchen. Allerdings möchte er vorher noch bei seinen Kunden in Frankfurt und Köln vorbeischauen. Nun bietet die Fluggesellschaft "GünstigAir" für die Strecken Aachen-Köln, Köln-Aachen, Aachen-Berlin, Köln-Frankfurt, Köln-Berlin und Frankfurt-Berlin, Flüge für jeweils 20 € an. Herr Müller würde nun gerne diese günstigen Flüge nutzen. Wie kann er am besten fliegen?
Daraufhin wird ein Aufgabenblatt verteilt, das die Schülerinnen und Schüler in Partnerarbeit bearbeiten. Ihre Aufgabe ist es, einen Weg zur Lösung des Problems zu beschreiben und diesen so aufzubereiten, dass er an der Tafel anschaulich präsentiert werden kann.
-
6_problemstellung_flugroute.pdf
Beschreibung des Problems und Aufgabenstellung.
Vorschau Mappe Merkliste
Formalisierung
Bei der anschließenden Besprechung des Arbeitsblattes präsentieren zwei bis drei Gruppen ihre Ergebnisse an der Tafel (Zeichnung). Das Problem wird anschließend formalisiert:
Gesucht ist in der Schemazeichnung ein Weg, der von Aachen nach Berlin führt, mit Zwischenstopps in Köln und Frankfurt (also ein Hamilton-Pfad von Aachen nach Berlin).
Die Schülerinnen und Schüler notieren die Problemformulierung und zeichnen die Grafik ab, damit sie diese in den folgenden Stunden immer zur Hand haben. Für die Probleminstanz wurde ganz bewusst ein geringer Schwierigkeitsgrad gewählt. Um die Frage zu klären, ob man mit DNA überhaupt rechnen kann, sollte man mit einem einfachen Problem beginnen. Wenn sich dann zeigen sollte, dass das Problem schnell gelöst wird, können auch größere Instanzen bewältigt werden.
-
Schwierigkeit des Problems
Die Lernenden beschäftigen sich mit einem ungerichteten Hamilton-Pfad-Problem und einem Hamilton-Kreis-Problem.
-
Formulierung des Algorithmus
Die Schülerinnen und Schüler testen die Effizienz eines Algorithmus bei der Lösung von Hamilton-Pfad-Problemen.
-
Codierungen und Synthese von Lösungsmöglichkeiten
Für die Städte und Flüge werden "genetische" Codierungen entwickelt, mit denen der virtuelle DNA-Computer „gefüttert“ werden kann.
-
Herausfiltern der richtigen Lösung
Entwicklung und Simulation einer Strategie zur Selektion der gesuchten Lösung mit der Software „Hellics“.