Algorithmenanalyse und O-Notation

Aktive Methoden machen abstrakte Konzepte wie O-Notation greifbar, weil Schülerinnen und Schüler durch Simulationen und Messungen selbst erleben, wie Algorithmen bei wachsender Datenmenge skalieren. Das fördert ein tiefes Verständnis für die praktische Relevanz mathematischer Modelle und zeigt, warum Effizienzanalysen in der Programmierung unverzichtbar sind.

• Klasse 12
• Informatik Oberstufe: Von Algorithmen zur vernetzten Gesellschaft
• 4 Aktivitäten
• 20 Min.–50 Min.

Lernziele

1. Analysieren Sie die Laufzeitkomplexität von einfachen Algorithmen (z. B. lineare Suche) und klassifizieren Sie diese in Big-O-Notation.
2. Vergleichen Sie die Speicherplatz- und Zeitkomplexität verschiedener Lösungsansätze für dasselbe Problem.
3. Erklären Sie die Bedeutung der O-Notation für die Vorhersage der Skalierbarkeit von Algorithmen bei wachsenden Datenmengen.
4. Berechnen Sie die Anzahl der Operationen für gegebene Algorithmen und leiten Sie daraus die O-Notation ab.

Problemorientiertes Lernen

⏱ 30 Min.·Partnerarbeit

Paararbeit: Laufzeit-Simulation

Paare erhalten Algorithmenkarten mit linearer und binärer Suche. Sie simulieren Ausführungen für Datenmengen von 10 bis 1000 Elementen und notieren Schritte. Abschließend plotten sie Kurven und bestimmen die O-Notation.

Vorbereitung & Details

Wie lässt sich mathematisch vorhersagen, ob ein Algorithmus bei großen Datenmengen noch funktioniert?

Moderationstipp: Während der Laufzeit-Simulation in Paararbeit gezielt nachfragen, warum die gemessenen Zeiten manchmal überraschend ausfallen und wie Konstanten das Ergebnis beeinflussen.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

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

Lernen an Stationen

⏱ 45 Min.·Kleingruppen

Lernen an Stationen: Komplexitätsbestimmung

Richten Sie Stationen für Bubble Sort, Quick Sort und Hash-Tabellen ein. Gruppen analysieren Code-Snippets, schätzen Komplexitäten und diskutieren Trade-offs. Jede Gruppe präsentiert ein Ergebnis.

Vorbereitung & Details

Was ist der Trade-off zwischen Speicherplatzverbrauch und Rechengeschwindigkeit?

Moderationstipp: Bei der Stationenarbeit klare Zeitlimits setzen und gezielt auf die Dokumentation der Komplexitätsbestimmung achten, um oberflächliche Antworten zu vermeiden.

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

Debatte

⏱ 50 Min.·Ganze Klasse

Klassenweite Grafikdebatte

Die Klasse misst reale Laufzeiten mit Python-Code für verschiedene Eingaben. Gemeinsam erstellen sie Big-O-Grafiken am Whiteboard und debattieren Vorhersagen für große n.

Vorbereitung & Details

Analysieren Sie die Laufzeitkomplexität einfacher Algorithmen wie der linearen Suche.

Moderationstipp: Die Klassenweite Grafikdebatte mit gezielten Nachfragen steuern, um sicherzustellen, dass die Schülerinnen und Schüler nicht nur Meinungen äußern, sondern ihre Aussagen mit Daten begründen.

Setup: Zwei sich gegenüberstehende Teams, Sitzplätze für das Publikum

Materials: Thesenkarte für die Debatte, Recherche-Dossier für jede Seite, Bewertungsbogen für das Publikum, Stoppuhr

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

Problemorientiertes Lernen

⏱ 20 Min.·Einzelarbeit

Individuell: Eigene Algorithmen

Schüler wählen einen Alltagsalgorithmus, analysieren seine Komplexität und visualisieren sie in einer Tabelle oder Grafik. Sie tauschen Ergebnisse aus und korrigieren gegenseitig.

Vorbereitung & Details

Wie lässt sich mathematisch vorhersagen, ob ein Algorithmus bei großen Datenmengen noch funktioniert?

Moderationstipp: Bei der Erstellung eigener Algorithmen darauf achten, dass die Schülerinnen und Schüler ihre O-Notation-Bewertung schriftlich begründen und nicht nur das Ergebnis nennen.

Setup: Gruppentische mit Zugang zu Recherchequellen

Materials: Dokumentation des Problemszenarios, KWL-Tabelle (Wissen, Wollen, Lernen) oder Inquiry-Framework, Ressourcenpool / Handapparat, Vorlage für die Ergebnispräsentation

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

Dieses Thema unterrichten

Beginne mit konkreten, alltagsnahen Beispielen, um die abstrakte O-Notation zu veranschaulichen. Vermeide reine Theorievermittlung und baue stattdessen schrittweise Messungen und Vergleiche ein. Forschung zeigt, dass Schülerinnen und Schüler komplexe Konzepte besser verstehen, wenn sie selbst aktiv werden und Ergebnisse direkt beobachten können. Achte darauf, dass die Unterschiede zwischen worst-case, best-case und average-case deutlich werden, um Fehlvorstellungen zu vermeiden.

Was Sie erwartet

Am Ende sollen die Schülerinnen und Schüler nicht nur O-Notationen korrekt anwenden, sondern auch erklären können, warum bestimmte Algorithmen für große Datenmengen ungeeignet sind. Sie erkennen Trade-offs zwischen Zeit- und Platzkomplexität und können diese in eigenen Beispielen anwenden.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Während der Laufzeit-Simulation in Paararbeit könnte ein Schüler behaupten: 'O(n) ist immer langsamer als O(1), egal wie klein die Konstanten sind.'

Was Sie stattdessen lehren sollten

Fordere die Schülerinnen und Schüler auf, ihre Messungen zu vergleichen und gezielt nach Algorithmen mit kleinen Konstanten in O(1) zu suchen. Zeige ihnen, wie sie die gemessenen Zeiten in einer Tabelle gegenüberstellen und diskutieren lassen, warum O-Notation Konstanten ignoriert.

Häufige Fehlvorstellung

Während der Stationenarbeit zur Komplexitätsbestimmung könnte ein Schüler sagen: 'O(1) bedeutet, dass der Algorithmus in genau einer Operation läuft.'

Was Sie stattdessen lehren sollten

Gib den Schülerinnen und Schülern eine konkrete Messaufgabe vor und lass sie verschiedene Eingabegrößen testen. Zeige ihnen, dass O(1) bedeutet, dass die Laufzeit unabhängig von der Eingabegröße ist, aber nicht unbedingt genau eine Operation umfasst.

Häufige Fehlvorstellung

Während der Stationenrotation zum Ressourcenverbrauch könnte ein Schüler behaupten: 'Platzkomplexität ist nur bei Speicherknappheit relevant.'

Was Sie stattdessen lehren sollten

Stelle den Schülerinnen und Schülern eine Aufgabe, bei der sie zwei Algorithmen mit unterschiedlicher Platzkomplexität auf einem fiktiven Gerät mit begrenztem Speicher testen müssen. Lass sie dokumentieren, wie sich die Wahl des Algorithmus auf die Ressourcennutzung auswirkt.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Laufzeit-Simulation in Paararbeit gib den Schülerinnen und Schülern ein Pseudocode-Fragment vor und frage sie: 'Wie viele Operationen werden ungefähr ausgeführt, wenn n sehr groß wird?' und 'Welche O-Notation beschreibt die Laufzeit dieses Code-Fragments?' Lasse sie ihre Antworten auf einem Whiteboard oder in einem Lerntagebuch festhalten und kurz besprechen.

Diskussionsfrage

Nach der Stationenarbeit zur Komplexitätsbestimmung stelle die Klasse vor die Frage: 'Warum ist es wichtig, die O-Notation zu verstehen, wenn man Software für mobile Apps entwickelt, die auf Geräten mit begrenztem Speicher und Akkulaufzeit laufen muss?' Nutze die Ergebnisse der Stationenarbeit als Grundlage für eine strukturierte Diskussion über Trade-offs zwischen Zeit- und Platzkomplexität.

Lernstandskontrolle

Nach der Erstellung eigener Algorithmen bitte die Schülerinnen und Schüler, zwei einfache Algorithmen zu beschreiben: einen mit O(n) und einen mit O(n²). Für jeden Algorithmus sollen sie angeben, für welche Art von Problem er geeignet sein könnte und warum der andere Algorithmus bei sehr großen Datenmengen ungeeignet wäre. Sammle die Ergebnisse ein und nutze sie, um individuelle Rückmeldungen zu geben.

Erweiterungen & Unterstützung

• Fordere schnelle Schülerinnen und Schüler auf, einen O(n log n)-Algorithmus zu entwerfen und dessen Laufzeit mit den bereits analysierten Algorithmen zu vergleichen.
• Für Schülerinnen und Schüler, die kämpfen, vereinfache die Stationenarbeit auf O(1), O(n) und O(n²) und nutze grafische Hilfen wie Balkendiagramme zur Visualisierung.
• Vertiefe die Thematik mit einer Gruppenaufgabe: Analysiere einen realen Algorithmus aus einer Programmiersprache deiner Wahl und präsentiere die Ergebnisse der Klasse.

Schlüsselvokabular

O-Notation (Obere Schranke)	Eine mathematische Notation, die die obere Schranke für das Wachstum der Laufzeit oder des Speicherbedarfs eines Algorithmus angibt, wenn die Eingabegröße wächst.
Zeitkomplexität	Ein Maß dafür, wie lange ein Algorithmus zur Ausführung benötigt, typischerweise ausgedrückt als Funktion der Größe der Eingabedaten.
Platzkomplexität	Ein Maß dafür, wie viel Speicherplatz ein Algorithmus während seiner Ausführung benötigt, ebenfalls als Funktion der Eingabegröße.
Asymptotisches Verhalten	Das Verhalten eines Algorithmus für sehr große Eingabewerte, das durch die O-Notation beschrieben wird.
Konstante Faktoren und Terme niedrigerer Ordnung	Elemente, die bei der Bestimmung der O-Notation ignoriert werden, da sie für große Eingaben weniger relevant sind als der dominierende Term.