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.

• Klasse 13
• Informatik Oberstufe: Komplexe Systeme und Theoretische Grundlagen
• 4 Aktivitäten
• 30 Min.–50 Min.

Lernziele

1. Vergleichen Sie die Laufzeitkomplexität von linearer Suche, binärer Suche und Hashing für verschiedene Datengrößen.
2. Erklären Sie die notwendigen Datenstrukturbedingungen für die effiziente Anwendung der binären Suche.
3. Analysieren Sie die Auswirkungen von Kollisionen auf die Leistung von Hashing-Algorithmen.
4. Bewerten Sie die Eignung verschiedener Suchverfahren für spezifische Anwendungsfälle, z.B. Datenbankabfragen.
5. Entwerfen Sie ein einfaches Hashing-Schema zur Speicherung und zum Abruf von Schlüssel-Wert-Paaren.

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.

Vorbereitung & Details

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.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

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.

Vorbereitung & Details

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.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

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.

Vorbereitung & Details

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.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

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.

Vorbereitung & Details

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.

Setup: Gruppentische mit Zugang zu Quellenmaterialien

Materials: Quellensammlung, Arbeitsblatt zum Forschungszyklus, Leitfaden zur Fragestellung, Vorlage für die Ergebnispräsentation

• Analysieren
• Bewerten
• Erschaffen
• Selbststeuerung
• Selbstwahrnehmung

Dieses Thema unterrichten

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.

Was Sie erwartet

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

Häufige Fehlvorstellung

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

Was Sie stattdessen lehren sollten

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.

Häufige Fehlvorstellung

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

Was Sie stattdessen lehren sollten

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.

Häufige Fehlvorstellung

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

Was Sie stattdessen lehren sollten

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.

Ideen zur Lernstandserhebung

Kurze Überprüfung

After der Programmier-Stationen zeigen Sie den Schülern drei kurze Code-Snippets: 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.

Diskussionsfrage

During der Karten-Suche 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.

Lernstandskontrolle

After der Hashing-Challenge erhält jeder Schüler 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.

Erweiterungen & Unterstützung

• Fordern Sie schnelle Schüler auf, eine eigene Implementierung zu entwickeln, die eine Kombination aus binärer Suche und Hashing nutzt.
• Schüler mit Schwierigkeiten erhalten eine vorgefertigte Tabelle, in der sie die Zeitkomplexitäten der Verfahren für verschiedene Listengrößen eintragen müssen.
• Vertiefen Sie die Thematik, indem Sie eine Diskussion über die Anwendbarkeit der Suchverfahren in der Künstlichen Intelligenz anregen, etwa bei Entscheidungsbäumen oder neuronalen Netzen.

Schlüsselvokabular

Lineare Suche	Ein einfacher Suchalgorithmus, der jedes Element einer Liste nacheinander prüft, bis das gesuchte Element gefunden wird oder die Liste endet. Seine Zeitkomplexität ist O(n).
Binäre Suche	Ein effizienter Suchalgorithmus für sortierte Listen, der die Suchmenge wiederholt halbiert. Seine Zeitkomplexität ist O(log n).
Hashing	Eine Technik, die eine Funktion (Hash-Funktion) verwendet, um einen Schlüssel direkt auf einen Speicherort abzubilden. Im Idealfall ermöglicht dies einen konstanten Zeitaufwand O(1) für Suchen, Einfügen und Löschen.
Kollision (Hashing)	Ein Ereignis beim Hashing, bei dem zwei verschiedene Schlüssel durch die Hash-Funktion auf denselben Speicherort abgebildet werden. Dies erfordert spezielle Handhabungsstrategien.
Hash-Funktion	Eine Funktion, die beliebige Eingabedaten (Schlüssel) in eine feste Größe von Ausgabedaten (Hash-Wert oder Index) umwandelt. Eine gute Hash-Funktion verteilt Schlüssel gleichmäßig.