Informatik · Klasse 13

Ideen für aktives Lernen

Suchverfahren im Vergleich

Aktives Ausprobieren hilft Schülerinnen und Schülern, die abstrakten Konzepte der Suchverfahren greifbar zu machen und nachhaltig zu verinnerlichen. Durch das direkte Implementieren und Simulieren der Algorithmen erleben sie selbst, warum bestimmte Verfahren unter bestimmten Bedingungen besser geeignet sind als andere.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen
• KMK: Sekundarstufe II - Modellieren und Implementieren

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

Aktivität 01

• Forschungskreis
• 50 Min. · Kleingruppen

Programmier-Stationen: Algorithmen implementieren

Schüler implementieren lineare Suche, binäre Suche und einfaches Hashing in Python. Sie testen jeden Algorithmus mit Arrays von 10 bis 10.000 Elementen und protokollieren Laufzeiten. In der Schlussphase vergleichen Gruppen ihre Ergebnisse grafisch.

Vergleichen Sie die Effizienz von linearer Suche, binärer Suche und Hashing.

Moderationstipp

Während der Programmier-Stationen darauf achten, dass jeder Schüler die Implementierung Schritt für Schritt nachvollzieht und nicht einfach Code kopiert.

Worauf zu achten ist

Stellen Sie den Schülern drei kurze Code-Snippets vor: eines für lineare Suche, eines für binäre Suche und eines für eine einfache Hashing-Implementierung. Bitten Sie sie, für jedes Snippet die erwartete Zeitkomplexität für eine Suche in einer Liste mit 1000 Elementen anzugeben und kurz zu begründen.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Aktivität 02

• Forschungskreis
• 30 Min. · Partnerarbeit

Karten-Suche: Simulation binärer und linearer Suche

Teilen Sie sortierte und unsortierte Kartensets aus. Paare führen lineare und binäre Suche durch und zählen Suchschritte. Nach 10 Runden diskutieren sie Voraussetzungen und Effizienz.

Erklären Sie die Voraussetzungen für die Anwendung der binären Suche.

Moderationstipp

Bei der Karten-Suche die Schüler auffordern, ihre Beobachtungen schriftlich festzuhalten, um die Unterschiede zwischen linearer und binärer Suche klar herauszuarbeiten.

Worauf zu achten ist

Geben Sie den Schülern die Aufgabe, ein Szenario zu beschreiben, in dem die binäre Suche aufgrund fehlender Voraussetzungen (z.B. unsortierte Daten) ungeeignet wäre. Diskutieren Sie anschließend, welche alternativen Suchverfahren in diesem Fall effizienter wären und warum.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Aktivität 03

• Forschungskreis
• 40 Min. · Kleingruppen

Hashing-Challenge: Kollisionsbehandlung

Schüler bauen eine Hash-Tabelle mit Listen für Kollisionen und füllen sie mit 50 Wörtern. Sie messen Zugriffszeiten und vergleichen mit linearer Suche. Gemeinsam optimieren sie den Hash-Faktor.

Analysieren Sie die Rolle von Heuristiken bei der Lösung komplexer Suchprobleme.

Moderationstipp

In der Hashing-Challenge gezielt Gruppen bilden, die unterschiedliche Strategien zur Kollisionsbehandlung ausprobieren und vergleichen.

Worauf zu achten ist

Jeder Schüler erhält eine Karte mit einer der folgenden Fragen: 'Welche Datenstruktur ist für die binäre Suche zwingend erforderlich und warum?' oder 'Nennen Sie eine Methode zur Behandlung von Kollisionen beim Hashing und erklären Sie kurz, wie sie funktioniert.' Die Antworten werden eingesammelt.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Aktivität 04

• Forschungskreis
• 35 Min. · Kleingruppen

Heuristik-Diskussion: Labyrinth-Suche

Gruppen lösen Labyrinth-Rätsel mit Greedy- und A*-Heuristiken auf Papier. Sie notieren Schritte und vergleichen mit exhaustiver Suche, um heuristische Vorteile zu erkennen.

Vergleichen Sie die Effizienz von linearer Suche, binärer Suche und Hashing.

Moderationstipp

Bei der Heuristik-Diskussion darauf achten, dass die Schüler nicht nur Lösungen präsentieren, sondern auch ihre Entscheidungen für bestimmte Heuristiken begründen.

Worauf zu achten ist

Stellen Sie den Schülern drei kurze Code-Snippets vor: eines für lineare Suche, eines für binäre Suche und eines für eine einfache Hashing-Implementierung. Bitten Sie sie, für jedes Snippet die erwartete Zeitkomplexität für eine Suche in einer Liste mit 1000 Elementen anzugeben und kurz zu begründen.

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte setzen bei diesem Thema auf eine Kombination aus Hands-On-Aktivitäten und gezielten Reflexionsphasen. Sie vermeiden es, die Algorithmen nur theoretisch zu erklären, sondern lassen die Schüler die Vor- und Nachteile selbst erarbeiten. Wichtig ist, immer wieder den Bezug zur Praxis herzustellen, etwa durch Alltagsbeispiele oder reale Datenmengen.

Am Ende der Einheit können die Schülerinnen und Schüler die drei Suchverfahren in Bezug auf ihre Effizienz und Voraussetzungen vergleichen und ihr Wissen auf neue Szenarien anwenden. Sie erkennen, dass die Wahl des Verfahrens von der Datenstruktur und dem Kontext abhängt.

---

Vorsicht vor diesen Fehlvorstellungen

• During der Karten-Suche, watch for Schüler, die annehmen, die binäre Suche sei immer die schnellere Option.

  Nutzen Sie die Karten-Simulation gezielt, um die Voraussetzung der sortierten Liste zu betonen: Lassen Sie die Schüler die binäre Suche auf einem unsortierten Stapel ausprobieren und beobachten, wie sie scheitert oder ineffizient wird. Diskutieren Sie anschließend, warum Sortierung hier entscheidend ist.

• During der Hashing-Challenge, watch for Schüler, die glauben, Hashing habe immer konstante Laufzeit.

  Nutzen Sie die praktischen Tests mit unterschiedlichen Datenmengen, um zu zeigen, dass Kollisionen die Laufzeit verschlechtern. Lassen Sie die Schüler selbst Kollisionen provozieren und messen, wie sich die Zeit verändert.

• During der Heuristik-Diskussion, watch for Schüler, die annehmen, Heuristiken führten immer zur optimalen Lösung.

  Nutzen Sie das Labyrinth-Szenario, um zu verdeutlichen, dass Heuristiken Kompromisse eingehen. Lassen Sie die Schüler verschiedene Heuristiken testen und deren Ergebnisse vergleichen, um die Trade-offs zwischen Geschwindigkeit und Qualität zu erkennen.

---

In dieser Übersicht verwendete Methoden

• Forschungskreis