Informatik · Klasse 9 · Algorithmen und komplexe Datenstrukturen · 1. Halbjahr

Einfache Suchverfahren

Die Schülerinnen und Schüler implementieren und analysieren lineare Suchverfahren in Listen und bewerten deren Effizienz.

• KMK Bildungsstandards
• KMK: Sekundarstufe I - Algorithmen
• KMK: Sekundarstufe I - Problemlösen

Über dieses Thema

Die lineare Suche ist ein einfaches Verfahren, um ein Element in einer unsortierten Liste zu finden. Schülerinnen und Schüler lernen, die Liste sequentiell von vorne nach hinten zu durchlaufen, bis das gesuchte Element erscheint oder die Liste zu Ende ist. Sie implementieren den Algorithmus in Pseudocode oder Python, testen ihn mit Beispielen und analysieren seine Schritte. Dies entspricht den KMK-Standards zu Algorithmen und Problemlösen in der Sekundarstufe I. Die Key Questions fordern, die Funktionsweise zu erklären, Effizienz bei großen Datenmengen zu bewerten und den Algorithmus selbst zu konstruieren.

Im Unterrichtsthema 'Algorithmen und komplexe Datenstrukturen' bildet die lineare Suche die Grundlage für fortgeschrittene Methoden wie binäre Suche. Schüler erkennen, dass die Zeitkomplexität im Worst-Case O(n) beträgt, was bei großen Listen ineffizient ist. Sie diskutieren Anwendungen in Alltagsszenarien, etwa bei kleinen Datenbanken oder Echtzeit-Suchen, und vergleichen Vor- und Nachteile. So entsteht Verständnis für algorithmische Effizienz als zentrales Konzept der Informatik.

Aktives Lernen passt ideal, weil Schüler Algorithmen selbst programmieren, mit variierenden Listengrößen messen und Ergebnisse visualisieren können. Solche praktischen Experimente machen abstrakte Komplexitäten konkret, fördern Fehleranalyse und bauen echtes Problemlösevermögen auf. (178 Wörter)

Leitfragen

1. Erklären Sie die Funktionsweise der linearen Suche und ihre Anwendungsbereiche.
2. Bewerten Sie die Effizienz der linearen Suche bei großen Datenmengen.
3. Konstruieren Sie einen Algorithmus zur Suche eines Elements in einer unsortierten Liste.

Lernziele

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

Bevor es losgeht

Grundlagen der Programmierung (Variablen, Datentypen, Schleifen)

Warum: Schüler müssen grundlegende Programmierkonzepte wie Variablen, Datentypen (insbesondere Listen/Arrays) und Kontrollstrukturen (wie for-Schleifen) verstehen, um den Algorithmus implementieren zu können.

Einführung in Algorithmen

Warum: Ein grundlegendes Verständnis davon, was ein Algorithmus ist und wie er schrittweise Probleme löst, ist notwendig, um die lineare Suche als spezifischen Algorithmus zu begreifen.

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.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Lineare Suche erfordert eine sortierte Liste.

Was Sie stattdessen lehren sollten

Lineare Suche funktioniert bei unsortierten Listen, da sie sequentiell prüft. Aktive Codierübungen in Paaren zeigen dies direkt: Schüler testen sortierte und unsortierte Eingaben und sehen gleiche Funktionsweise, was Vorurteile abbaut.

Häufige Fehlvorstellung

Lineare Suche ist immer die schnellste Methode.

Was Sie stattdessen lehren sollten

Bei großen Listen ist sie ineffizient mit O(n)-Komplexität. Simulationsspiele mit wachsenden Stapeln lassen Schüler die zunehmende Zeit spüren und vergleichen mit Alternativen, fördert nuanciertes Bewerten.

Häufige Fehlvorstellung

Die Effizienz hängt nur von der Hardware ab.

Was Sie stattdessen lehren sollten

Effizienz wird durch Algorithmus bestimmt, nicht primär Hardware. Gruppenexperimente mit Timern bei gleicher Hardware machen dies evident und trainieren analytisches Denken.

Ideen für aktives Lernen

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.

35 Min.·Partnerarbeit

Gruppensimulation: Karten-Suche

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

25 Min.·Kleingruppen

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.

45 Min.·Ganze Klasse

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.

20 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• Ein Bibliothekar sucht in einem kleinen, nicht digitalisierten Katalog nach einem bestimmten Buch. Er muss jedes Regal durchgehen und jedes Buch einzeln prüfen, bis er das gesuchte findet.
• Ein Kundendienstmitarbeiter sucht in einer kurzen Liste von Support-Tickets nach einer spezifischen Ticket-ID, um den Status zu überprüfen. Da die Liste kurz ist, ist eine einfache, sequentielle Durchsicht am schnellsten zu implementieren.
• Bei der Suche nach einem bestimmten Wort in einem kurzen Textdokument, das nicht alphabetisch sortiert ist, wird im Grunde eine lineare Suche durchgeführt, indem jedes Wort einzeln betrachtet wird.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Geben Sie den Schülern eine kleine, unsortierte Liste (z.B. [5, 12, 3, 8, 1]) und eine zu suchende Zahl (z.B. 8). Bitten Sie sie, auf einem Blatt Papier jeden Schritt der linearen Suche aufzuschreiben, bis die Zahl gefunden ist, und die Anzahl der Vergleiche zu notieren.

Diskussionsfrage

Stellen Sie die Frage: 'Unter welchen Umständen ist die lineare Suche eine sinnvolle Methode, um Daten zu finden, und wann sollten wir uns nach effizienteren Algorithmen umsehen?' Diskutieren Sie die Antworten der Schüler und leiten Sie zur Effizienzbetrachtung über.

Lernstandskontrolle

Bitten Sie die Schüler, zwei Sätze zu schreiben: Der erste Satz soll erklären, wann die lineare Suche am schnellsten ist. Der zweite Satz soll ein Beispiel für eine Situation nennen, in der die lineare Suche trotz ihrer Ineffizienz bei großen Datenmengen dennoch praktisch ist.

Häufig gestellte Fragen

Was ist die Funktionsweise der linearen Suche?

Die lineare Suche durchläuft eine unsortierte Liste schrittweise von Index 0 bis Ende. Bei jedem Element wird geprüft, ob es dem Gesuchten entspricht; bei Treffer wird der Index zurückgegeben, sonst signalisiert 'nicht gefunden'. In Python sieht der Code so aus: for i in range(len(liste)): if liste[i] == ziel: return i. return -1. Diese Einfachheit eignet sich für kleine Datensätze. (72 Wörter)

Wie bewertet man die Effizienz der linearen Suche?

Effizienz misst sich an Zeit- und Raumkomplexität: Worst-Case O(n) Vergleiche, Best-Case O(1). Bei 1.000 Elementen bis zu 1.000 Schritte. Praktische Tests mit Timern zeigen Skalierbarkeitsprobleme. Für große Mengen sind binäre Suche oder Hash-Tabellen vorzuziehen. Schüler lernen durch Messungen, wann linear akzeptabel ist. (68 Wörter)

Wie kann aktives Lernen die lineare Suche verständlich machen?

Aktives Lernen aktiviert durch Codieren in Paaren, manuelle Simulationen mit Karten und Klassen-Timer-Challenges. Schüler messen selbst Laufzeiten bei wachsenden Listen, visualisieren O(n) in Diagrammen und debuggen Fehler. Diese Hände-auf-Methoden wandeln Theorie in Erfahrung um, stärken Problemlösen und machen Effizienz greifbar, statt passiv vorzutragen. (74 Wörter)

In welchen Anwendungsbereichen eignet sich lineare Suche?

Ideal für kleine, unsortierte Listen wie Adressbücher mit wenigen Einträgen oder Echtzeit-Suchen in Spielen. Nicht für Millionen-Datensätze wie Suchmaschinen. Schüler erkunden via Fallstudien: Bibliothekskatalog klein vs. Web-Index groß. Implementierung trainiert Basis für fortgeschrittene Algorithmen. (62 Wörter)