Grundlagen der Algorithmenanalyse

Aktive Lernformen sind hier besonders wirksam, weil das abstrakte Konzept der O-Notation durch praktische Messungen und Vergleiche greifbar wird. Schülerinnen und Schüler erkennen so selbst, wie sich Laufzeiten bei wachsender Eingabe verändern und warum bestimmte Komplexitätsklassen entscheidend sind für die Skalierbarkeit von Algorithmen.

• Klasse 10
• Digitale Welten Gestalten: Informatik in der Praxis
• 4 Aktivitäten
• 20 Min.–50 Min.

Lernziele

1. Vergleichen Sie die Laufzeitkomplexität von Algorithmen wie linearer Suche (O(n)) und binärer Suche (O(log n)) für gegebene Datensatzgrößen.
2. Erklären Sie die Bedeutung der O-Notation als obere Schranke für die Laufzeit und die Abstraktion von konstanten Faktoren.
3. Berechnen Sie die Anzahl der Operationen für einfache Algorithmen (z. B. Schleifen) und ordnen Sie sie einer O-Notation zu.
4. Analysieren Sie, warum exponentielle Algorithmen (O(2^n)) bei wachsender Eingabegröße schnell unpraktikabel werden.

Lernen an Stationen

⏱ 45 Min.·Kleingruppen

Lernen an Stationen: Laufzeiten messen

Richten Sie Stationen für Bubble Sort (O(n²)), Insertion Sort (O(n²)) und Binary Search (O(log n)) ein. Schüler implementieren Algorithmen in Python, testen mit Datensätzen von 10 bis 10.000 Elementen und protokollieren Zeiten. Abschließende Diskussion vergleicht Ergebnisse.

Vorbereitung & Details

Warum sind manche Algorithmen bei großen Datenmengen exponentiell langsamer?

Moderationstipp: Stellen Sie sicher, dass die Stationenlernen-Materialien präzise Messanleitungen enthalten und führen Sie eine kurze Vorbesprechung durch, damit alle Lernenden die gleichen Grundlagen haben.

Setup: Im Raum verteilte Tische/Stationen

Materials: Stationskarten mit Arbeitsanweisungen, Unterschiedliche Materialien je Station, Timer für die Rotation

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

Lernen an Stationen

⏱ 30 Min.·Partnerarbeit

Pair Programming: O-Notation visualisieren

In Paaren zeichnen Schüler Graphen der Funktionen O(1), O(n), O(n log n) und O(n²) für n=1 bis 1000. Sie plotten mit Tools wie Desmos und diskutieren Kreuzungspunkte. Gemeinsam erstellen sie eine Tabelle mit Beispielen.

Vorbereitung & Details

Wie lässt sich die Effizienz mathematisch (O-Notation) beschreiben?

Moderationstipp: Geben Sie beim Pair Programming klare Visualisierungsaufträge vor, z.B. konkrete Graphen zu erstellen oder Tabellen mit Messwerten zu füllen, um die O-Notation nachvollziehbar zu machen.

Setup: Im Raum verteilte Tische/Stationen

Materials: Stationskarten mit Arbeitsanweisungen, Unterschiedliche Materialien je Station, Timer für die Rotation

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

Lernen an Stationen

⏱ 50 Min.·Kleingruppen

Whole Class Challenge: Algorithmus-Wettbewerb

Teilen Sie die Klasse in Teams auf, die effizienteste Lösung für ein Suchproblem finden. Teams präsentieren Code und O-Analyse. Die Klasse votet und diskutiert den Gewinner basierend auf Skalierbarkeit.

Vorbereitung & Details

Vergleichen Sie die Laufzeitkomplexität von linearen und logarithmischen Algorithmen.

Moderationstipp: Beim Algorithmus-Wettbewerb achten Sie darauf, dass die Teams ihre Lösungen nicht nur implementieren, sondern auch ihre Komplexitätsanalyse schriftlich festhalten und im Plenum vorstellen.

Setup: Im Raum verteilte Tische/Stationen

Materials: Stationskarten mit Arbeitsanweisungen, Unterschiedliche Materialien je Station, Timer für die Rotation

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

Lernen an Stationen

⏱ 20 Min.·Einzelarbeit

Individual: Komplexitäts-Tagebuch

Jeder Schüler analysiert einen Alltagsalgorithmus (z.B. Telefonbuchsuche), schätzt O-Notation und simuliert mit Pseudocode. Nächste Stunde teilen sie in Plenum.

Vorbereitung & Details

Warum sind manche Algorithmen bei großen Datenmengen exponentiell langsamer?

Moderationstipp: Fordern Sie beim Komplexitäts-Tagebuch die Lernenden auf, ihre Einträge mit konkreten Beispielen und Messwerten zu untermauern, um ein tieferes Verständnis zu fördern.

Setup: Im Raum verteilte Tische/Stationen

Materials: Stationskarten mit Arbeitsanweisungen, Unterschiedliche Materialien je Station, Timer für die Rotation

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

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit einfachen, alltagsnahen Beispielen wie Suchalgorithmen im Telefonbuch, um das abstrakte Konzept der O-Notation einzuführen. Sie vermeiden zunächst formale Definitionen und lassen die Lernenden stattdessen selbst Laufzeiten messen und vergleichen. Wichtig ist, dass die Diskussionen immer wieder auf die praktische Relevanz hinführen: Welche Algorithmen halten was aus, wenn die Datenmenge wächst? So wird die Theorie lebendig und nachvollziehbar.

Was Sie erwartet

Erfolgreiches Lernen zeigt sich darin, dass Lernende O-Notation nicht nur benennen, sondern selbstständig für gegebene Algorithmen bestimmen und in konkreten Beispielen anwenden können. Sie diskutieren kritisch, welche Algorithmen für große Datenmengen geeignet sind und begründen ihre Entscheidungen mit Messdaten oder theoretischen Überlegungen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Stationenlernen-Aktivität 'Laufzeiten messen' beobachten Sie, wie Lernende die gemessenen Zeiten mit der theoretischen O-Notation vergleichen und dabei erkennen, dass die genauen Werte zwar abweichen, die Wachstumsrate aber übereinstimmt.

Was Sie stattdessen lehren sollten

Nutzen Sie die Messergebnisse, um gezielt zu fragen: 'Warum ist die O-Notation hier trotzdem hilfreich, obwohl die tatsächlichen Zeiten nicht exakt passen?' und lassen Sie die Lernenden diskutieren, wie Konstanten und Hardware die Laufzeit beeinflussen.

Häufige Fehlvorstellung

Während der Pair Programming-Aktivität 'O-Notation visualisieren' achten Sie darauf, ob Lernende exponentielle Algorithmen für kleine Eingaben als 'schneller' einstufen und dies mit Messwerten belegen.

Was Sie stattdessen lehren sollten

Lenken Sie die Diskussion auf die Skalierung: 'Was passiert, wenn die Eingabe von 10 auf 1000 steigt? Zeigen Sie den Lernenden, wie sich die Laufzeit bei O(2^n) im Vergleich zu O(n^2) entwickelt und lassen Sie sie dies grafisch darstellen.

Häufige Fehlvorstellung

Während des Whole Class Challenge 'Algorithmus-Wettbewerb' stellen Sie fest, ob Lernende die Komplexität nur auf den Worst Case beziehen oder auch Average Case und Best Case berücksichtigen.

Was Sie stattdessen lehren sollten

Fordern Sie die Teams auf, für ihre Algorithmen nicht nur die Worst-Case-Komplexität zu nennen, sondern auch zu diskutieren, unter welchen Bedingungen der Average Case oder Best Case eintritt und wie sich dies auf die praktische Eignung auswirkt.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Stationenlernen-Aktivität 'Laufzeiten messen' geben Sie den Lernenden Code-Snippets mit einfachen Schleifen, verschachtelten Schleifen und bedingten Anweisungen. Sie bestimmen die Laufzeitkomplexität und begründen ihre Wahl mit Bezug auf die gemessenen Zeiten aus der Stationenarbeit.

Diskussionsfrage

Nach dem Pair Programming 'O-Notation visualisieren' leiten Sie eine Diskussion mit der Frage: 'Warum ist es wichtig, die Laufzeitkomplexität zu verstehen, bevor man einen Algorithmus für sehr große Datensätze einsetzt?' Die Lernenden nennen Beispiele aus ihrer Visualisierung, z.B. wie sich O(n^2) im Vergleich zu O(n log n) bei wachsender Eingabe verhält.

Lernstandskontrolle

Nach dem Whole Class Challenge 'Algorithmus-Wettbewerb' erhalten die Lernenden einen Zettel, auf dem sie erklären sollen, warum ein Algorithmus mit O(n) besser skaliert als einer mit O(n^2), wenn die Eingabe von 10 auf 100 steigt. Sie geben eine quantitative Schätzung ab, z.B. wie viel länger der O(n^2)-Algorithmus im Vergleich zum O(n)-Algorithmus braucht.

Erweiterungen & Unterstützung

• Fordern Sie schnelle Lernende auf, für einen gegebenen Algorithmus nicht nur die O-Notation zu bestimmen, sondern auch eine alternative Implementierung mit besserer Komplexität zu entwickeln und zu vergleichen.
• Für Lernende mit Schwierigkeiten bieten Sie vorbereitete Tabellen an, in die sie Messwerte eintragen können, oder lassen Sie sie zunächst nur die O-Notation für sehr einfache Algorithmen (z.B. lineare Suche) bestimmen.
• Vertiefen Sie mit einer zusätzlichen Aufgabe, bei der Lernende selbst einen ineffizienten Algorithmus (z.B. Fibonacci rekursiv) in einen effizienten (z.B. iterativ oder mit Memoization) umwandeln und die Laufzeiten vergleichen.

Schlüsselvokabular

Laufzeitkomplexität	Beschreibt, wie sich die Ausführungszeit eines Algorithmus mit zunehmender Größe der Eingabedaten verändert.
O-Notation (Landau-Notation)	Eine mathematische Notation, die die obere Schranke der Wachstumsrate eines Algorithmus angibt, um seine Effizienz zu klassifizieren.
Asymptotische Analyse	Untersuchung des Verhaltens eines Algorithmus für sehr große Eingabegrößen, wobei konstante Faktoren und Terme niedrigerer Ordnung ignoriert werden.
Exponentielles Wachstum	Eine Wachstumsrate, bei der sich die Laufzeit eines Algorithmus mit jeder zusätzlichen Eingabeeinheit verdoppelt oder vervielfacht (z. B. O(2^n)).
Logarithmisches Wachstum	Eine Wachstumsrate, bei der sich die Laufzeit eines Algorithmus mit jeder Verdopplung der Eingabegröße nur um eine konstante Menge erhöht (z. B. O(log n)).