Feuer löschen mit der Informatik? - Einführung in Graph- und Flussalgorithmen
In diesem InfoSphere-Modul lösen die SchülerInnen mit verschiedenen Algorithmen Graphprobleme. Eingebettet in eine spannende und alltagsbezogene Geschichte werden Navigationsprobleme und die Unterschiede der Breiten- und Tiefensuche erarbeitet. Zusätzlich können neue, eigene Algorithmen entwickelt und verglichen werden. Da die Grundlagen der Algorithmik vermittelt werden sollen, wird auch auf eine komplizierte und aufwändige Implementierung verzichtet und alle Algorithmen werden in übersichtlichen und leicht verständlichen Nassi-Shneiderman-Struktogrammen dargestellt. Besonders das Verständnis und die Arbeitsweise/Logik der Informatik sollen im Vordergrund stehen und das Interesse an diesem Teilgebiet der Informatik wecken.
Die SchülerInnen werden dazu auf die Reise als Feuerwehrmann geschickt und sollen in drei Hauptschritten einen Einsatz planen und Menschenleben retten.
Im ersten Schritt muss die Feuerwehr, unter Kommando der SchülerInnen, möglichst schnell und effektiv zu seinem Einsatzort fahren. Wie kann man den kürzesten Weg finden? Ist der kürzeste Weg immer der Schnellste? Wie kann man mit Algorithmen zuverlässig den besten Weg finden und damit das Haus schnellstmöglich löschen? Die SchülerInnen versuchen zunächst alleine eine Antwort auf diese Frage zu finden. Anschließend werden diese Ideen in Struktogramm systematisiert und professionelle Algorithmen vorgestellt, mit den SchülerInnen-Lösungen verglichen und angewendet.
Angekommen am brennenden Gebäude muss dieses nun noch gelöscht werden. Aber wie bekommt man ausreichend Wasser an den Brandherd? Welche Rohre werden benötigt und wo sind die Engstellen des Rohrsystems? Mithilfe des Max-Cut-Min-Flow wird ein Rohrsystem analysiert, verbessert und ausgebaut.
Während der Löscharbeiten muss eine Person aus dem brennenden Haus geborgen werden. Hierzu wird den SchülerInnen der Algorithmus für die Tiefen- als auch für die Breitensuche gegeben. Zunächst müssen diese im Pseudocode gelesen, umgesetzt und verstanden werden und in einem weiteren Schritt ein eigener Algorithmus entwickelt werden. Nach mehrmaliger Anwendung werden die Algorithmen verglichen. Hier sollen die Schüler erkennen, dass es nicht den „perfekten Algorithmus“ gibt, sondern je nach Anwendung differenziert werden muss.
Nachdem die Personen gerettet wurden und die SchülerInnen einen spannenden und lehrreichen Tag im Info-Sphere Schülerlabor hatten, werden alle Ergebnisse nochmals festgehalten und gesammelt. Zusätzlich ist klar geworden, dass Informatik sehr alltagsbezogen sein kann, wichtig für uns alle ist und keinesfalls trocken und abgefahren sein muss.