Informatik · Klasse 11

Ideen für aktives Lernen

Graphenalgorithmen: Einführung

Aktives Lernen eignet sich besonders gut für Graphenalgorithmen, weil Schüler durch physische und visuelle Modellierungen abstrakte Konzepte wie Knoten, Kanten und Traversierungen greifbar machen. Die Kombination aus Gruppenarbeit, Simulationen und Programmierung fördert das Verständnis für die Struktur und Funktion von Graphen, die für viele technische und alltagsnahe Probleme grundlegend sind.

KMK BildungsstandardsKMK: Sekundarstufe II - ModellierenKMK: Sekundarstufe II - Algorithmen entwerfen

30–50 Min.Partnerarbeit → Ganze Klasse4 Aktivitäten

Aktivität 01

Concept-Mapping45 Min. · Kleingruppen

Gruppenmodellierung: Städtenetzwerk bauen

Schüler erhalten Kartenkarten als Knoten und Fäden als Kanten, um ein Städtenetzwerk zu modellieren. Sie markieren Startknoten und traversieren mit BFS und DFS, notieren besuchte Knoten. Abschließend diskutieren sie Anwendungen in Navigationssystemen.

Wie lassen sich reale Probleme mithilfe von Graphen modellieren?

ModerationstippWährend der Gruppenmodellierung des Städtenetzwerks fragen Sie gezielt nach zyklischen Strukturen und lassen Sie Schüler diese markieren, um ungerichtete von gerichteten Graphen zu unterscheiden.

Worauf zu achten istGeben Sie jedem Schüler ein Blatt mit einem kleinen, ungerichteten Graphen (z.B. 5 Knoten, 6 Kanten). Bitten Sie die Schüler, eine Adjazenzliste für diesen Graphen zu erstellen und die Reihenfolge der besuchten Knoten bei einer manuellen Tiefensuche (DFS) ausgehend von einem bestimmten Knoten anzugeben.

VerstehenAnalysierenErschaffenSelbstwahrnehmungSelbststeuerung

Komplette Unterrichtsstunde erstellen

Aktivität 02

Planspiel30 Min. · Partnerarbeit

Planspiel: Murmel-Traversierung

Verwenden Sie einen Graphen aus Pappkarton mit Löchern als Knoten. Murmeln rollen für BFS (alle Nachbarn zuerst) oder DFS (tief zuerst). Gruppen protokollieren Pfade und vergleichen Ergebnisse.

Vergleichen Sie Breitensuche (BFS) und Tiefensuche (DFS) bei der Traversierung von Graphen.

ModerationstippBeobachten Sie bei der Murmel-Traversierung, ob Schüler die schichtweise Ausbreitung von BFS und die Pfadvertiefung von DFS aktiv nachvollziehen oder nur mechanisch wiederholen.

Worauf zu achten istStellen Sie die Frage: 'Unter welchen Umständen wäre die Breitensuche (BFS) besser geeignet als die Tiefensuche (DFS), um Informationen in einem großen sozialen Netzwerk zu verbreiten? Begründen Sie Ihre Antwort anhand der Funktionsweise beider Algorithmen.'

AnwendenAnalysierenBewertenErschaffenSozialbewusstseinEntscheidungsfähigkeit

Komplette Unterrichtsstunde erstellen

Aktivität 03

Concept-Mapping50 Min. · Partnerarbeit

Programmierpraxis: Einfache Traversierung

Schüler implementieren BFS und DFS in Python mit einer Adjazenzliste. Testen Sie mit einem sozialen Netzwerk-Beispiel. Paare debuggen gegenseitig und visualisieren Pfade mit Matplotlib.

Analysieren Sie die Bedeutung von Graphen in sozialen Netzwerken und Navigationssystemen.

ModerationstippBei der Programmierpraxis achten Sie darauf, dass Schüler nicht nur Code schreiben, sondern ihre Implementierung mit Beispielgraphen aus der Simulation vergleichen und anpassen.

Worauf zu achten istZeigen Sie eine einfache Adjazenzmatrix und fragen Sie: 'Welche Knoten sind direkt miteinander verbunden? Geben Sie die Knotenpaare an.' Wiederholen Sie dies für eine Adjazenzliste.

VerstehenAnalysierenErschaffenSelbstwahrnehmungSelbststeuerung

Komplette Unterrichtsstunde erstellen

Aktivität 04

Fishbowl-Diskussion35 Min. · Ganze Klasse

Fishbowl-Diskussion: Reale Modelle analysieren

Präsentieren Sie Graphen aus Facebook oder Google Maps. Whole class diskutiert Modellierung, traversiert manuell und bewertet BFS/DFS-Eignung.

Wie lassen sich reale Probleme mithilfe von Graphen modellieren?

AnalysierenBewertenSozialbewusstseinSelbstwahrnehmung

Komplette Unterrichtsstunde erstellen

Vorlagen

Vorlagen, die zu diesen Informatik-Aktivitäten passen

Nutzen, bearbeiten, drucken oder teilen.

UnterrichtsplanMINTEine MINT Vorlage, die auf dem Engineering Design Process basiert. Sie integriert Mathematik, Informatik, Naturwissenschaft und Technik durch reale Herausforderungen, die Lernende untersuchen und lösen.Unterrichtsplan

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit einer klaren Struktur: Zuerst werden Graphen als Modellierungsproblem eingeführt, bevor Algorithmen als Lösungsstrategien dienen. Vermeiden Sie es, beide Algorithmen gleichzeitig zu erklären, da dies die Unterschiede verwischt. Nutzen Sie Schülerfragen als Anker für Vertiefungen, etwa wenn jemand fragt, warum BFS in sozialen Netzwerken schneller Informationen verbreitet. Die Forschung zeigt, dass Lernende durch wiederholtes Anwenden und Erklären der Algorithmen ein tieferes Verständnis entwickeln, als durch reine Theorievermittlung.

Am Ende der Einheit können Schüler Graphen als Adjazenzlisten oder -matrizen darstellen, die Unterschiede zwischen BFS und DFS erklären und beide Algorithmen manuell sowie in einfachen Programmen anwenden. Sie erkennen, wann welcher Algorithmus sinnvoll ist und identifizieren typische Fehlerquellen in der Modellierung oder Implementierung.

Vorsicht vor diesen Fehlvorstellungen

Während der Gruppenmodellierung des Städtenetzwerks hören Sie Schüler sagen: 'Graphen haben doch immer Pfeile und keine Kreise.'
Fordern Sie die Gruppe auf, einen einfachen Kreis aus vier Städten zu zeichnen und zu markieren, ob die Verbindungen ungerichtet (z.B. Straßen) oder gerichtet (z.B. Einbahnstraßen) sind. Diskutieren Sie gemeinsam, warum Zyklen in realen Modellen häufig vorkommen.
Während der Murmel-Simulation zur Traversierung beobachten Sie, dass Schüler annehmen: 'BFS und DFS geben immer dieselbe Reihenfolge aus.'
Bitten Sie die Schüler, die Murmel-Simulation mit demselben Graphen, aber unterschiedlichen Startknoten zu wiederholen und die Ergebnisse zu vergleichen. Fragen Sie nach: 'Was ändert sich, wenn wir bei einem anderen Knoten beginnen?'
Während der Programmierpraxis zur Adjazenzmatrix hören Sie Schüler sagen: 'Matrizen sind immer schneller als Listen.'
Geben Sie den Schülern einen Graphen vor, bei dem die Matrix fast leer ist (z.B. nur 3 von 100 Knoten verbunden), und lassen Sie sie die Speicherauslastung beider Darstellungen berechnen und vergleichen.

In dieser Übersicht verwendete Methoden

Mehr in Algorithmen und Komplexität

Grundlagen der Algorithmenanalyse

Einführung in die Konzepte von Zeit- und Platzkomplexität.

2 methodologies

Suchalgorithmen: Linear und Binär

Vergleich verschiedener Verfahren wie Linear Search, Binary Search oder BubbleSort.

2 methodologies

Sortieralgorithmen: Bubble Sort und Selection Sort

Die Schülerinnen und Schüler implementieren und analysieren einfache Sortierverfahren.

2 methodologies

Sortieralgorithmen: Merge Sort und Quick Sort

Einführung in effizientere, rekursive Sortierverfahren.

2 methodologies

Effizienzanalyse (O-Notation)

Mathematische Abschätzung des Zeit- und Platzbedarfs von Algorithmen.

2 methodologies