Informatik · Klasse 13

Ideen für aktives Lernen

Graphen: Darstellung und Grundlagen

Aktives Handeln verankert abstrakte Konzepte wie Graphen in realen Szenarien und macht Beziehungen zwischen Knoten und Kanten greifbar. Durch das Bauen, Vergleichen und Programmieren von Graphen entwickeln Schülerinnen und Schüler ein intuitives Verständnis für die Grundlagen, das über theoretische Erklärungen hinausgeht.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Daten und ihre Strukturierung
• KMK: Sekundarstufe II - Strukturieren und Vernetzen

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

Aktivität 01

• Concept-Mapping
• 45 Min. · Kleingruppen

Graphenbau: Freundschaftsnetzwerke

Schüler zeichnen ein Klassennetzwerk mit Knoten für Mitschüler und Kanten für Freundschaften. Sie klassifizieren als ungerichtet oder gerichtet und notieren Eigenschaften. In der Reflexion diskutieren sie Vor- und Nachteile der Visualisierung.

Erklären Sie die Konzepte von Knoten, Kanten und Graphentypen.

Moderationstipp

Fordern Sie während 'Graphenbau: Freundschaftsnetzwerke' gezielt auf, Knoten und Kanten mit konkreten Beispielen zu benennen, um den abstrakten Charakter zu betonen.

Worauf zu achten ist

Geben Sie den Schülern eine Liste mit drei verschiedenen Netzwerkbeschreibungen (z. B. ein U-Bahn-Netz, eine Liste von E-Mails zwischen Kollegen, eine Liste von Webseiten mit Links). Bitten Sie sie, für jede Beschreibung zu entscheiden, ob ein gerichteter oder ungerichteter Graph am besten geeignet ist und warum.

• Verstehen
• Analysieren
• Erschaffen
• Selbstwahrnehmung
• Selbststeuerung

Aktivität 02

• Concept-Mapping
• 30 Min. · Partnerarbeit

Vergleich: Matrix vs. Liste

Paare erstellen für einen Graphen eine Adjazenzmatrix und eine Adjazenzliste. Sie messen Speicherbedarf und simulieren Nachbarschaftsabfragen. Abschließend vergleichen sie Zeit- und Platzkomplexität in einer Tabelle.

Vergleichen Sie Adjazenzmatrizen und Adjazenzlisten zur Graphendarstellung.

Moderationstipp

Nutzen Sie bei 'Vergleich: Matrix vs. Liste' eine Whiteboard-Diskussion, um gemeinsam die Vor- und Nachteile beider Darstellungsformen zu sammeln und sichtbar zu machen.

Worauf zu achten ist

Zeigen Sie eine kleine Adjazenzmatrix und eine entsprechende Adjazenzliste für einen einfachen Graphen. Stellen Sie folgende Fragen: 'Welche Kante fehlt in der Adjazenzliste?' oder 'Welche Knoten sind mit Knoten 3 verbunden, basierend auf der Adjazenzmatrix?'

• Verstehen
• Analysieren
• Erschaffen
• Selbstwahrnehmung
• Selbststeuerung

Aktivität 03

• Concept-Mapping
• 60 Min. · Kleingruppen

Programmier-Challenge: Graphen modellieren

Gruppen implementieren einen einfachen Graphen in Python mit Listen oder Dictionaries. Sie laden reale Daten, z. B. aus einem Social-Media-Beispiel, und testen Traversierungen. Gemeinsam debuggen sie und präsentieren Ergebnisse.

Analysieren Sie, wie reale Netzwerke wie soziale Medien als Graphen modelliert werden können.

Moderationstipp

Lassen Sie in 'Programmier-Challenge: Graphen modellieren' die Schülerinnen und Schüler ihre Lösungen in Kleingruppen präsentieren, um Lernfortschritte durch Peer-Feedback zu verstärken.

Worauf zu achten ist

Stellen Sie die Frage: 'Stellen Sie sich vor, Sie entwerfen ein System zur Empfehlung von Musik. Wie würden Sie dieses Problem als Graphenproblem modellieren? Welche wären die Knoten und welche die Kanten? Welche Art von Graph wäre am besten geeignet und warum?'

• Verstehen
• Analysieren
• Erschaffen
• Selbstwahrnehmung
• Selbststeuerung

Aktivität 04

• Concept-Mapping
• 50 Min. · Ganze Klasse

Netzwerk-Analyse: reale Daten

Die Klasse analysiert ein öffentliches Dataset wie Flugverbindungen als Graph. Individuen berechnen Gradzahlen, teilen in Plenum und diskutieren Implikationen für Algorithmen.

Erklären Sie die Konzepte von Knoten, Kanten und Graphentypen.

Moderationstipp

Bei 'Netzwerk-Analyse: reale Daten' achten Sie darauf, dass die Datenauswahl die Vielfalt der Graphentypen widerspiegelt, um unterschiedliche Anwendungsfälle zu erkunden.

Worauf zu achten ist

Geben Sie den Schülern eine Liste mit drei verschiedenen Netzwerkbeschreibungen (z. B. ein U-Bahn-Netz, eine Liste von E-Mails zwischen Kollegen, eine Liste von Webseiten mit Links). Bitten Sie sie, für jede Beschreibung zu entscheiden, ob ein gerichteter oder ungerichteter Graph am besten geeignet ist und warum.

• Verstehen
• Analysieren
• Erschaffen
• Selbstwahrnehmung
• Selbststeuerung

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit anschaulichen Beispielen aus dem Alltag, um Graphen als Modelle für Netzwerke zu etablieren. Sie vermeiden es, sich in theoretischen Definitionen zu verlieren, und setzen stattdessen auf handlungsorientierte Aufgaben, die das abstrakte Denken fördern. Wichtig ist, dass Visualisierungen als Hilfsmittel genutzt werden, ohne dass sie die einzige Darstellungsform bleiben. Durch gezielte Fragen und Gegenüberstellungen von Darstellungsformen wird das Verständnis für die Struktur von Graphen geschärft.

Erfolgreich gelernt haben die Schülerinnen und Schüler, wenn sie Graphen als Modelle für Netzwerke erkennen und selbstständig zwischen ungerichteten und gerichteten Graphen, Listen und Matrizen unterscheiden können. Sie sollen zudem einfache Algorithmen anwenden und die Eignung der Darstellungsformen begründen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während 'Graphenbau: Freundschaftsnetzwerke' wird beobachtet, dass einige Schülerinnen und Schüler Graphen als bloße Zeichnungen missverstehen.

  Lenken Sie die Aufmerksamkeit auf die abstrakte Natur der Graphen, indem Sie die Schülerinnen und Schüler auffordern, ihre Netzwerke zunächst als Listen von Knoten und Kanten zu beschreiben, bevor sie diese visualisieren.

• Während 'Vergleich: Matrix vs. Liste' wird bemerkt, dass Schülerinnen und Schüler Matrizen generell als effizienter einstufen.

  Lassen Sie die Schülerinnen und Schüler mit vorgegebenen Graphen experimentieren und die Speicherplatzausnutzung beider Darstellungsformen vergleichen, um das Verständnis für die Abhängigkeit von der Graphendichte zu fördern.

• Während 'Programmier-Challenge: Graphen modellieren' wird festgestellt, dass Schülerinnen und Schüler unbewusst von bidirektionalen Kanten ausgehen.

  Fordern Sie die Schülerinnen und Schüler auf, ihre Graphenmodelle mit gerichteten Kanten zu testen, indem sie reale Szenarien wie Web-Links oder Einbahnstraßen verwenden.

---

In dieser Übersicht verwendete Methoden

• Concept-Mapping