Informatik · Klasse 13

Ideen für aktives Lernen

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.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Algorithmen
• KMK: Sekundarstufe II - Strukturieren und Vernetzen

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

Aktivität 01

• 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.

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.

Worauf zu achten ist

Geben Sie den Schülern 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.

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

Aktivität 02

• 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.

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.

Worauf zu achten ist

Stellen Sie 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 Auswirkungen großer Datenmengen und die langfristige Wartbarkeit von Software stützen.

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

Aktivität 03

• 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.

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.

Worauf zu achten ist

Bitten Sie die Schüler, 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.

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

Aktivität 04

• 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.

Warum ist die Skalierbarkeit eines Algorithmus wichtiger als die Hardwaregeschwindigkeit?

Worauf zu achten ist

Geben Sie den Schülern 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.

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

Einige Hinweise zum Unterrichten dieser Einheit

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.

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

• 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.

  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.

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

  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.

• 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.

  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.

---

In dieser Übersicht verwendete Methoden

• Fallstudienanalyse