Informatik · Klasse 12

Ideen für aktives Lernen

Suchverfahren: Binäre Suche und Hashing

Aktives Lernen zeigt hier seine Stärke, weil die Effizienz von Suchverfahren nicht durch Theorie allein begreifbar wird. Schülerinnen und Schüler müssen die Algorithmen selbst anwenden, messen und vergleichen, um zu verstehen, warum Sortierung und Hash-Funktionen entscheidend sind. Erst durch eigenes Ausprobieren und Reflektieren wird der Unterschied zwischen O(n) und O(log n) oder zwischen O(1) und O(n) im Alltag spürbar.

KMK BildungsstandardsKMK: Sekundarstufe II - Modellieren und ImplementierenKMK: Sekundarstufe II - Problemlösen und Handeln
25–50 Min.Partnerarbeit → Ganze Klasse4 Aktivitäten

Aktivität 01

Forschungskreis45 Min. · Partnerarbeit

Pair Programming: Binäre Suche implementieren

Paare sortieren eine Liste von 20 Zahlen und coden die binäre Suche in Python. Sie testen mit verschiedenen Werten und messen Vergleichsschritte. Abschließend vergleichen sie mit linearer Suche.

Welche Rolle spielen vorsortierte Daten für die Effizienz von Suchalgorithmen?

ModerationstippLassen Sie die Schülerinnen und Schüler bei der Pair Programming die Schritte der binären Suche laut kommentieren, um die Entscheidungslogik zu verdeutlichen.

Worauf zu achten istGeben Sie den Schülern eine kleine, sortierte Liste von Zahlen und einen Suchwert. Bitten Sie sie, die Schritte der binären Suche auf Papier nachzuvollziehen und den Mittelwert bei jedem Schritt zu notieren, bis das Element gefunden ist oder ausgeschlossen wird.

AnalysierenBewertenErschaffenSelbststeuerungSelbstwahrnehmung
Komplette Unterrichtsstunde erstellen

Aktivität 02

Forschungskreis30 Min. · Kleingruppen

Small Group Simulation: Hash-Tabelle bauen

Gruppen erstellen eine Hash-Tabelle mit 10 Slots per Hand auf Papier, wenden eine einfache Hash-Funktion an und lösen Kollisionen durch Verkettung. Sie fügen 15 Elemente ein und analysieren Auslastung.

Erklären Sie das Funktionsprinzip der binären Suche und ihre Voraussetzungen.

ModerationstippVerteilen Sie in der Small Group Simulation konkrete Zahlenwerte und Schlüssel, damit die Schüler die Kollisionen direkt sichtbar machen können.

Worauf zu achten istStellen Sie die Frage: 'Unter welchen Umständen wäre die binäre Suche einer linearen Suche deutlich unterlegen, auch wenn die Daten sortiert sind?' Diskutieren Sie die Antworten und leiten Sie zur Bedeutung der Datenmenge und der Implementierungskosten über.

AnalysierenBewertenErschaffenSelbststeuerungSelbstwahrnehmung
Komplette Unterrichtsstunde erstellen

Aktivität 03

Forschungskreis50 Min. · Ganze Klasse

Whole Class Challenge: Effizienzvergleich

Klasse teilt sich in Teams: Ein Team simuliert lineare Suche, das andere binäre. Mit großen Listen (100 Elemente) zählen sie Schritte und präsentieren Ergebnisse auf dem Beamer.

Analysieren Sie, wie Hash-Kollisionen in Hash-Tabellen behandelt werden können.

ModerationstippFordern Sie die Gruppen im Whole Class Challenge auf, ihre Ergebnisse auf Folien zu notieren und zu vergleichen, um die Diskussion zu strukturieren.

Worauf zu achten istBitten Sie die Schüler, auf einem Zettel zu erklären, warum eine Hash-Kollision ein Problem darstellt und nennen Sie eine Methode, wie diese behoben werden kann. Bewerten Sie die Klarheit der Erklärung und die Korrektheit der genannten Methode.

AnalysierenBewertenErschaffenSelbststeuerungSelbstwahrnehmung
Komplette Unterrichtsstunde erstellen

Aktivität 04

Forschungskreis25 Min. · Einzelarbeit

Individual Experiment: Kollisionsstrategien

Jeder Schüler testet chaining vs. linear probing in Code mit zufälligen Daten. Er notiert Insert- und Search-Zeiten und diskutiert Vor- Nachteile.

Welche Rolle spielen vorsortierte Daten für die Effizienz von Suchalgorithmen?

ModerationstippBeobachten Sie während des Individual Experiments, wie die Schüler ihre Kollisionsstrategien dokumentieren, um gezielt nachzufragen.

Worauf zu achten istGeben Sie den Schülern eine kleine, sortierte Liste von Zahlen und einen Suchwert. Bitten Sie sie, die Schritte der binären Suche auf Papier nachzuvollziehen und den Mittelwert bei jedem Schritt zu notieren, bis das Element gefunden ist oder ausgeschlossen wird.

AnalysierenBewertenErschaffenSelbststeuerungSelbstwahrnehmung
Komplette Unterrichtsstunde erstellen

Vorlagen

Vorlagen, die zu diesen Informatik-Aktivitäten passen

Nutzen, bearbeiten, drucken oder teilen.

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte wissen, dass Schüler oft glauben, Algorithmen funktionieren immer gleich gut. Daher ist es wichtig, die Grundlagen greifbar zu machen: Lassen Sie die Schülerinnen und Schüler zunächst mit kleinen, überschaubaren Datenmengen arbeiten, bevor sie zu größeren Mengen übergehen. Vermeiden Sie zu frühe Abstraktion. Stattdessen sollte der Fokus auf dem schrittweisen Aufbau und der Reflexion der eigenen Handlungen liegen. Nutzen Sie Fehler als Lernchance und besprechen Sie gemeinsam, warum bestimmte Ansätze scheitern.

Erfolgreiches Lernen zeigt sich, wenn Schülerinnen und Schüler die Schritte der binären Suche und Hashing-Methoden selbstständig durchführen und erklären können. Sie erkennen die Bedeutung der Sortierung oder der Hash-Funktion und wenden Lösungsstrategien für Kollisionen korrekt an. Zudem können sie die Effizienz verschiedener Verfahren in konkreten Beispielen vergleichen und begründen.

Vorsicht vor diesen Fehlvorstellungen

  • Während der Pair Programming zur binären Suche beobachten Sie, dass einige Schüler annehmen, die Halbierung spare immer Zeit, unabhängig von der Sortierung.

    Geben Sie den Schülern eine unsortierte Liste und lassen Sie sie die binäre Suche durchführen. Sie werden merken, dass der Algorithmus versagt, und müssen selbst die Notwendigkeit der Sortierung erkennen.

  • Während der Small Group Simulation zur Hash-Tabelle übersehen einige, dass Kollisionen die Effizienz stark beeinträchtigen können.

    Fügen Sie gezielt viele Schlüssel hinzu, die auf denselben Index abgebildet werden, und lassen Sie die Schüler messen, wie sich die Suchzeit verlängert. Diskutieren Sie gemeinsam, wie gute Hash-Funktionen dies verhindern.

  • Während des Individual Experiments zu Kollisionsstrategien denken einige, dass jede Hash-Funktion gleich gut funktioniert.

    Lassen Sie die Schüler verschiedene Hash-Funktionen testen und vergleichen. Sie werden Clusterbildung erkennen und müssen selbstständig Verbesserungen vorschlagen.

In dieser Übersicht verwendete Methoden

Mehr in Datenstrukturen und Algorithmen

Grundlagen der Algorithmen

Die Schülerinnen und Schüler definieren Algorithmen und analysieren ihre Eigenschaften wie Endlichkeit, Eindeutigkeit und Effektivität.

2 methodologies

Arrays und Listen

Die Schülerinnen und Schüler vergleichen statische Arrays mit dynamischen Listen hinsichtlich ihrer Eigenschaften und Einsatzgebiete.

2 methodologies

Stacks und Queues

Die Schülerinnen und Schüler implementieren und analysieren die Funktionsweise von Stacks (LIFO) und Queues (FIFO) und deren Anwendungen.

2 methodologies

Binäre Bäume und Traversierung

Die Schülerinnen und Schüler untersuchen binäre Bäume als nicht-lineare Datenstrukturen und implementieren verschiedene Traversierungsverfahren.

2 methodologies

Graphen und ihre Darstellung

Die Schülerinnen und Schüler lernen Graphen als Modell für komplexe Beziehungen kennen und verschiedene Darstellungsformen (Adjazenzmatrix, Adjazenzliste).

2 methodologies