Wie funktionieren Navigationsprogramme? ein Exkurs in die Netzwerkoptimierung und "Kürzeste-Wege-Probleme" - kostenloses Unterrichtsmaterial online bei Elixier

h t t p s : / / w w w . l e h r e r - o n l i n e . d e / u n t e r r i c h t / s e k u n d a r s t u f e n / n a t u r w i s s e n s c h a f t e n / m a t h e m a t i k / u n t e r r i c h t s e i n h e i t / u e / w i e - f u n k t i o n i e r e n - n a v i g a t i o n s p r o g r a m m e - e i n - e x k u r s - i n - d i e - n e t z w e r k o p t i m i e r u n g - u n d - k u e r z e s t e - w e g e - p r o b l e m e /

Über das Anschauungsproblem vom Finden der schnellsten Route lernen die Schülerinnen und Schüler die Grundlagen der Netzwerkoptimierung und das algorithmische Lösen von "Schnellste-Wege-Problemen". Darüber hinaus bearbeiten die Schülerinnen und Schüler das Problem, einen möglichst guten Kompromiss zwischen schnellster und umweltfreundlichster Route zu finden und tauchen dabei in ein Problem der multikriteriellen Optimierung ein.

Anbieter:

Lehrer-Online | Eduversum GmbH, Taunusstr. 52, 65183 Wiesbaden

Autor:

Kathrin Kennel, Lynn Knippertz und Paul Weber

Lange Beschreibung:

Was ist die schnellste Route von Mainz nach München? Google Maps oder andere Online-Karten beantworten uns diese Frage schnell. Aber wie geht ein Computerprogramm dabei vor? Ist die schnellste Route automatisch auch die umweltfreundlichste Route? In diesem Unterrichtsmaterial müssen als erstes aus dem komplexen Straßennetz auf einer Karte Süddeutschlands die wichtigsten Informationen und Wege von Mainz nach München gefunden werden. Dabei konzentrieren sich die Lernenden auf das Autobahnnetz und markieren Straßen und Autobahnkreuze. Autobahnabschnitte werden mit Zeiten ergänzt, die man benötigt, um sie zurückzulegen. So erstellen die Schülerinnen und Schüler einen Graph und entwickeln eine grobe Vorstellung von möglichen Routen und eventuell sogar schon eine Idee für die schnellste Route. An dieser Stelle werden die anwendungsbezogenen Arbeitsblätter durch ein nicht obligatorisches Video ergänzt, das Graphen formal-mathematisch einführt. Die Materialien und Arbeitsblätter finden Sie über den Link am Ende dieser Seite. Wie kann man sich jedoch sicher sein, die schnellste Route gefunden zu haben? Dafür soll der Dijkstra-Algorithmus, der wohl bekannteste "Kürzeste-Wege-Algorithmus", so nachvollzogen werden, dass die Lernenden ihn selbst anwenden können. Da es sich um einen für Schülerinnen und Schüler komplexen Algorithmus in einem nicht bekannten Anwendungsgebiet handelt, bekommen die sie zum Nachvollziehen zuerst übersichtliche grafische Hilfestellungen und Hinweise, die es besonders zu beachten gilt. Auch ein Erklärvideo soll helfen, den Algorithmus zu verstehen. Nachdem die Lernenden den schnellsten Weg gefunden und versucht haben, den Dijkstra-Algorithmus selbst zu formulieren, sind sie nun selbst gefordert, die umweltfreundlichste Route von Mainz nach München zu finden. Weil die Umweltfreundlichkeit einer Route einerseits von sehr vielen Faktoren abhängt, andererseits aber auch nicht eindeutig definiert ist, handelt es sich dabei um eine starke Vereinfachung. Abschließend wird folgende Frage bearbeitet: Wie findet man den besten Kompromiss zwischen schneller und umweltfreundlicher Route? Thematisch schließt somit die Lerneinheit in Richtung der aktuellen Nachhaltigkeitsdebatte ab und schafft fachmathematisch eine Verbindung zwischen Netzwerk- und multikriterieller Optimierung. Darüber hinaus haben die Lernenden die Möglichkeit, sich in einem interaktiven Jupyter-Notebook-Kurs mit dem Programmieren des Dijkstra-Algorithmus zu beschäftigen. Dieser löst die Anschauungsbeispiele in der Programmiersprache Python.

Bildungsebene:

Berufliche Bildung Sekundarstufe I Sekundarstufe II

Frei zugänglich:

nein

Kostenpflichtig:

nein

Lernressourcentyp:

Unterrichtsplanung

Lizenz:

Frei nutzbares Material

Sprache:

Deutsch

Themenbereich:

Geeignet für:

Lehrer