Informatik · Klasse 10

Ideen für aktives Lernen

Heuristiken und Optimierung

Aktive Lernformen eignen sich besonders für Heuristiken und Optimierung, weil Schülerinnen und Schüler die Grenzen exakter Lösungen am eigenen Leib erfahren müssen. Durch eigenes Ausprobieren verstehen sie, warum Computer bei großen Problemen scheitern und warum heuristische Ansätze im Alltag unverzichtbar sind.

• KMK Bildungsstandards
• KMK: STD.03
• KMK: STD.17

• 30–60 Min.
• Partnerarbeit → Ganze Klasse
• 4 Aktivitäten

Aktivität 01

• World Café
• 45 Min. · Kleingruppen

Stationenrotation: Heuristiken testen

Richten Sie vier Stationen ein: Nearest Neighbor, Greedy, 2-Opt und Zufallsheuristik für ein TSP mit 10 Städten. Gruppen lösen jede Instanz in 7 Minuten, notieren Tourenlänge und Zeit. Abschließend vergleichen sie Ergebnisse im Plenum.

Warum finden Computer für manche Rätsel keine perfekte Lösung in sinnvoller Zeit?

Moderationstipp

Während der Stationenrotation achten Sie darauf, dass jede Gruppe die Heuristiken nicht nur anwendet, sondern auch die Ergebnisse dokumentiert und mit Mitschülerinnen vergleicht.

Worauf zu achten ist

Stellen Sie den Lernenden eine kleine TSP-Instanz (z. B. 4-5 Städte) auf einem Arbeitsblatt zur Verfügung. Bitten Sie sie, die Route zu finden, die sie mit dem Nearest Neighbor Algorithmus berechnen würden, und die Gesamtdistanz anzugeben. Vergleichen Sie die Ergebnisse im Plenum.

• Verstehen
• Anwenden
• Analysieren
• Sozialbewusstsein
• Beziehungsfähigkeit

Aktivität 02

• World Café
• 30 Min. · Partnerarbeit

Paararbeit: Routenplaner bauen

Paare zeichnen 8 Städte auf Papier, wenden Nearest-Neighbor-Heuristik an und messen die Tourenlänge. Sie variieren Startpunkte und diskutieren, warum keine perfekte Lösung entsteht. Erweitern Sie auf digitale Tools wie GeoGebra.

Wie funktionieren „gute genug" Lösungen im Alltag?

Moderationstipp

In der Paararbeit zum Routenplaner stellen Sie sicher, dass die Teams ihre Algorithmen schriftlich festhalten und mit konkreten Distanzen testen.

Worauf zu achten ist

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie sind ein Projektmanager für die Planung einer mehrtägigen Fahrradtour durch die Alpen. Welche Art von Problemen würden Sie bei der Routenplanung erwarten, und warum wäre eine exakte Lösung möglicherweise nicht die beste Wahl?'

• Verstehen
• Anwenden
• Analysieren
• Sozialbewusstsein
• Beziehungsfähigkeit

Aktivität 03

• World Café
• 50 Min. · Ganze Klasse

Klassenexperiment: Exakt vs. Heuristik

Die Klasse testet ein TSP mit 12 Städten: Eine Gruppe sucht exhaustiv (kleine Instanz), andere heuristisch. Gemeinsam plotten sie Ergebnisse und diskutieren Skalierbarkeit. Nutzen Sie Python-Skripte für Visualisierung.

Was ist das Problem des Handlungsreisenden?

Moderationstipp

Beim Klassenexperiment zur Gegenüberstellung von exakter Lösung und Heuristik sorgen Sie für klare Zeitvorgaben, damit die Schüler die Diskrepanz in der Laufzeit selbst erkennen.

Worauf zu achten ist

Lassen Sie die Schülerinnen und Schüler auf einem Zettel erklären, warum ein Computer für das Problem des Handlungsreisenden mit 100 Städten wahrscheinlich keine perfekte Lösung findet, und nennen Sie eine Situation, in der eine 'gute genug'-Lösung ausreicht.

• Verstehen
• Anwenden
• Analysieren
• Sozialbewusstsein
• Beziehungsfähigkeit

Aktivität 04

• World Café
• 60 Min. · Einzelarbeit

Individuell: Heuristik programmieren

Jede Schülerin oder jeder Schüler implementiert Nearest Neighbor in Python für variable Städteanzahlen. Testen Sie Laufzeit und Güte, vergleichen Sie mit Bibliotheken. Teilen Sie Code im Klassenchat.

Warum finden Computer für manche Rätsel keine perfekte Lösung in sinnvoller Zeit?

Moderationstipp

Bei der individuellen Programmierung der Heuristik bieten Sie den Lernenden Debugging-Hilfen an, damit sie den Code nicht vorzeitig verwerfen.

Worauf zu achten ist

Stellen Sie den Lernenden eine kleine TSP-Instanz (z. B. 4-5 Städte) auf einem Arbeitsblatt zur Verfügung. Bitten Sie sie, die Route zu finden, die sie mit dem Nearest Neighbor Algorithmus berechnen würden, und die Gesamtdistanz anzugeben. Vergleichen Sie die Ergebnisse im Plenum.

• Verstehen
• Anwenden
• Analysieren
• Sozialbewusstsein
• Beziehungsfähigkeit

Einige Hinweise zum Unterrichten dieser Einheit

Erklären Sie zunächst die Grundidee der Heuristiken mit einem konkreten Beispiel aus dem Alltag, etwa der Routenplanung. Vermeiden Sie abstrakte Definitionen und setzen Sie stattdessen auf Simulationen und eigene Experimente. Geben Sie den Lernenden Zeit, ihre eigenen Ansätze zu entwickeln und zu scheitern, bevor Sie theoretische Konzepte einführen. Research zeigt, dass dieser Prozess des 'konstruktiven Scheiterns' das Verständnis nachhaltig fördert.

Am Ende der Einheit können die Lernenden heuristische Verfahren anwenden, ihre Güte bewerten und den Unterschied zu exakten Lösungen erklären. Sie erkennen, wann eine 'gute genug'-Lösung sinnvoll ist und transferieren dieses Wissen auf reale Situationen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Stationenrotation zum Testen von Heuristiken hören Sie häufig die Aussage: 'Computer finden für jedes Problem immer die beste Lösung.'

  Nutzen Sie die Stationenrotation, um die Explosion der Möglichkeiten bei großen Problemen sichtbar zu machen. Geben Sie den Lernenden eine TSP-Instanz mit 8 Städten und lassen Sie sie die Anzahl der möglichen Routen berechnen. Die Erkenntnis, dass exakte Lösungen bei 15 Städten bereits Milliarden Optionen umfassen, widerlegt den Mythos direkt.

• Während der Paararbeit zum Bau eines Routenplaners argumentieren einige Schüler: 'Heuristiken liefern immer falsche Ergebnisse.'

  Verweisen Sie in der Paararbeit auf die Ergebnisse der Stationenrotation. Lassen Sie die Teams ihre heuristischen Lösungen mit den exakten Lösungen kleinerer Instanzen vergleichen und diskutieren, wie nah diese oft am Optimum liegen. Die konkreten Distanzwerte zeigen, dass Heuristiken im Alltag völlig ausreichen.

• Im Plenum nach dem Klassenexperiment äußern Lernende: 'Optimierung ist nur für Profis relevant.'

  Nutzen Sie die Ergebnisse des Klassenexperiments, um auf Alltagsbeispiele einzugehen. Fragen Sie die Schüler, welche Heuristiken Google Maps verwendet, und lassen Sie sie ihre eigenen Routen mit der App vergleichen. Die direkte Verbindung zu einer Anwendung, die sie täglich nutzen, macht die Relevanz greifbar.

---

In dieser Übersicht verwendete Methoden

• World Café