Effizienzanalyse (O-Notation)

Aktives Lernen funktioniert besonders gut bei der Effizienzanalyse, weil Schüler die abstrakten Konzepte der O-Notation durch messbare und sichtbare Experimente selbst nachvollziehen können. Die Verbindung von Theorie und Praxis in realen Algorithmen macht die Bedeutung der Asymptotik greifbar und fördert ein tiefes Verständnis für die Skalierbarkeit von Lösungen.

• Klasse 11
• Informatik in der Oberstufe: Algorithmen, Daten und Gesellschaft
• 4 Aktivitäten
• 30 Min.–50 Min.

Lernziele

1. Berechnen Sie die Laufzeit eines gegebenen Algorithmus für kleine Eingabegrößen und extrapolieren Sie die asymptotische Laufzeit mit der O-Notation.
2. Vergleichen Sie die Effizienz von zwei verschiedenen Sortieralgorithmen (z. B. Bubble Sort vs. Merge Sort) basierend auf ihrer O-Notation.
3. Erklären Sie, wie sich eine Verdopplung der Eingabegröße auf die Laufzeit von Algorithmen mit O(1), O(n), O(n log n) und O(n²) Komplexität auswirkt.
4. Bewerten Sie die praktische Relevanz der theoretischen Komplexität gegenüber der reinen Hardwaregeschwindigkeit bei der Auswahl eines Algorithmus für ein bestimmtes Problem.
5. Identifizieren Sie Beispiele für Probleme, die aufgrund ihrer Komplexität als praktisch unlösbar gelten (z. B. das Traveling Salesperson Problem mit Brute-Force-Ansatz).

Entscheidungsmatrix

⏱ 45 Min.·Kleingruppen

Stationenrotation: Laufzeiten messen

Richten Sie Stationen für Algorithmen ein: lineare Suche (O(n)), Bubble Sort (O(n²)) und Binärsuche (O(log n)). Gruppen führen Tests mit Datensätzen von 10 bis 1000 Elementen durch, messen Zeiten mit Stoppuhr und notieren Ergebnisse. Abschließend vergleichen sie die Daten grafisch.

Vorbereitung & Details

Wie wirkt sich eine Verdopplung der Eingabedaten auf die Laufzeit eines Programms aus?

Moderationstipp: Während der Stationenrotation die Laufzeitmessung mit einfachen Stoppuhren oder digitalen Tools wie Jupyter Notebooks anleiten, um die Schüler direkt mit der Datenaufnahme zu konfrontieren.

Setup: Gruppentische mit Arbeitsblättern für die Matrix

Materials: Vorlage für die Entscheidungsmatrix, Beschreibungen der Handlungsoptionen, Leitfaden zur Kriteriengewichtung, Präsentationsvorlage

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

Entscheidungsmatrix

⏱ 30 Min.·Partnerarbeit

Paararbeit: Komplexitätskurven plotten

Paare implementieren einen Algorithmus in Python, variieren die Eingabegröße und protokollieren Laufzeiten. Sie plotten die Werte mit Matplotlib und approximieren die O-Notation. Diskutieren Sie Abweichungen durch Konstantenfaktoren.

Vorbereitung & Details

Warum ist die theoretische Komplexität oft wichtiger als die tatsächliche Hardwaregeschwindigkeit?

Moderationstipp: Bei der Paararbeit die Schüler auffordern, ihre Komplexitätskurven auf Millimeterpapier zu skizzieren, damit sie die Steigung und Krümmung der Kurven selbst interpretieren können.

Setup: Gruppentische mit Arbeitsblättern für die Matrix

Materials: Vorlage für die Entscheidungsmatrix, Beschreibungen der Handlungsoptionen, Leitfaden zur Kriteriengewichtung, Präsentationsvorlage

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

Entscheidungsmatrix

⏱ 50 Min.·Kleingruppen

Gruppenexperiment: Skalierbarkeitswettbewerb

Gruppen optimieren denselben Algorithmus und vergleichen Laufzeiten bei großen Eingaben. Sie präsentieren ihre O-Analyse und testen gegeneinander. Der Fokus liegt auf asymptotischem Verhalten.

Vorbereitung & Details

Gibt es Probleme, die für Computer grundsätzlich unlösbar sind?

Moderationstipp: Beim Skalierbarkeitswettbewerb die Gruppen ermutigen, ihre Ergebnisse auf großen Plakaten festzuhalten und gegenseitig zu erklären, warum bestimmte Algorithmen schneller wachsen als andere.

Setup: Gruppentische mit Arbeitsblättern für die Matrix

Materials: Vorlage für die Entscheidungsmatrix, Beschreibungen der Handlungsoptionen, Leitfaden zur Kriteriengewichtung, Präsentationsvorlage

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

Entscheidungsmatrix

⏱ 35 Min.·Ganze Klasse

Ganzklasse: Unentscheidbarkeitsdemo

Die Klasse diskutiert das Halteproblem anhand simpler Beispiele. Jede Gruppe entwirft ein Gegenbeispiel und reflektiert kollektiv Grenzen der O-Notation.

Vorbereitung & Details

Wie wirkt sich eine Verdopplung der Eingabedaten auf die Laufzeit eines Programms aus?

Moderationstipp: Für die Unentscheidbarkeitsdemo die Schüler aktiv in die Diskussion einbeziehen, indem sie Beispiele aus ihrem Alltag nennen lassen, die ähnliche Wachstumsmuster zeigen.

Setup: Gruppentische mit Arbeitsblättern für die Matrix

Materials: Vorlage für die Entscheidungsmatrix, Beschreibungen der Handlungsoptionen, Leitfaden zur Kriteriengewichtung, Präsentationsvorlage

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

Dieses Thema unterrichten

Erfahrene Lehrkräfte beginnen mit konkreten, alltagsnahen Beispielen wie dem Suchen in einer Liste oder dem Sortieren von Namen, um die O-Notation einzuführen. Sie vermeiden es, die O-Notation als starres Schema zu vermitteln, und betonen stattdessen die Bedeutung des asymptotischen Verhaltens. Wichtig ist, dass Schüler selbst messen und vergleichen, um die theoretischen Konzepte mit realen Daten zu verknüpfen. Fehlerhafte Vorstellungen wie die Gleichsetzung von O-Notation mit exakter Laufzeit werden durch gezielte Experimente direkt korrigiert.

Was Sie erwartet

Am Ende dieser Einheit können Schüler die O-Notation verschiedener Algorithmen korrekt zuordnen und die Auswirkungen von Eingabegrößenänderungen auf Laufzeit und Speicherbedarf präzise vorhersagen. Sie nutzen Messdaten und grafische Darstellungen, um theoretische Aussagen zu überprüfen und zu begründen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

During der Stationenrotation 'Laufzeiten messen', watch for...

Was Sie stattdessen lehren sollten

Schüler, die glauben, die gemessenen Zeiten seien die exakte Laufzeit, sollten durch den Vergleich mehrerer Durchläufe mit derselben Eingabegröße erkennen, dass O-Notation nur eine obere Schranke darstellt. Nutzen Sie die gemessenen Daten, um zu zeigen, wie Konstantenfaktoren die Kurvenform beeinflussen.

Häufige Fehlvorstellung

During dem Gruppenexperiment 'Skalierbarkeitswettbewerb', watch for...

Was Sie stattdessen lehren sollten

Schüler, die annehmen, dass Hardwareverbesserungen ineffiziente Algorithmen immer praktikabel machen, sollten durch die Visualisierung der exponentiellen Wachstumskurve von O(2^n) erkennen, dass selbst große Hardwareverbesserungen hier keine Lösung bieten.

Häufige Fehlvorstellung

During der Ganzklasse 'Unentscheidbarkeitsdemo', watch for...

Was Sie stattdessen lehren sollten

Schüler, die behaupten, alle Probleme hätten eine effiziente Lösung in O(n), sollten durch Gegenbeispiele wie das Rucksackproblem und die Diskussion realer Szenarien erkennen, dass viele Probleme nur mit höherer Komplexität lösbar sind.

Ideen zur Lernstandserhebung

Kurze Überprüfung

Nach der Stationenrotation 'Laufzeiten messen' zeigen Sie den Schülern drei Code-Snippets (eine einfache Schleife, eine verschachtelte Schleife, eine Operation mit fester Anzahl von Schritten). Bitten Sie sie, die O-Notation für jedes Snippet zu bestimmen und kurz zu begründen, warum sie zu dieser Einschätzung kommen.

Diskussionsfrage

Während des Gruppenexperiments 'Skalierbarkeitswettbewerb' stellen Sie die Frage: 'Warum ist es wichtiger, die O-Notation eines Algorithmus zu kennen, als zu wissen, ob mein Computer 2 GHz oder 3 GHz schnell ist?' Leiten Sie eine Diskussion, die die langfristige Skalierbarkeit und die Grenzen der Hardwaregeschwindigkeit anhand der gemessenen Daten hervorhebt.

Lernstandskontrolle

Nach der Paararbeit 'Komplexitätskurven plotten' geben Sie jedem Schüler eine Karte mit einer Eingabegröße (z. B. n=10, n=100, n=1000) und einer Komplexitätsklasse (z. B. O(n), O(n²)). Bitten Sie sie, die ungefähre Laufzeit zu schätzen und eine kurze Erklärung zu geben, wie sie zu ihrer Einschätzung gekommen sind.

Erweiterungen & Unterstützung

• Fordern Sie schnelle Schüler auf, einen Algorithmus mit O(log n) Komplexität zu analysieren und dessen Laufzeitverhalten mit den bereits untersuchten Algorithmen zu vergleichen.
• Unterstützen Sie Schüler mit Schwierigkeiten, indem Sie eine vorbereitete Tabelle mit Beispielen für O(1), O(n) und O(n²) ausfüllen lassen und gemeinsam die Muster diskutieren.
• Vertiefen Sie mit allen Schülern die Analyse eines Algorithmus mit O(n log n), wie MergeSort, und vergleichen Sie dessen Skalierbarkeit mit O(n²).

Schlüsselvokabular

O-Notation (Obere Schranke)	Eine mathematische Notation, die die obere Wachstumsgrenze der Laufzeit oder des Speicherbedarfs eines Algorithmus in Abhängigkeit von der Eingabegröße beschreibt. Sie ignoriert konstante Faktoren und Terme niedrigerer Ordnung.
Zeitkomplexität	Ein Maß dafür, wie lange ein Algorithmus benötigt, um ausgeführt zu werden, ausgedrückt als Funktion der Größe der Eingabe. Sie wird oft mit der O-Notation angegeben.
Platzkomplexität	Ein Maß dafür, wie viel Speicherplatz ein Algorithmus während seiner Ausführung benötigt, ebenfalls ausgedrückt als Funktion der Eingabegröße und oft mit der O-Notation.
Asymptotisches Verhalten	Das Verhalten eines Algorithmus, wenn die Eingabegröße gegen unendlich geht. Die O-Notation konzentriert sich auf dieses Verhalten, um die Skalierbarkeit zu beurteilen.
Exponentielles Wachstum	Eine Wachstumsrate, bei der die Laufzeit eines Algorithmus exponentiell mit der Eingabegröße zunimmt (z. B. O(2^n)), was ihn für größere Eingaben schnell unpraktikabel macht.