Erarbeitung des Algorithmus
Entdecken lassendes Verfahren
Als erste Möglichkeit bietet es sich an, dass die Schülerinnen und Schüler den Algorithmus selbst entdecken. Die Aufgabe besteht dann darin, von einem intuitiven Tun zu einem systematischen Vorgehen zu kommen und dieses zu verbalisieren. Am Ende kann eine textuelle Beschreibung oder eine Beschreibung des Algorithmus im Pseudocode stehen. Eine Bewertung des gefundenen Algorithmus kann die Erarbeitung vertiefen. Die Arbeitsblätter enthalten dafür weiterführende Fragen.
Möchten Sie diese Variante anwenden, sollten die Schülerinnen und Schüler nach dem Einstiegsbeispiel, bei dem der Graph selbstständig modelliert wurde, einige weitere kleinere Beispielgraphen entweder "unplugged" auf einem Blatt Papier oder digital im Graphentester erhalten, um den gefundenen Algorithmus in anderen Situationen zu verifizieren.
Wichtig ist dabei, dass die Schülerinnen und Schüler eine systematische Ausführung des Algorithmus im Blick haben. Sie sollten den Algorithmus also mit Sätzen wie "Mache mit jedem Knoten...", "Mache mit jedem Nachbarn ...", "Nimm den Knoten/die Kante mit dem kleinsten Wert und mache ..." bilden. Anweisungen, die den ganzen Graphen im Blick haben sind unzulässig: "Gehe in Richtung des Zielknotens", "Nimm eine Farbe, die noch von keinem Knoten des Graphen benutzt wurde". Diese Sätze dürfen allenfalls als Zwischenstufen formuliert werden.
Die Verwendung des Graphentesters im Experimentiermodus unterstützt das Finden einer korrekten Beschreibung, da sich die ausführbaren Aktionen alle auch implementieren lassen. Ein Blick auf den ganzen Graphen ist unmöglich.
Nachdem der Algorithmus erarbeitet wurde, kann er anschließend implementiert oder analysiert werden. Für die Analyse des Algorithmus bietet es sich an, den Simulationsmodus des Graphentesters zu nutzen. Dann können auch größere Graphen untersucht werden oder schnell verschiedene Varianten eines Graphen getestet werden, um das Verhalten des Algorithmus bei Spezialfällen zu untersuchen.
Simulation des Algorithmus als Ausgangspunkt
Der Graphentester ermöglicht die Simulation fertiger Algorithmen und visualisiert dabei die Veränderung des Zustands des Graphen. Man kann zwischen einen Einzelschrittmodus (A) und einer fortlaufenden Ausführung (B) wählen. Mit dem Slider "Geschwindigkeit" kann die Ausführungsgeschwindigkeit verändert werden.
Bildquelle: Algorithmen-Simulationsfenster im Graphtester (eigenes Werk) von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 2_unterrichtsverlauf.odt
Bildquelle: Ablauf eines Algorithmus im Hilfefenster von ZPG Informatik [CC BY-NC-SA 3.0 DE], aus 2_unterrichtsverlauf.odt
Die zur Verfügung stehenden Algorithmen werden aus dem Unterverzeichnis "algorithmen" (fertige Algorithmen) und aus dem Hauptverzeichnis (selbst programmierte Algorithmen) des Graphentesters geladen. Der Name der Klasse muss dazu mit "GraphAlgo_" beginnen. Löscht man die class-Datei des Algorithmus, wird der Algorithmus nicht mehr zur Auswahl angeboten. Damit kann man als Lehrer festlegen, welche Algorithmen vorhanden sein sollen. Am Anfang ist es sinnvoll erst mal alle .class-Dateien zu löschen und die Schüler dann sukzessive einzelne Algorithmen kompilieren zu lassen oder sogar die Quelltexte erst später zur Verfügung zu stellen.
Die Schülerinnen und Schüler bekommen die Aufgabe, die Arbeitsweise des Algorithmus zu analysieren und zu versprachlichen. Eine Übertragung auf andere Graphen sichert das Verständnis des Algorithmus. Weiterführende Fragestellungen sichern die Erarbeitung zusätzlich.
Über das Menü Hilfe/Hilfefenster kann ein zusätzliches Fenster eingeblendet werden, in dem der Ablauf des Algorithmus protokolliert wird. Die kleinen Dreiecke erlauben das Ausblenden einzelner Abschnitte und erlauben damit, den Blick auf größere Strukturen (z.B. Schleifen über alle Kanten/Knoten) zu richten. Wird das Hilfefenster anzeigt, werden alle Zwischenzustände des Graphen gespeichert. Daher können einzelnen Schritte ausgewählt werden und der dazugehörige Zustand des Graphen angezeigt werden. Bei sehr aufwändigen Algorithmen sollte aber auf das Anzeigen des Hilfefensters verzichtet werden, da der benötige Speicherplatz enorm ansteigt.
Der Ablauf des Algorithmus ist eine gute Hilfe bei der Erstellung einer textuellen Beschreibung des Algorithmus oder einer Formulierung als Pseudocode. Als Lehrer kann man die angezeigten Texte leicht im Quelltext des Algorithmus verändern (siehe Beschreibung Implementierung).
Diese Herangehensweise ist nur mit Hilfe des Graphentesters möglich. Die Simulation im Graphentester ermöglicht außerdem die Bearbeitung größerer Graphen und damit realistischerer Situationen als dies auf einem Blatt Papier möglich wäre.
Eine anschließende Implementation des Algorithmus bietet sich bei diesem Vorgehen nicht an, da es unbefriedigend ist, ein schon fertig vorliegendes Programm erneut zu implementieren.
Unterrichtsverlauf: Herunterladen [odt][298 KB]
Weiter zu Implementierung von Graphen-Algorithmen