Informatik · Klasse 11

Ideen für aktives Lernen

Suchalgorithmen: Linear und Binär

Aktive Lernformen eignen sich besonders gut, um Suchalgorithmen zu verstehen, weil Schüler die Unterschiede zwischen linearer und binärer Suche nicht nur theoretisch nachvollziehen, sondern durch eigenes Handeln erfahren können. Die manuelle Simulation und der direkte Vergleich zeigen, warum Effizienz von Datenmenge und Vorbereitung abhängt. So wird Abstraktes greifbar und nachhaltig verankert.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen entwerfen
• KMK: Sekundarstufe II - Implementieren

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

Aktivität 01

• Planspiel
• 30 Min. · Kleingruppen

Planspiel: Manuelle Suche

Teilen Sie Karten mit Zahlen an Gruppen aus. Führen Sie lineare Suche durch Sequentielles Durchsuchen durch, notieren Sie Schritte. Wiederholen Sie mit sortierter Liste und binärer Suche, vergleichen Sie die Anzahl der Prüfungen. Diskutieren Sie Ergebnisse in der Gruppe.

Wie verändert die Vorsortierung von Daten die Geschwindigkeit einer Suche?

Moderationstipp

Während der manuellen Suche lassen Sie Schüler die Anzahl der Schritte laut mitzählen, um die O(n)-Komplexität direkt erlebbar zu machen.

Worauf zu achten ist

Geben Sie den Schülern eine kleine, unsortierte Liste von Zahlen und eine Zielzahl. Lassen Sie sie die Schritte einer linearen Suche aufschreiben, um die Zahl zu finden. Fragen Sie anschließend: 'Wie viele Vergleiche waren nötig?'

• Anwenden
• Analysieren
• Bewerten
• Erschaffen
• Sozialbewusstsein
• Entscheidungsfähigkeit

Aktivität 02

• Lernen an Stationen
• 45 Min. · Partnerarbeit

Coding Challenge: Python-Implementierung

Schüler implementieren lineare und binäre Suche in Python. Testen Sie mit Listen unterschiedlicher Größe und Sortierung. Messen Sie Laufzeiten mit time-Modul und plotten Sie Grafiken. Präsentieren Sie beste Fälle.

Vergleichen Sie die Effizienz von linearer und binärer Suche unter verschiedenen Bedingungen.

Moderationstipp

Fordern Sie in der Coding Challenge die Schüler auf, ihre Implementierungen mit einer Stoppuhr zu testen, um den Unterschied zwischen O(n) und O(log n) quantitativ zu erfassen.

Worauf zu achten ist

Stellen Sie die Frage: 'Unter welchen Umständen wäre eine lineare Suche trotz ihrer geringeren Effizienz bei großen Datensätzen die bessere Wahl als eine binäre Suche?' Lassen Sie die Schüler Beispiele wie sehr kleine Listen oder einmalige Suchen in nicht sortierbaren Daten nennen und begründen.

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Aktivität 03

• Lernen an Stationen
• 50 Min. · Kleingruppen

Effizienz-Wettbewerb

Erstellen Sie große Listen mit Zufallsdaten. Gruppen sortieren mit Bubble Sort, dann suchen. Wettkampf um schnellste Gesamtlaufzeit. Analysieren Sie, warum lineare Suche bei kleinen Listen gewinnt.

Begründen Sie, wann eine lineare Suche trotz geringerer Effizienz die bessere Wahl sein kann.

Moderationstipp

Beim Effizienz-Wettbewerb verteilen Sie Listen unterschiedlicher Größe, um zu zeigen, dass lineare Suche bei kleinen Datenmengen schneller sein kann.

Worauf zu achten ist

Bitten Sie die Schüler, auf einem Zettel zwei Szenarien zu beschreiben: Ein Szenario, in dem die binäre Suche klar überlegen ist, und ein Szenario, in dem die lineare Suche ausreicht oder sogar vorteilhaft ist. Sie sollen jeweils kurz begründen, warum.

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Aktivität 04

• Lernen an Stationen
• 35 Min. · Ganze Klasse

Visualisierung: Schritt-für-Schritt

Nutzen Sie Online-Tools wie VisuAlgo. Schüler führen binäre Suche schrittweise aus, markieren Suchraum. Erstellen Sie Screenshots und erklären Sie in Plenum, warum Halbierung effizient ist.

Wie verändert die Vorsortierung von Daten die Geschwindigkeit einer Suche?

Moderationstipp

Lassen Sie bei der Visualisierung die Schüler die Teilungsschritte der binären Suche an der Tafel nachzeichnen, um das Prinzip der Halbierung zu verinnerlichen.

Worauf zu achten ist

Geben Sie den Schülern eine kleine, unsortierte Liste von Zahlen und eine Zielzahl. Lassen Sie sie die Schritte einer linearen Suche aufschreiben, um die Zahl zu finden. Fragen Sie anschließend: 'Wie viele Vergleiche waren nötig?'

• Erinnern
• Verstehen
• Anwenden
• Analysieren
• Selbststeuerung
• Beziehungsfähigkeit

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit der Simulation, um das Grundprinzip beider Algorithmen zu verankern. Anschließend setzen sie die Implementierung in Code um, um die Brücke zwischen Theorie und Praxis zu schlagen. Wichtig ist, immer wieder auf die Voraussetzungen hinzuweisen: Binäre Suche braucht Sortierung, lineare Suche nicht. Vermeiden Sie es, die Komplexität nur abstrakt zu erklären – messbare Beispiele zeigen den Unterschied klarer.

Am Ende sollen die Schüler den Unterschied zwischen linearer und binärer Suche nicht nur erklären, sondern auch praktisch anwenden können. Sie erkennen, wann welche Methode sinnvoll ist und können die Zeitkomplexität mit eigenen Messungen begründen. Die Diskussion zeigt, dass sie Bedingungen für Effizienz kritisch hinterfragen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während des Effizienz-Wettbewerbs beobachten Sie, dass einige Schüler glauben, binäre Suche sei immer schneller.

  Führen Sie nach dem Wettbewerb eine kurze Diskussion an, in der die Schüler ihre Messergebnisse vergleichen. Lassen Sie sie erklären, warum lineare Suche bei kleinen Listen (z.B. unter 20 Elementen) oft schneller ist und welche Rolle die Vorbereitungszeit von Bubble Sort spielt.

• Während der Python-Implementierung hören Sie Schüler sagen, die Zeitkomplexität hänge vom verwendeten Computer ab.

  Lassen Sie die Schüler ihre Programme mit Listen unterschiedlicher Größen (z.B. 1.000, 10.000, 100.000 Elemente) ausführen und die Laufzeiten notieren. Zeigen Sie, dass sich das Verhältnis der Laufzeiten (z.B. 10:1) unabhängig vom Rechner bestätigt.

• Während der Simulation mit Karten wird Bubble Sort als irrelevant für Suchalgorithmen abgetan.

  Lassen Sie die Schüler die sortierte Liste nach dem Bubble-Sort-Schritt mit der ursprünglichen vergleichen. Fordern Sie sie auf, die Anzahl der Vertauschungen zu zählen und zu berechnen, wie sich diese auf die Gesamtzeit auswirken, wenn eine binäre Suche folgt.

---

In dieser Übersicht verwendete Methoden

• Planspiel
• Lernen an Stationen