Einfache Suchverfahren

Aktive Lernformen eignen sich besonders hier, weil das Thema Suchverfahren abstrakt ist und Schülerinnen und Schüler durch eigenes Handeln ein echtes Verständnis entwickeln müssen. Die Kombination aus Programmierübungen, Simulationen und Diskussionen fördert sowohl die kognitive als auch die praktische Auseinandersetzung mit dem Algorithmus. Theorie wird so direkt mit Anwendung verknüpft.

• Klasse 9
• Digitale Welten Gestalten: Informatik und Gesellschaft
• 4 Aktivitäten
• 20 Min.–45 Min.

Lernziele

1. Demonstrieren Sie die schrittweise Ausführung eines linearen Suchalgorithmus für eine gegebene unsortierte Liste und ein Suchkriterium.
2. Analysieren Sie die Anzahl der Vergleiche, die für eine lineare Suche in verschiedenen Szenarien (best, worst, average case) benötigt werden.
3. Erstellen Sie einen Python-Code, der eine lineare Suche in einer Liste implementiert.
4. Bewerten Sie die Effizienz der linearen Suche im Vergleich zu anderen Suchverfahren für unsortierte Datenmengen.
5. Erklären Sie die Anwendungsbereiche der linearen Suche, insbesondere bei kleinen oder dynamischen Datensätzen.

Forschungskreis

⏱ 35 Min.·Partnerarbeit

Paarprogrammierung: Lineare Suche coden

Paare schreiben eine Python-Funktion für lineare Suche. Sie testen mit unsortierten Listen unterschiedlicher Länge und notieren Fundpositionen. Abschließend vergleichen sie Laufzeiten mit time-Modul.

Vorbereitung & Details

Erklären Sie die Funktionsweise der linearen Suche und ihre Anwendungsbereiche.

Moderationstipp: Achten Sie bei der Paarprogrammierung darauf, dass beide Partner abwechselnd codieren und erklären, um sicherzustellen, dass alle aktiv mitdenken.

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

⏱ 25 Min.·Kleingruppen

Gruppensimulation: Karten-Suche

Kleingruppen sortieren keine Kartenstapel und suchen ein Zielkarte manuell durch. Jede Runde mit mehr Karten, Beobachtung der Schritte. Protokollieren der Durchsuchzeit.

Vorbereitung & Details

Bewerten Sie die Effizienz der linearen Suche bei großen Datenmengen.

Moderationstipp: Legen Sie bei der Gruppensimulation klare Regeln fest, z.B. dass die Gruppe nur gemeinsam entscheiden darf, ob der gesuchte Begriff gefunden wurde.

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

⏱ 45 Min.·Ganze Klasse

Whole-Class-Challenge: Effizienz messen

Klasse teilt große Listen-Datensätze. Jeder testet lineare Suche und misst Zeit mit Stopwatch. Gemeinsam plotten Ergebnisse in Diagramm für O(n)-Kurve.

Vorbereitung & Details

Konstruieren Sie einen Algorithmus zur Suche eines Elements in einer unsortierten Liste.

Moderationstipp: Verwenden Sie bei der Whole-Class-Challenge Stoppuhren mit sichtbarer Anzeige, damit die Schüler die Zeitmessung direkt nachvollziehen können.

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

⏱ 20 Min.·Einzelarbeit

Individual-Aufgabe: Algorithmus erweitern

Jeder Schüler modifiziert Code für Zählung von Vergleichen. Testen mit 10, 100, 1000 Elementen und Bewertung der Skalierbarkeit in Bericht.

Vorbereitung & Details

Erklären Sie die Funktionsweise der linearen Suche und ihre Anwendungsbereiche.

Moderationstipp: Fordern Sie bei der Individual-Aufgabe explizit auf, die Erweiterungen schriftlich zu dokumentieren, um den Lernprozess nachvollziehbar zu machen.

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

Beginne mit einer realen Analogie, z.B. dem Suchen eines Namens in einem ungeordneten Telefonbuch, um die Notwendigkeit des sequentiellen Durchsuchens zu verdeutlichen. Vermeide es, den Algorithmus nur theoretisch zu erklären – stattdessen sollten Schüler ihn von Anfang an selbst ausprobieren. Nutze Fehlermeldungen und Debugging als natürliche Lerngelegenheiten, um das Verständnis zu vertiefen. Forschung zeigt, dass Schüler Algorithmen besser verstehen, wenn sie sie selbst implementieren und mit unterschiedlichen Eingaben testen.

Was Sie erwartet

Erfolgreiches Lernen zeigt sich darin, dass Schülerinnen und Schüler den linearen Suchalgorithmus nicht nur korrekt anwenden, sondern auch seine Funktionsweise erklären und seine Grenzen erkennen können. Sie sollen in der Lage sein, den Algorithmus in Pseudocode oder Python umzusetzen, seine Effizienz einzuschätzen und alternative Methoden zu begründen. Die Fähigkeit, Fehler zu identifizieren und zu korrigieren, ist ebenfalls ein zentrales Kriterium.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

During der Individual-Aufgabe: Lineare Suche erfordert eine sortierte Liste.

Was Sie stattdessen lehren sollten

Zeigen Sie den Schülern während der Codierübung explizit, dass die lineare Suche bei unsortierten Listen funktioniert, indem Sie ihnen eine unsortierte Eingabeliste zum Testen geben und das Ergebnis mit einer sortierten Liste vergleichen lassen.

Häufige Fehlvorstellung

During der Whole-Class-Challenge: Lineare Suche ist immer die schnellste Methode.

Was Sie stattdessen lehren sollten

Nutzen Sie die wachsenden Suchstapel in der Simulation, um den Schülern zu verdeutlichen, dass die Zeit linear mit der Listenlänge steigt, und vergleichen Sie dies mit dem Gefühl, das sie bei einer sortierten Liste hätten, um die Ineffizienz zu verdeutlichen.

Häufige Fehlvorstellung

During der Gruppensimulation: Die Effizienz hängt nur von der Hardware ab.

Was Sie stattdessen lehren sollten

Führen Sie die Simulation mit einem Timer durch und halten Sie die Hardware konstant, um zu zeigen, dass die Laufzeit direkt vom Algorithmus abhängt und nicht von der Technik.

Ideen zur Lernstandserhebung

Kurze Überprüfung

After der Gruppensimulation: Geben Sie den Schülern eine unsortierte Liste und eine zu suchende Zahl vor. Bitten Sie sie, die Schritte der linearen Suche schriftlich zu dokumentieren und die Anzahl der Vergleiche zu notieren, um die korrekte Anwendung des Algorithmus zu überprüfen.

Diskussionsfrage

After der Whole-Class-Challenge: Stellen Sie die Frage: 'In welchen Situationen ist die lineare Suche trotz ihrer Ineffizienz praktikabel?' und leiten Sie eine Diskussion an, in der Schüler Beispiele nennen und ihre Entscheidungen begründen.

Lernstandskontrolle

During der Individual-Aufgabe: Bitten Sie die Schüler, zwei Sätze zu formulieren: Der erste soll erklären, wann die lineare Suche am schnellsten ist, und der zweite ein Beispiel nennen, in dem sie trotz Ineffizienz sinnvoll eingesetzt wird.

Erweiterungen & Unterstützung

• Fordere schnelle Schüler auf, eine verbesserte Version des Algorithmus zu entwickeln, die nach dem ersten Treffer abbricht, und erkläre, warum dies die Effizienz steigert.
• Biete Schülern, die Schwierigkeiten haben, eine vorbereitete Liste mit bereits markierten Vergleichsschritten an, die sie als Vorlage nutzen können.
• Ermutige interessierte Schüler, eine grafische Visualisierung des Algorithmus zu erstellen, z.B. mit einem Flussdiagramm oder einer Animation, um die Schritte nachhaltig zu verankern.

Schlüsselvokabular

Lineare Suche	Ein Suchalgorithmus, der eine Liste Element für Element von Anfang bis Ende durchläuft, bis das gesuchte Element gefunden wird oder die Liste erschöpft ist.
Sequentielle Suche	Ein Synonym für lineare Suche, das den schrittweisen, nacheinander erfolgenden Durchlauf der Datenstruktur betont.
Zeitkomplexität	Ein Maß dafür, wie die Laufzeit eines Algorithmus mit der Größe der Eingabedaten wächst. Bei der linearen Suche ist dies im schlechtesten Fall O(n).
Best Case / Worst Case	Beschreibt das günstigste bzw. ungünstigste Szenario für die Ausführung eines Algorithmus. Bei linearer Suche ist der Best Case 1 Vergleich (Element am Anfang), der Worst Case n Vergleiche (Element am Ende oder nicht vorhanden).
Unsortierte Liste	Eine Datenstruktur, bei der die Elemente keine feste Reihenfolge aufweisen, was bedeutet, dass ein Element nicht anhand seiner Position vorhergesagt werden kann.