Komplexitätsanalyse (O-Notation)

Die Komplexitätsanalyse mit O-Notation lebt von praktischer Anwendung und Veranschaulichung. Aktive Lernmethoden wie der Graphen-Workshop oder die Timer-Challenge ermöglichen es den Lernenden, abstrakte Konzepte greifbar zu machen und die Auswirkungen verschiedener Algorithmen auf die Leistung direkt zu erfahren.

• Klasse 13
• Informatik Oberstufe: Komplexe Systeme und Theoretische Grundlagen
• 4 Aktivitäten
• 35 Min.–50 Min.

Lernziele

1. Vergleichen Sie die asymptotische Laufzeit von drei verschiedenen Suchalgorithmen (linear, binär, exponentiell) für gegebene Eingabegrößen.
2. Erklären Sie anhand von Pseudocode, wie sich die Anzahl der Operationen eines Sortieralgorithmus mit der Eingabegröße ändert.
3. Bewerten Sie die Effizienz eines gegebenen Algorithmus in Bezug auf Zeit- und Speicherkomplexität unter Verwendung der O-Notation.
4. Identifizieren Sie die dominante Terme in einer Laufzeitfunktion, um die O-Notation korrekt anzuwenden.
5. Entwerfen Sie einen einfachen Algorithmus für ein gegebenes Problem und analysieren Sie dessen Worst-Case-Komplexität.

Fallstudienanalyse

⏱ 50 Min.·Kleingruppen

Timer-Challenge: Sortieralgorithmen

Schüler implementieren Bubble Sort und Quick Sort in Python. Sie messen Laufzeiten für Datensätze mit 10, 100, 1000 und 10.000 Elementen. In Gruppen plotten sie die Ergebnisse und approximieren die O-Notation.

Vorbereitung & Details

Warum ist die Skalierbarkeit eines Algorithmus wichtiger als die Hardwaregeschwindigkeit?

Moderationstipp: Beim Graphen-Workshop: Achten Sie darauf, dass die Lernenden die Unterschiede zwischen den Skalen und Wachstumsraten der Graphen erkennen, indem Sie sie die Achsenbeschriftungen und die Form der Kurven vergleichen lassen.

Setup: Gruppentische mit Platz für die Fallunterlagen

Materials: Fallstudien-Paket (3-5 Seiten), Arbeitsblatt mit Analyseraster, Präsentationsvorlage

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

Fallstudienanalyse

⏱ 40 Min.·Partnerarbeit

Flaschenhals-Jagd: Code-Analyse

Teilen Sie Code-Snippets mit verschachtelten Schleifen aus. Gruppen markieren dominante Terme, ersetzen sie durch effizientere Varianten und vergleichen simulierte Laufzeiten mit Tabellenkalkulation.

Vorbereitung & Details

Wie unterscheidet sich die durchschnittliche Laufzeit vom Worst-Case-Szenario?

Moderationstipp: Bei der Timer-Challenge: Ermutigen Sie die Lernenden während der Implementierungsphase, sich auf die Messung der Laufzeiten für große Datensätze zu konzentrieren, da hier die Unterschiede in der Komplexität am deutlichsten werden.

Setup: Gruppentische mit Platz für die Fallunterlagen

Materials: Fallstudien-Paket (3-5 Seiten), Arbeitsblatt mit Analyseraster, Präsentationsvorlage

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

Fallstudienanalyse

⏱ 35 Min.·Einzelarbeit

Graphen-Workshop: Asymptotik

Individuell zeichnen Schüler Kurven für O(1), O(n), O(n log n) und O(n²) mit Excel. Im Plenum diskutieren sie Überschneidungen bei kleinen n und Dominanz bei großen n.

Vorbereitung & Details

Wie identifiziert man Flaschenhälse in komplexen Programmabläufen?

Moderationstipp: Bei der Flaschenhals-Jagd: Fordern Sie die Gruppen auf, während der Code-Analyse die dominanten Terme nicht nur zu identifizieren, sondern auch zu erklären, wie diese die Gesamtlaufzeit bei wachsender Eingabe beeinflussen.

Setup: Gruppentische mit Platz für die Fallunterlagen

Materials: Fallstudien-Paket (3-5 Seiten), Arbeitsblatt mit Analyseraster, Präsentationsvorlage

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

Fallstudienanalyse

⏱ 45 Min.·Kleingruppen

Worst-Case-Simulation: Pfadfindung

Gruppen simulieren mit Karten Worst-Case-Szenarien für Suchalgorithmen. Sie zählen Schritte manuell und leiten O-Notation ab, bevor sie zu Code übergehen.

Vorbereitung & Details

Warum ist die Skalierbarkeit eines Algorithmus wichtiger als die Hardwaregeschwindigkeit?

Setup: Gruppentische mit Platz für die Fallunterlagen

Materials: Fallstudien-Paket (3-5 Seiten), Arbeitsblatt mit Analyseraster, Präsentationsvorlage

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

Dieses Thema unterrichten

Beim Unterrichten der O-Notation ist es entscheidend, die abstrakte Mathematik mit konkreten Beispielen zu verbinden. Beginnen Sie mit einfachen, nachvollziehbaren Algorithmen und steigern Sie die Komplexität schrittweise. Vermeiden Sie es, die O-Notation als reine Formel zu präsentieren; stattdessen sollte sie als Werkzeug zur Vorhersage und Optimierung von Algorithmen verstanden werden, was durch praktische Experimente wie die Timer-Challenge verdeutlicht wird.

Was Sie erwartet

Erfolgreiche Lernende können die O-Notation korrekt auf einfache Algorithmen anwenden und die Laufzeitunterschiede verschiedener Sortieralgorithmen quantifizieren. Sie verstehen, warum die Skalierbarkeit eines Algorithmus entscheidend ist und können zwischen verschiedenen Komplexitätsklassen unterscheiden.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Timer-Challenge: Achten Sie darauf, dass die Lernenden nicht fälschlicherweise glauben, die O-Notation würde die exakte Laufzeit in Sekunden angeben.

Was Sie stattdessen lehren sollten

Lenken Sie die Diskussion nach der Timer-Challenge darauf, dass die gemessenen Zeiten von der Hardware abhängen, die O-Notation aber das grundsätzliche Skalierungsverhalten beschreibt, und nutzen Sie die unterschiedlichen Laufzeiten bei verschiedenen n, um dies zu verdeutlichen.

Häufige Fehlvorstellung

Bei der Worst-Case-Simulation: Beobachten Sie, ob die Lernenden davon ausgehen, dass der Worst-Case immer die einzig relevante Laufzeit ist.

Was Sie stattdessen lehren sollten

Nach der Worst-Case-Simulation regen Sie eine Diskussion an, in der die Lernenden verschiedene Eingabedaten simulieren (z.B. bereits sortierte Listen für die Suche) und so erkennen, dass die durchschnittliche oder Best-Case-Laufzeit in manchen Szenarien aussagekräftiger sein kann.

Häufige Fehlvorstellung

Während der Flaschenhals-Jagd: Achten Sie darauf, dass die Lernenden die Bedeutung der Platzkomplexität nicht ignorieren, nur weil der Fokus auf Zeitkomplexität liegt.

Was Sie stattdessen lehren sollten

Leiten Sie nach der Identifizierung zeitlicher Engpässe eine kurze Diskussion über die Speicheranforderungen der identifizierten Code-Abschnitte ein und verknüpfen Sie dies mit praktischen Beispielen, wo Speicherplatz ebenso kritisch sein kann wie Rechenzeit.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Flaschenhals-Jagd: Geben Sie den Lernenden drei kurze Pseudocode-Snippets für einfache Algorithmen (z.B. Summe einer Liste, Maximum finden, doppelte Schleife). Bitten Sie sie, für jedes Snippet die O-Notation für die Zeitkomplexität zu bestimmen und ihre Antwort kurz zu begründen, basierend auf den Techniken aus der Aktivität.

Diskussionsfrage

Stellen Sie nach dem Graphen-Workshop die Frage: 'Warum ist es wichtiger, die Skalierbarkeit eines Algorithmus zu verstehen, als die genaue Taktfrequenz eines Prozessors zu kennen?' Lassen Sie die Schüler ihre Antworten auf die visuellen Erkenntnisse aus den gezeichneten Graphen stützen.

Lernstandskontrolle

Bitten Sie die Schüler nach der Timer-Challenge, zwei Algorithmen zu nennen, die sie im Unterricht behandelt haben, und deren O-Notation zu notieren. Fordern Sie sie auf, einen Satz dazu zu schreiben, warum der effizientere Algorithmus für große Datensätze bevorzugt wird, gestützt auf ihre Messergebnisse.

Erweiterungen & Unterstützung

• Challenge: Implementieren Sie einen weiteren Sortieralgorithmus (z.B. Insertion Sort) und analysieren Sie dessen O-Notation sowie seine Leistung im Vergleich zu Bubble Sort und Quick Sort.
• Scaffolding: Bieten Sie den Lernenden vorgefertigte Code-Snippets mit auskommentierten Erklärungen für die dominanten Terme, um die Flaschenhals-Jagd zu unterstützen.
• Deeper Exploration: Untersuchen Sie die durchschnittliche und Best-Case-Laufzeit für die implementierten Sortieralgorithmen und diskutieren Sie, wann diese Metriken relevanter sein könnten als die Worst-Case-Analyse.

Schlüsselvokabular

O-Notation (Obere Schranke)	Eine mathematische Notation, die die obere Wachstumsgrenze der Laufzeit oder des Speicherbedarfs eines Algorithmus beschreibt, unabhängig von konstanten Faktoren und niedrigeren Ordnungstermen.
Asymptotische Analyse	Die Untersuchung des Verhaltens eines Algorithmus für sehr große Eingabegrößen, um seine Effizienz unabhängig von der Hardware zu bewerten.
Worst-Case-Komplexität	Die maximale Laufzeit oder der maximale Speicherbedarf, den ein Algorithmus für eine gegebene Eingabegröße haben kann.
Eingabegröße (n)	Die Größe der Daten, die ein Algorithmus verarbeitet, oft repräsentiert durch die Anzahl der Elemente in einer Liste oder die Anzahl der Knoten in einem Graphen.
Konstante Laufzeit (O(1))	Ein Algorithmus, dessen Ausführungszeit unabhängig von der Größe der Eingabe ist und immer gleich bleibt.