Wie funktionieren Navigationsprogramme? – ein Exkurs in die Netzwerkoptimierung und "Kürzeste-Wege-Probleme"

Unterrichtseinheit

Ü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.

  • Mathematik / Rechnen & Logik / Informatik / Wirtschaftsinformatik / Computer, Internet & Co.
  • Sekundarstufe I, Sekundarstufe II, Berufliche Bildung
  • 1 bis 5 Unterrichtsstunden
  • kooperatives Lernen, Internetressource, Arbeitsblatt

Beschreibung der Unterrichtseinheit

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.

Unterrichtsablauf

Inhalt
Sozial- / Aktionsform

Didaktisch-methodischer Kommentar

Relevanz des Themas

Heutzutage spielen Navigationsprogramme, besonders Google Maps oder Apple Karten, eine sehr große Rolle und werden alltäglich verwendet. Das Lösen von Navigationsproblemen kann dem mathematischen Fachgebiet der Netzwerkoptimierung zugeordnet werden. Das allein zeigt die herausragende Relevanz und unterschätzte Bedeutung eines Themas, das in den Lehrplänen der Länder deutschlandweit bisher keine große spielt.

Vorkenntnisse

Die Lernenden benötigen für die Unterrichtseinheit keine mathematischen Vorkenntnisse, da es sich um ein außerschulisches mathematisches Anwendungsfeld handelt. Durch die recht anspruchsvollen Inhalte ist diese Lernumgebung jedoch erst für Schülerinnen und Schüler ab der 8. Klasse bis hin zur Oberstufe empfohlen.

Didaktische Analyse

Die Schülerinnen und Schüler lernen mathematische Inhalte im Bereich der Netzwerkoptimierung kennen. Sie lernen den Umgang mit Graphen, Knoten, Kanten und Kantengewichten. Ein Exkurs mit einer kleinen Einführung in die formal-mathematische Netzwerkoptimierung wird für leistungsstarke Oberstufenschülerinnen und -schüler in einem Video gegeben. Außerdem erarbeiten sie ein algorithmisches Vorgehen, den Dijkstra-Algorithmus, sowie ein bikriterielles Netzwerkoptimierungsproblem. Lernschwierigkeiten sind besonders bei der Formulierung des Algorithmus zu erwarten, weswegen hier das Wahrnehmen der Hilfestellungen im Erklärvideo empfohlen wird.

Methodische Analyse

Das Lernheft beziehungsweise die Arbeitsblätter können ausgedruckt, ausgeteilt und bearbeitet werden. Die Bearbeitung an Tablets bietet sich ebenfalls an. Für den Programmierexkurs ist ein Computer oder ein Tablet notwendig.

Es gibt unterschiedliche Möglichkeiten, die Lerneinheit methodisch durchzuführen:

  1. Sie kann über mehrere Stunden als Wochenarbeitsauftrag mit dem Lernheft in Einzel- oder Paararbeit erfolgen. Sicherungen können in kleinen Gruppen- oder Paararbeitsphasen durchgeführt werden, indem Ergebnisse verglichen werden.
  2. Die Arbeitsphasen des Lernhefts sind als Arbeitsblätter nutzbar. Für jede Arbeitsphase kann eine Unterrichtsstunde verwendet werden. Am Anfang kann ein gemeinsamer Einstieg und am Ende eine gemeinsame Sicherung stattfinden. Die Arbeitsphasen finden in Einzel- oder Paararbeit statt.
  3. Es ist auch denkbar, das Lernheft vollständig in einer Heimarbeitsphase durchzuführen. Am Ende sollte aber eine Besprechung im Unterricht stattfinden

Hinweise zu den Materialien

Arbeitsblatt 1: Die Lernenden erstellen aus Kartenmaterial ein Netzwerk aus Knoten und Kanten.

Arbeitsblatt 2: Die Lernenden vollziehen an einem Beispiel den Dijkstra-Algorithmus nach und formulieren ihn selbst.

Arbeitsblatt 3: Die Lernenden wenden den Dijkstra-Algorithmus an einem Beispiel selbst an.

Arbeitsblatt 4: Die Lernenden lösen an einem Beispiel ein bikriterielles Netzwerksoptimierungsproblem.

Programmierexkurs: Die Lernenden vollziehen den Code des Dijkstra-Algorithmus nach und programmieren Abschnitte selbst.

Alle Arbeitsblätter sind einzeln oder als Lernheft zusammengefasst verfügbar. Sie können die Arbeitsblätter über den Link am Ender der Seite herunterladen.

Digitale Kompetenzen, die Lehrende zur Umsetzung der Unterrichtseinheit benötigen (nach dem DigCompEdu Modell)

Die Lehrkräfte integrieren das Hilfsmaterial zur Programmierung des Dijkstra-Algorithmus, um den Lernenden das Erarbeiten eigener, kreativer Lösungen zu ermöglichen und sie in ihrem Lösungsprozess zu unterstützen (3.2 und 3.4). Dabei nutzen sie das Lernvideo zu Graphen, um den Lernenden das Vertiefen ihres eigenen Wissens zu ermöglichen (3.4).

IMMER UP TO DATE SEIN

Möchten Sie über neue Veröffentlichungen der Deutsche Telekom Stiftung auf der Plattform Lehrer-Online stets informiert sein? Dann melden Sie sich hier an.

Vermittelte Kompetenzen

Fachkompetenz

Die Schülerinnen und Schüler

  • erstellen einen Graph mit Knoten, Kanten und Kantengewichten, indem sie aus Kartenmaterial einen Graphen erstellen.
  • erklären und formulieren den Dijkstra-Algorithmus, indem sie ihn an einem Beispiel nachvollziehen und anschließend die einzelnen Schritte dokumentieren.
  • wenden den Dijkstra-Algorithmus an, indem sie die umweltfreundlichste Route zwischen Mainz und München finden.

Medienkompetenz

Die Schülerinnen und Schüler

  • verstehen die Funktionsweise von Navigationsprogrammen, indem sie grundlegende Prinzipien der Netzwerkoptimierung anhand eines Beispiels nachvollziehen.
  • erklären einen Algorithmus, indem sie algorithmische Strukturen in einem Beispiel erkennen und allgemeingültig formulieren.
  • lösen ein technisches Problem, indem sie ein "Kürzeste-Wege-Problem" in der Programmiersprache Python formulieren.

Sozialkompetenz

Die Schülerinnen und Schüler

  • kommunizieren miteinander, indem sie in Paararbeit zusammenarbeiten.
  • geben einander Feedback, indem sie in Sicherungsphasen Lösungen kontrollieren und besprechen.

21st Century-Skills

Die Schülerinnen und Schüler

  • fördern sich im kritischen Denken, indem sie bei der Formulierung und Programmierung des Dijkstra-Algorithmus strukturiert vorgehen, Argumente innerhalb der Lerngruppe analysieren und die Ergebnisse des Dijkstra-Algorithmus nutzen, um die umweltfreundlichste Route zu bestimmen*.
  • stärken ihre Fähigkeiten zur Kollaboration und Kommunikation, indem sie die Aufgaben im Team diskutieren und lösen.
  • fördern ihr Verständnis der digitalen Welt, indem sie durch das Bearbeiten der Aufgaben einen Einblick in die Funktionsweise von Navigationsprogrammen erlangen.

* nach Ennis, R.H. (2011). Critical Thinking: Reflection and perspective – Part I. Inquiry: CT across the Disciplines 26 (1), S. 4–18.



Autorenteam

Avatar
Kathrin Kennel, Lynn Knippertz und Paul Weber

Zum Profil

Lizenzinformation

Frei nutzbares Material
Die von Lehrer-Online angebotenen Materialien können frei für den Unterricht genutzt und an die eigene Zielgruppe angepasst werden.

Herausgeber

Die Zukunft des MINT-Lernens

Die Materialien sind im Projekt "Die Zukunft des MINT-Lernens" der Deutsche Telekom Stiftung entstanden.