Arbeitsblatt: Lehrmittel zum Informatik-Biber

Informatik – Biber Lehrmittel für die informatische Bildung an der Sekundarstufe Lehrpersonenkommentar Inhaltsverzeichnis Optimieren – Wie finde ich die beste Rundreise? 3 Ausgangskompetenz 3 Umsetzungsvorschläge (bis 4 Lektionen) 4 Bildungsrelevanz des Themas gemäss Lehrplan 21 (aktuell diskutierte Vorarbeiten) Kompetenzbereiche des Fachbereichs „Mathematik Kompetenzbereiche des Fachbereichs „Natur, Mensch, Gesellschaft: Hintergrundwissen zum Traveling Salesman Problem Umsetzungshilfen 4 4 4 4 6 Lernenden-Perspektiven Experiment 1 „Wer findet die beste Rundreise? Experiment 2: „Die kürzeste Rundreise auf dem Pausenplatz Informatik-Biberaufgaben zum Thema Optimierung Mögliche Vertiefungen Mögliche Lösungen 6 6 7 7 7 9 Reflexion Lernfilm: „Beste Rundreise durch sieben Städte Experiment 1: „Wer findet die beste Rundreise? Experiment 2: „Die kürzeste Rundreise auf dem Pausenplatz informatik-biber.ch 9 10 10 2 Optimieren – Wie finde ich die beste Rundreise? Ausgangskompetenz: Strategien und Methoden zur Lösung von Optimierungsproblemen kennen und diese an konkreten Beispielen ausführen können, sowie die Komplexität des Traveling Salesman Problem kennen. informatik-biber.ch 3 Umsetzungsvorschläge (bis 4 Lektionen) Lernenden-Perspektiven Experiment 1 Wie finde ich eine optimale Rundreise durch sieben Schweizer Städte? Experiment 2 Suche nach der kürzesten Rundreise auf dem Pausenplatz. In Halbklassen oder im Klassenverband verschiedene Strategien zur Optimierung eines kürzesten Rundwegs erproben. Lernende laufen eine von Ihnen gewählte Rundreise auf dem Pausenplatz ab und protokollieren die einzelnen angelaufenen Orte. Biberaufgabe Verschiedene Aufgaben zum Thema Optimierung selbständig lösen. Transfer Mögliche Lösungen von Optimierungsaufgaben an konkreten Beispielen erproben. Es gibt Optimierungsprobleme welche sich nicht mit „gierigen Strategien lösen lassen, weil auch die schnellsten Computer zu viel Zeit brauchen um alle Lösungsmöglichkeiten zu überprüfen. Für das Lösen solcher Probleme helfen spezielle, heuristische Lösungsverfahren („schlaue Software), welche von Informatikerinnen und Informatikern entwickelt werden. Mögliche Vertiefung Zu Optimierungsproblemen und im Speziellen zum Traveling Salesman Problem finden sich verschiedene interaktive Applets und Erläuterungen im Internet. Interessierte Schülerinnen und Schüler können mit diesen Informationen selbständig weitere Experimente ausführen. Selbständiges Experimentieren mit Aufgabenblättern zum Traveling Salesman Problem. Fragestellung: Wie findet man eine optimale Rundreise? Die Lernenden zeichnen Rundreisen ein, messen diese und vergleichen sie miteinander. Bildungsrelevanz des Themas gemäss Lehrplan 21 (aktuell diskutierte Vorarbeiten) Nationale Grundkompetenzen für Themen der Informatik fehlen. Kompetenzbereiche des Fachbereichs „Mathematik Die Schülerinnen und Schüler lernen Erforschen und Argumentieren. Sie können sich auf unbekannte Zahlenräume und Muster einlassen, Beispiele zu Gesetzmässigkeiten suchen, die erlangten Ergebnisse beschreiben, überprüfen, hinterfragen, interpretieren und begründen. Kompetenzbereiche des Fachbereichs „Natur, Mensch, Gesellschaft: • Die Schülerinnen und Schüler können sich im Raum orientieren. • Energiefrage (Transport), sparsamer Umgang mit Ressourcen informatik-biber.ch 4 Hintergrundwissen zum Traveling Salesman Problem Navigationssysteme oder Routenplaner sollen nicht nur irgendeine mögliche Strecke vom Start zum Ziel berechnen, sondern den kürzesten (optimalen) Weg berechnen. Die Suche nach dem kürzesten Weg oder nach einer optimalen Rundreise beschäftigt Informatikerinnen und Informatiker seit Jahrzehnten. Routenplaner können heutzutage diese Aufgabe lösen, weil Forscherinnen und Forscher effiziente Algorithmen („schlaue Software) gefunden haben und die heutigen Informationssysteme zudem schnell genug sind, um Millionen von Berechnungen in kurzer Zeit auszuführen. Die Frage nach dem kürzesten Weg wie auch die Frage nach einer optimalen Rundreise gehören zur Klasse der Optimierungsprobleme. „Mit möglichst wenig Mitteln möglichst viel erreichen. ist das grundlegende Ziel bei der Lösung eines „Optimierungsproblems. Computerprogramme, welche zur Lösung benutzt werden, verwenden manchmal „gierige (Englisch: „greedy) Strategien: Diese untersuchen alle verschiedenen Möglichkeiten und wählen die beste, gefundene Lösung aus. Beim Traveling Salesman Problem führt eine „gierige Strategie nur für wenige Städte zum Ziel. Bei einer Rundreise durch 20 Städte müsste ein heutiger Computer mehr als zwanzig Jahre rechnen um alle Lösungsmöglichkeiten miteinander zu vergleichen. Für das Finden von optimalen Rundreisen mit mehr als 15 Städten werden so genannte heuristische Verfahren („schlaue Software) eingesetzt. Diese suchen nicht die beste, sondern nur eine sehr gute Lösung, welche in der Praxis genügt. informatik-biber.ch 5 Umsetzungshilfen Lernenden-Perspektiven In Gruppen oder im Plenum wird der Lernfilm „Wie finde ich die beste Rundreise? geschaut. Die Lehrperson fragt, was die Lernenden erstaunt hat. Anschliessend diskutieren die Lernenden in Kleingruppen Fragen, welche sich nach dem Betrachten des Lernfilms ergeben: • Welche ist die beste Rundreise durch sieben Schweizer Städte? • Welche Kriterien bezüglich eines optimalen Wegs können beachtet werden? • Wie viele mögliche Wege gibt es durch 4, 5 oder 6 Städte? Experiment 1 „Wer findet die beste Rundreise? Eine Gruppe Schülerinnen und Schüler markiert auf einer Europa- oder Schweizerkarte zehn Städte (mit Stecknadel oder Magneten), welche sie besuchen möchte. Es soll gemeinsam eine möglichst kurze Rundreise mit Bus oder Bahn auf einer Karte geplant werden. Auf Aufgabenblättern (Städtekarten in der Beilage) sind auf einem quadratischen (14 14)-Gitter an verschiedenen Gitterpunkten Städte als Kreise eingezeichnet und mit Buchstaben gekennzeichnet. Die Städtekarten sind in drei Kategorien (einfach, mittel, schwierig) unterteilt. Die Lernenden sollen in Kleingruppen eine möglichst kurze Rundreise suchen und diese auf ihrem Arbeitsblatt einzeichnen. Es dürfen direkte Strecken (Luftlinie) zwischen zwei Städten gewählt werden. Zur Überprüfung der besten Lösung können verschiedene Rundreisen mit Schnur oder Faden abgemessen und verglichen werden. Als zusätzliche Fragestellung kann untersucht werden, welche optimalen Rundreisen sich ergeben, wenn nur noch Wege entlang der Gitterlinien erlaubt sind. Schülerinnen und Schüler können im weiteren untersuchen, ob die vom Computer vorgeschlagenen Musterlösungen immer die besten sind und welche konkrete Rundreise durch zehn oder mehr vorgegebenen Städte ein Routenplaner vorschlägt (z.B. gebweb.net/optimap). informatik-biber.ch 6 Experiment 2: „Die kürzeste Rundreise auf dem Pausenplatz Eine optimale Rundreise durch zehn bis zwanzig Städte (wie bei Experiment 1) zu finden, kann auf dem Papier gelingen. Bei einem Wechsel der Perspektive wenn man inmitten der anzulaufenden Orte steht erhöht sich die Herausforderung. Die Lernenden haben in diesem Experiment eine lokale Sichtweise und sehen nur die nächsten möglichen Orte. Eine globale Übersicht fehlt ihnen. Sie müssen nun anhand von lokalen Informationen eine möglichst gute globale Lösung finden. Algorithmen in der Informatik versuchen mit Hilfe von lokalen Informationen globale Lösungen zu finden. Ein berühmtes Beispiel dafür ist der Algorithmus von Dijkstra. Link: Zur Durchführung wird ein Pausenplatz oder ein grosses Feld benötigt, auf welchem Markierungen im gegenseitigen Abstand von mehr als 30 Meter platziert werden können. Jede Markierung sollte mit einem Label (z.B. Buchstaben) beschriftet sein. Eine erste Gruppe legt die Markierungen so unregelmässig wie möglich aus. Die zweite Gruppe erhält mehrere Versuche (z.B. immer zwei Schülerinnen und Schüler zusammen) um eine kürzeste Rundreise zu finden. Die erste Gruppe protokolliert die Versuche und stellt sicher, dass alle Markierungen genau einmal besucht werden. Der zurück gelegte Weg der einzelnen Rundgänge kann mit einem Messrad, Schrittzähler oder GPS bestimmt werden. Nach einem ersten Durchgang tauschen die Gruppen ihre Rollen. Informatik-Biberaufgaben zum Thema Optimierung In vielen Lebenssituationen kann durch das Wählen eines optimalen Weges Geld, Schweiss oder Zeit gespart werden. Mit sieben Aufgabenblättern, welche aus den Informatik-Biberwettbewerben von 2007 bis 2011 stammen, können die Lernenden verwandte Optimierungsprobleme mit unterschiedlichen Niveaus an konkreten Beispielen lösen. Die Arbeitsblätter können als Einzelarbeit oder in kleinen Gruppen gelöst werden. Die gefunden Lösungen können in der Klasse diskutiert oder selbständig mit den Musterlösungen verglichen werden. Weitere Informationen zum Informatik-Biber Wettbewerb finden Sie auf der Webseite informatik-biber.ch 7 Mögliche Vertiefungen Mit der Frage nach optimalen Rundreise haben sich Forschende aus den Bereichen Informatik, Mathematik, Architektur und den Ingenieurswissenschaften in den letzten 100 intensiv befasst. So konnte zum Beispiel 1954 eine optimale Rundreise durch 49 Städte der USA gefunden werden. 1977 gelang es einem deutschen Wissenschaftler eine kürzeste Rundreise durch 120 deutsche Städte zu finden und im Jahr 2004 konnte eine kürzeste Rundreise durch 24978 Dörfer von Schweden gefunden werden. Momentan läuft ein Wettbewerb, bei welchem eine kürzeste Rundreise durch alle Ortschaften der Welt gesucht wird. Diese und weitere Informationen zum Traveling Salesman Problem finden Sie auf der Webseite ca/tsp/index.html Mit einem interaktiven Applet auf der Seite kann versucht werden eine optimale Rundreise durch 10 Städte zu finden. Ein weiteres Applet auf der Webseite zeigt, wie ein Algorithmus („schlaue Software) eine Rundreise durch 99 Ortschaften schrittweise (nach jedem Tastendruck) verbessert. Neben der Frage nach dem kürzesten oder schnellsten Weg kann als erweiterte Fragestellung untersucht werden, welche Strassen oder Verbindungen minimal notwendig sind, um alle Ortschaften zu erreichen. Die neunte Aktivität mit dem Titel „minimal aufspannende Bäume von Computer Science Unplugged befasst sich mit diesem Thema. Link: minimal-spanning-trees Mit Hilfe des Werkzeugs GraphBench lassen sich Experimente auf Graphen, wie auch die Suche nach kürzesten Rundreisen durchführen. Verschiedene Forschungsbereiche suchen nach optimalen Touren mit Hilfe von heuristischen Verfahren („schlaue Software). Vorlesungen an Hochschulen oder Diplomarbeiten befassen sich aktuell mit Anwendungen des Traveling Salesman Problem und speziellen Lösungsverfahren. Link: html Link: Link: informatik-biber.ch 8 Mögliche Lösungen Reflexion Lernfilm: „Beste Rundreise durch sieben Städte Rundreise durch Basel, Bern, Lugano, Luzern, Neuenburg, Zermatt, Zürich Distanztabelle Distanzen zwischen den sieben Orten [km] Basel Bern Lugano Luzern Neuenburg Zermatt Zürich Basel Bern Lugano Luzern Neuenburg Zermatt Zürich 0 95.9 263 97.1 122 229 86.2 95.9 0 242 114 45.7 136 127 263 242 0 169 303 204 205 97.1 114 169 0 137 181 52.1 122 45.7 303 137 0 243 151 229 136 204 181 243 0 232 86.2 127 205 52.1 151 232 0 Ein mögliches Verfahren ist die schrittweise Zusammensetzung der Rundreise aus Verbindungen mit minimalen Distanzen. Die fünf kürzesten Verbindung sind in diesem konkreten Fall: 45.7 (Bern-Neuenburg), 52.1 (Luzern – Zürich), 86.2 (Basel – Zürich), 95.9 (Basel –Bern) und 97.1 (Basel – Luzern). Der Reihe nach können diese auf einer Karte eingezeichnet werden. Die fünfte Verbindung (Basel – Luzern) macht keinen Sinn in Bezug auf eine Rundreise. Anstelle des Wegstück Basel – Luzern verbindet man die noch freien Städte (Zermatt und Lugano) mit Neuenburg und Luzern. Die erhaltene Rundreise Bern-Basel-Zürich-Luzern-Lugano-Zermatt-Neuenburg-Bern hat eine Länge von 895.9 km (45.752.186.295.9243204169 895.9 km) Findige Schülerinnen und Schüler bemerken, dass es besser ist, anstelle von Basel-Bern-Neuenburg die Tour in der Reihenfolge Basel-Neuenburg-Bern zu planen. Das führt zu der kürzesten Rundreise: Bern Neuenburg-Basel-Zürich-Luzern-Lugano-Zermatt-Bern mit einer Länge von 815 km (45.712286.252.1169204136 815 km) In den Beilagen befindet sich eine Schweizer Karte mit den sieben Städten Die Frage nach der Anzahl möglicher Rundreisen bei 4,5 oder 6 Städten können die Lernenden selbständig durch aufzeichnen aller Möglichkeiten beantworten. Ein mögliches Verfahren, welches zu allen Möglichkeiten ermittelt, könnte wie folgt aussehen: Ich beginne bei irgend einer Stadt. Von dieser Stadt habe ich (n-1) Möglichkeiten zu einer nächsten Stadt zu gelangen Von dieser Stadt habe ich (n-2) Möglichkeiten zu einer nächsten Stadt zu gelangen usw. bis es keine Möglichkeiten mehr gibt. Im Fall von 6 Städten sind das 5 4 3 2 1 Möglichkeiten, also 120 Möglichkeiten informatik-biber.ch 9 Nun gilt es noch zu beachten, dass die Richtung in welcher die Rundreise durchlaufen wird, keine Rolle spielt. Das heisst Verbindungen wie z.B. Bern – Basel und Basel – Bern sind im Bezug auf eine Rundreise äquivalent. (Beim Zeichnen aller Möglichkeiten für 5 Städte wird das ersichtlich.) Für den Fall von 6 Städten existieren demnach 60 verschiedene Rundreisen. Die Formel für die Anzahl verschiedener Rundreisen lautet: Anzahl Rundreise (n-1)!/2 Das Ausrufezeichen ist das Symbol für die Fakultät. Es gilt: n! n·(n-1)· ·3·2·1 Experiment 1: „Wer findet die beste Rundreise? Zu diesem Experiment befinden sich zahlreiche Aufgabenblätter mit Lösungen in den Beilagen. Das verwendete numerische Lösungsverfahren sucht nach optimalen Lösungen, findet jedoch nicht immer die beste Lösung. Deshalb haben die Lernenden die Möglichkeit bei Aufgabenblättern mit vielen Städten die Lösung des Computers zu schlagen. Experiment 2: „Die kürzeste Rundreise auf dem Pausenplatz Bei der Durchführung dieses Experiments sollte darauf geachtet werden, dass jede Gruppe von einer Beobachterin oder einem Beobachter (ev. aus einer anderen Gruppe) begleitet wird. Sie notieren die Label der angelaufen Orte (Markierungen) und notieren am Schluss den total zurück gelegten Weg. Falls man die Möglichkeit besitzt, das ganze Feld mit den Markierungen aus der Vogelperspektive aufzunehmen, kann diese Aufnahme bei der Schlussbesprechung verwendet werden um die beste gefundene Lösung zu visualisieren. Es besteht auch die Möglichkeit, dass die Gruppen ihre Markierungen nach einem Plan, den sie im Klassenzimmer vorbereitet haben, auslegen. informatik-biber.ch 10 Impressum Herausgeber SVIA, Schweizerischer Verein für Informatik in der Ausbildung Partner Hasler Stiftung SWITCH Konzeption Umsetzung Lernetz AG Autor Martin Guggisberg, PH FHNW informatik-biber.ch 11