Informatik · Klasse 9

Ideen für aktives Lernen

Binäre Suche und Effizienz

Aktive Lernmethoden wie Paarprogrammierung oder physische Experimente machen die abstrakte Komplexität der binären Suche für Schülerinnen und Schüler greifbar. Durch die Kombination von Code, Bewegung und Wettbewerb erkennen sie selbst, warum dieser Algorithmus effizient ist und welche Rolle Sortierung dabei spielt.

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

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

Aktivität 01

• Problemorientiertes Lernen
• 45 Min. · Partnerarbeit

Paarprogrammierung: Binäre vs. Lineare Suche

In Paaren implementieren Schüler beide Algorithmen in Python für eine Liste von 1000 Zahlen. Sie messen die Vergleichszahlen mit print-Anweisungen und vergleichen die Ergebnisse in einer Tabelle. Abschließend diskutieren sie den Effizienzunterschied.

Vergleichen Sie die Effizienz der binären Suche mit der linearen Suche.

Moderationstipp

Fordern Sie die Teams in der Paarprogrammierung auf, ihre Implementierungen direkt mit Laufzeitmessungen zu testen und zu dokumentieren, um den Effizienzunterschied sichtbar zu machen.

Worauf zu achten ist

Die Schüler erhalten eine Liste von 10 Zahlen, die nicht sortiert ist, und eine sortierte Liste von 10 Zahlen. Sie sollen für jede Liste die Anzahl der Schritte schätzen, die eine lineare bzw. eine binäre Suche benötigen würde, um die Zahl 7 zu finden. Notieren Sie Ihre Schätzungen und eine kurze Begründung.

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Aktivität 02

• Lernen an Stationen
• 50 Min. · Kleingruppen

Lernen an Stationen: Physische Suche

Richten Sie Stationen ein: Sortieren von Karten, lineare Suche, binäre Suche und Effizienzvergleich mit Stoppuhr. Gruppen rotieren, protokollieren Suchzeiten und ziehen Rückschlüsse auf Skalierbarkeit.

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

Moderationstipp

Stellen Sie bei den Stationsarbeiten sicher, dass die Schülerinnen und Schüler die Sortiervoraussetzung durch das Scheitern mit unsortierten Karten selbst erleben und diskutieren.

Worauf zu achten ist

Stellen Sie den Schülern eine unsortierte Liste und eine sortierte Liste von jeweils 16 Elementen vor. Bitten Sie sie, den Algorithmus der binären Suche auf die sortierte Liste anzuwenden, um ein bestimmtes Element zu finden, und notieren Sie dabei jeden Vergleichsschritt. Vergleichen Sie anschließend die Anzahl der Schritte mit der maximal möglichen Anzahl bei einer linearen Suche.

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

Aktivität 03

• Problemorientiertes Lernen
• 35 Min. · Kleingruppen

Klassenwettbewerb: Such-Challenge

Teilen Sie eine große sortierte Liste aus. Teams wählen Strategie (linear oder binär), suchen Begriffe und messen kollektiv Zeiten. Die Klasse grafisch auswertend, gewinnt das effizienteste Team.

Begründen Sie, warum die Sortierung von Daten die Grundlage für schnelle Suche ist.

Moderationstipp

Legen Sie beim Klassenwettbewerb klare Regeln für die Laufzeitmessung fest, damit die Ergebnisse vergleichbar sind und die Effizienzunterschiede deutlich werden.

Worauf zu achten ist

Diskutieren Sie in Kleingruppen: Warum ist die binäre Suche so viel schneller als die lineare Suche, wenn die Daten sortiert sind? Nennen Sie ein Beispiel aus Ihrem Alltag, wo eine schnelle Suche wichtig ist und wie die Daten dafür sortiert sein könnten.

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Aktivität 04

• Problemorientiertes Lernen
• 30 Min. · Einzelarbeit

Individuell: Laufzeitanalyse

Jeder Schüler erzeugt Listen unterschiedlicher Größe, codet binäre Suche und plottet Vergleiche mit Matplotlib. Sie begründen Vor- und Nachteile gegenüber linearer Suche.

Vergleichen Sie die Effizienz der binären Suche mit der linearen Suche.

Moderationstipp

Ermutigen Sie die Lernenden während der Laufzeitanalyse, ihre Messergebnisse in Tabellen oder Diagrammen festzuhalten, um Muster zu erkennen.

Worauf zu achten ist

Die Schüler erhalten eine Liste von 10 Zahlen, die nicht sortiert ist, und eine sortierte Liste von 10 Zahlen. Sie sollen für jede Liste die Anzahl der Schritte schätzen, die eine lineare bzw. eine binäre Suche benötigen würde, um die Zahl 7 zu finden. Notieren Sie Ihre Schätzungen und eine kurze Begründung.

• Analysieren
• Bewerten
• Erschaffen
• Entscheidungsfähigkeit
• Selbststeuerung
• Beziehungsfähigkeit

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte beginnen mit konkreten, greifbaren Beispielen, bevor sie zur abstrakten Laufzeitanalyse übergehen. Sie vermeiden es, den Algorithmus nur theoretisch zu erklären, und setzen stattdessen auf Hands-on-Aktivitäten, die die Schülerinnen und Schüler aktiv einbinden. Wichtig ist, dass die Lernenden selbst die Effizienzunterschiede erleben und nicht nur hören.

Am Ende der Einheit verstehen die Lernenden, dass die binäre Suche bei sortierten Daten logarithmische Laufzeiten erreicht, während die lineare Suche linear wächst. Sie können den Algorithmus implementieren, Laufzeiten vergleichen und die Notwendigkeit von Sortierung begründen.

---

Vorsicht vor diesen Fehlvorstellungen

• Während der Stationenarbeit mit physischen Suchkarten beobachten Sie, dass einige Schülerinnen und Schüler die Karten absichtlich unsortiert lassen und trotzdem die binäre Suche anwenden.

  Bitten Sie die Lernenden, die unsortierten Karten systematisch zu sortieren und die binäre Suche erneut zu testen. Diskutieren Sie in der Gruppe, warum die Sortierung eine Voraussetzung ist und welche Schritte im Algorithmus ohne Sortierung scheitern würden.

• Während der Laufzeitanalyse in Kleingruppen äußern Schülerinnen und Schüler die Annahme, dass die binäre Suche immer genau doppelt so schnell ist wie die lineare Suche.

  Fordern Sie die Gruppen auf, ihre Laufzeitmessungen in Diagrammen darzustellen und zu vergleichen. Zeigen Sie, dass der Effizienzvorteil exponentiell mit der Datenmenge wächst, und diskutieren Sie, warum die Annahme nicht für alle n gilt.

• Während der Paarprogrammierung rechtfertigen einige Lernende lange, ineffiziente Implementierungen mit der Aussage, dass mehr Code immer besser sei.

  Lassen Sie die Teams ihre Laufzeiten messen und vergleichen Sie die Ergebnisse in der Klasse. Zeigen Sie, dass die binäre Suche trotz kürzerem Code effizienter ist, und diskutieren Sie, wie klare Struktur und einfache Algorithmen die Effizienz steigern.

---

In dieser Übersicht verwendete Methoden

• Problemorientiertes Lernen
• Lernen an Stationen