Informatik · Klasse 10

Ideen für aktives Lernen

Suchen in Graphen und Bäumen

Aktive Lernumgebungen wie Stationenlernen oder Simulationen ermöglichen es den Schülern, komplexe Suchalgorithmen nicht nur theoretisch zu verstehen, sondern ihre Wirkung in echten Modellen zu erleben. Indem sie Graphen und Bäume selbst bauen und Algorithmen anwenden, erkennen sie die Unterschiede zwischen BFS und DFS sowie deren Grenzen in der Praxis.

• KMK Bildungsstandards
• KMK: STD.01
• KMK: STD.16

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

Aktivität 01

• Lernen an Stationen
• 45 Min. · Kleingruppen

Lernen an Stationen: Graphen bauen

Schüler bauen mit Papier und Fäden einen Graphen einer Stadt. Sie markieren Knoten als Städte und Kanten als Straßen. In Gruppen führen sie BFS durch, um den kürzesten Weg zu finden, und notieren Schritte.

Wie findet ein Navi den kürzesten Weg von Berlin nach München?

Moderationstipp

Stellen Sie beim Stationenlernen sicher, dass jede Gruppe ihren Graphen aus Pins und Fäden klar beschriften und präsentieren kann, damit die Unterschiede zwischen Zyklen und Hierarchien sichtbar werden.

Worauf zu achten ist

Geben Sie jedem Schüler eine Karte mit einem einfachen Graphen (z.B. 5 Knoten, 6 Kanten). Bitten Sie die Schüler, den Graphen mit BFS und dann mit DFS zu durchlaufen und die Reihenfolge der besuchten Knoten aufzuschreiben. Vergleichen Sie die Ergebnisse.

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Aktivität 02

• Planspiel
• 30 Min. · Partnerarbeit

Baum-Suche: Hierarchie simulieren

Erstellen Sie einen Familienbaum als Baumstruktur. Schüler suchen mit DFS nach einem Verwandten auf der tiefsten Ebene. Sie vergleichen Ergebnisse mit BFS und diskutieren Vor- und Nachteile.

Was unterscheidet die Tiefensuche von der Breitensuche?

Moderationstipp

Beobachten Sie die Schüler während der Baum-Suche, ob sie die Hierarchieebenen korrekt durchlaufen. Fordern Sie sie auf, ihre Suchwege mit Pfeilen zu markieren, um Fehlerquellen zu identifizieren.

Worauf zu achten ist

Stellen Sie die Frage: 'Ein Freund möchte den kürzesten Weg durch eine Stadt finden, die wie ein Gitter aufgebaut ist. Welchen Suchalgorithmus würden Sie empfehlen und warum?' Bewerten Sie die Antworten auf die korrekte Anwendung von BFS und die Begründung.

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Aktivität 03

• Planspiel
• 50 Min. · Partnerarbeit

Computer-Simulation: Algorithmen programmieren

Mit Scratch oder Python implementieren Schüler BFS in einem einfachen Graphen. Sie testen mit verschiedenen Startpunkten und messen Laufdauer. Gemeinsam optimieren sie den Code.

Wie werden Hierarchien in der Informatik abgebildet?

Moderationstipp

Vorbereiten Sie in der Computer-Simulation vordefinierte Graphen mit verschiedenen Gewichtungen, damit die Schüler die Auswirkungen auf BFS und DFS direkt vergleichen können.

Worauf zu achten ist

Leiten Sie eine Diskussion mit der Frage: 'Stellen Sie sich vor, Sie entwerfen ein System zur Empfehlung von Freunden in einem sozialen Netzwerk. Welche Datenstruktur (Graph oder Baum) wäre besser geeignet und warum? Welche Suchstrategie (BFS oder DFS) würden Sie für die Empfehlungsfindung nutzen?'

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Aktivität 04

• Planspiel
• 60 Min. · Kleingruppen

Ganzer Unterricht: Navi-Challenge

Teilen Sie die Klasse in Teams, die ein Navi-Problem lösen. Jede Gruppe simuliert einen Algorithmus auf einer großen Karte und präsentiert den Pfad. Die Klasse bewertet Effizienz.

Wie findet ein Navi den kürzesten Weg von Berlin nach München?

Moderationstipp

Führen Sie die Navi-Challenge mit einer realen Karte durch, auf der die Schüler ihre Suchwege mit unterschiedlichen Farben markieren müssen, um die Effizienz der Algorithmen zu visualisieren.

Worauf zu achten ist

Geben Sie jedem Schüler eine Karte mit einem einfachen Graphen (z.B. 5 Knoten, 6 Kanten). Bitten Sie die Schüler, den Graphen mit BFS und dann mit DFS zu durchlaufen und die Reihenfolge der besuchten Knoten aufzuschreiben. Vergleichen Sie die Ergebnisse.

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit konkreten, greifbaren Beispielen wie Stadtplänen oder sozialen Netzwerken, bevor sie zur abstrakten Darstellung übergehen. Sie vermeiden es, die Algorithmen isoliert zu lehren, sondern verknüpfen sie stets mit anwendbaren Problemen. Wichtig ist, dass die Schüler die Grenzen der Algorithmen selbst entdecken, etwa durch Messungen oder Simulationen, statt ihnen die Ergebnisse vorzugeben.

Am Ende können die Schülerinnen und Schüler Graphen und Bäume unterscheiden, beide Suchalgorithmen korrekt anwenden und ihre Eignung für verschiedene Szenarien begründen. Sie erkennen, dass die Wahl des Algorithmus von der Struktur der Daten und der Aufgabenstellung abhängt.

---

Vorsicht vor diesen Fehlvorstellungen

• Während des Stationenlernens 'Graphen bauen' könnte der Eindruck entstehen, dass BFS immer den kürzesten Weg findet.

  Nutzen Sie in dieser Station Graphen mit unterschiedlich gewichteten Kanten (z.B. durch farbige Pins). Fordern Sie die Schüler auf, die Weglängen zu messen und zu vergleichen, um zu erkennen, dass BFS hier versagt und eine andere Strategie wie Dijkstra benötigt wird.

• Während der Baum-Suche 'Hierarchie simulieren' könnte der Eindruck entstehen, dass Graphen und Bäume identisch sind.

  Lassen Sie die Schüler in dieser Station bewusst Zyklen in Graphen einbauen und vergleichen Sie diese mit den linearen Pfaden in Bäumen. Die Präsentation der Ergebnisse im Plenum macht die Unterschiede klar.

• Während der Computer-Simulation 'Algorithmen programmieren' könnte der Eindruck entstehen, dass DFS immer effizienter ist.

  Nutzen Sie in dieser Station Graphen mit langen Pfaden. Fordern Sie die Schüler auf, die Suchzeiten zu notieren und zu diskutieren, warum BFS in solchen Fällen bessere Ergebnisse liefert.

---

In dieser Übersicht verwendete Methoden

• Lernen an Stationen
• Planspiel