Themen und Anwendungsbeispiele


Anhand konkreter Beispiele aus dem Bereich der Kombinatorischen Optimierung zeigen wir Anwendungsmöglichkeiten der Software Visage. Hier finden Sie kleine Anregungen und fertige Lerneinheiten zum Thema Graphenalgorithmen.
  • Minimale Aufspannende Bäme Minimale aufspannende Bäume sind in vielen Anwendungsgebieten der kombinatorischen Optimierung von Bedeutung, vor allem immer dann, wenn man in einem bestehenden Netzwerk vorhandene Knoten möglichst kostengünstig verbinden will. Anwendungsbeispiele sind der Ausbau von Leitungsnetzen für die Telekommunikation, die Planung von Straßennetzen oder das Chipdesign. Da bei der Lösung dieser Probleme besonders einfache Graphen, sogenannte Bäume, eine Rolle spielen, lassen sich entsprechende Fragestellungen bereits frühzeitig in der Sekundarstufe I untersuchen. Dabei können interessante Eigenschaften dieser Graphen von Schülern selbständig entdeckt werden. Die naheliegenden Lösungsalgorithmen sind so einfach, dass sie von den Schülern selbst entdeckt und mit nur geringen Programmierkenntnissen in Visage umgesetzt werden können.
  • Kürzeste Wege Unter dem Kürzeste-Wege-Problem versteht man die Fragestellung "Finde den besten Weg von S (Start) nach Z (Ziel)". Dabei stellt sich zuerst die Frage, was meint eigentlich "bester Weg"? Den längenmäßig kürzesten Weg? Oder den schnellsten? Vielleicht ja auch den bequemsten oder den schönsten?
  • Euler-Touren Das Königsberger Brückenproblem wurde von Leonhard Euler 1736 aufgestellt: Kann man einen Rundgang durch Königsberg so gestallten, dass jede Pregelbrücke dabei genau einmal überquert wird? Diese Fragestellung begründete das Gebiet der Graphentheorie.
  • Das Travelling Salesman Problem Das Problem des Handlungsreisenden, auch Travelling Salesman Problem genannt, ist eines der berühmtesten Probleme der kombinatorischen Optimierung - und gleichzeitig ist es eines der schwierigsten Probleme überhaupt. Effiziente Lösungsalgorithmen, die eine optimale Rundreise berechnen, sind nicht bekannt, und es wird wohl auch keine geben. Dennoch hat dieses Problem in vielen praktischen Anwendungen Bedeutung, nicht nur bei der Planung von Lieferfahrten eines Pizzaboten oder einer Sightseeing-Tour. Auch bei der optimalen Bohrung von Leiterplatten sind z.B. Rundtouren zu planen.
  • Färbungen Das bekannteste Problem auf diesem Gebiet ist wohl das "Vierfarbenproblem": Kann man jede beliebige Landkarte mit vier verschiedenen Farben färben? Dabei gelten folgende Regeln für das Färben: keine zwei Länder, die in mehr als einem Punkt aneinander grenzen, dürfen die gleiche Farbe bekommen. Ausserdem sind Exklaven ausgeschlossen. Die Vermutung, dass vier Farben zum Färben genügen, stellte Francis Guthrie schon 1852 auf, als er die Karte von England färben wollte. In den nächsten vierzig Jahren folgten fehlerhafte Beweisversuche dieser Vermutung, aber auch der Beweis, dass fünf Farben reichen. Erst 1976 gelang es Kenneth Appel und Wolfgang Haken den Vierfarbensatz zu beweisen. Allerdings auch nur mit massivem Rechnereinsatz.
  • weitere Beispiele Insbesondere durch die Möglichkeit, eigene Algorithmen in CindyScript zu programmieren, ist die Zahl der möglichen Themen, die in Visage dargestellt werden können, schier unbegrenzt. Einige weitere interessante Beispiel wollen wir hier präsentieren, um Ihnen Anregungen zu liefern, was sonst noch möglich ist.
  • Programmieren eigener Algorithmen Im Unterricht haben Ihre Schüler einen eigenen Algorithmus entworfen, den sie mal ausprobieren wollen? Oder Sie haben einen Algorithmus besprochen, an dessen Visualisierung wir noch nicht gedacht haben? Dann programmieren Sie ihn doch einfach selbst! Oder noch besser: Lassen Sie Ihre Schüler den Algorithmus programmieren! Wir verraten Ihn en, wie das geht.