Informatik · Klasse 12 · Datenstrukturen und Algorithmen · 1. Halbjahr

Dynamische Programmierung

Die Schülerinnen und Schüler lernen das Prinzip der dynamischen Programmierung kennen und wenden es auf Optimierungsprobleme an.

• KMK Bildungsstandards
• KMK: Sekundarstufe II - Modellieren und Implementieren
• KMK: Sekundarstufe II - Problemlösen und Handeln

Über dieses Thema

Dynamische Programmierung ist eine Methode zur Lösung komplexer Optimierungsprobleme, bei denen überlappende Teilprobleme und optimale Substrukturen vorliegen. Schülerinnen und Schüler lernen, rekursive Lösungen mit Memoisation oder Tabellen zu optimieren, um exponentielle Laufzeiten auf polynomielle zu reduzieren. Beispiele wie die Fibonacci-Folge oder der Rucksackalgorithmus machen das Prinzip greifbar und zeigen, wie DP Effizienz in der Algorithmik steigert.

Im KMK-Lehrplan Sekundarstufe II verbindet dieses Thema Modellieren und Implementieren mit Problemlösen. Es fördert das Verständnis von Datenstrukturen und Algorithmen, indem Schüler Probleme zerlegen, Abhängigkeiten erkennen und iterative Lösungen entwickeln. So entsteht ein tieferes Begreifen, wie Algorithmen reale Anwendungen wie Routenplanung oder Bioinformatik unterstützen.

Aktives Lernen eignet sich hervorragend für dynamische Programmierung, da Schüler durch Pair-Programming und Gruppenmodellierung abstrakte Konzepte konkretisieren. Sie bauen Tabellen manuell auf, vergleichen Rekursion mit DP und debuggen gemeinsam, was Fehlerquellen aufdeckt und langfristiges Verständnis sichert. Solche Ansätze machen den Stoff lebendig und transferierbar.

Leitfragen

1. Erklären Sie das Grundprinzip der dynamischen Programmierung und wann sie angewendet wird.
2. Analysieren Sie, wie dynamische Programmierung die Effizienz bei überlappenden Teilproblemen verbessert.
3. Entwerfen Sie eine dynamische Programmierlösung für ein Problem wie die Fibonacci-Folge.

Lernziele

• Erklären Sie das Prinzip der dynamischen Programmierung anhand des Problems der Fibonacci-Folge.
• Analysieren Sie die Zeitkomplexität einer rekursiven Lösung und einer dynamischen Programmierlösung für ein gegebenes Problem.
• Entwerfen Sie eine dynamische Programmierlösung für ein Optimierungsproblem wie den kürzesten Weg in einem Graphen.
• Vergleichen Sie die Effizienz von Memoisation und Tabellierung bei der Implementierung dynamischer Programmieralgorithmen.
• Bewerten Sie, ob ein gegebenes Problem die Eigenschaften überlappender Teilprobleme und optimaler Substrukturen aufweist.

Bevor es losgeht

Grundlagen der Rekursion

Warum: Schüler müssen verstehen, wie Funktionen sich selbst aufrufen können, um die rekursiven Ansätze zu verstehen, die durch dynamische Programmierung optimiert werden.

Algorithmen-Analyse und Zeitkomplexität (O-Notation)

Warum: Das Verständnis der Effizienzsteigerung durch dynamische Programmierung erfordert Kenntnisse über die Analyse von Algorithmen und die Big-O-Notation.

Grundlegende Datenstrukturen (Arrays, Listen)

Warum: Die Implementierung von Memoisation und Tabellierung basiert auf der Verwendung von Arrays oder ähnlichen Strukturen zur Speicherung von Zwischenergebnissen.

Schlüsselvokabular

Dynamische Programmierung	Eine algorithmische Technik zur Lösung komplexer Probleme durch Zerlegung in einfachere Teilprobleme, deren Lösungen gespeichert und wiederverwendet werden.
Überlappende Teilprobleme	Teilprobleme, die bei der Lösung eines größeren Problems mehrfach auftreten und deren Lösungen wiederverwendet werden können.
Optimale Substruktur	Ein Problem weist eine optimale Substruktur auf, wenn eine optimale Lösung des Gesamtproblems aus optimalen Lösungen seiner Teilprobleme aufgebaut werden kann.
Memoisation	Eine Optimierungstechnik, bei der die Ergebnisse von Funktionsaufrufen gespeichert werden, um bei wiederholten Aufrufen mit denselben Eingaben die Ergebnisse direkt zurückzugeben.
Tabellierung	Eine Bottom-up-Methode der dynamischen Programmierung, bei der die Lösungen für Teilprobleme in einer Tabelle gespeichert werden, beginnend mit den kleinsten Teilproblemen.

Vorsicht vor diesen Fehlvorstellungen

Häufige Fehlvorstellung

Dynamische Programmierung ist nur eine schnellere Rekursion.

Was Sie stattdessen lehren sollten

DP nutzt Tabellen oder Memoisation, um Subprobleme einmal zu lösen, nicht nur Rekursion zu beschleunigen. Pair-Programming hilft, indem Schüler Laufzeiten protokollieren und den Unterschied visualisieren, was den Bottom-up-Ansatz klar macht.

Häufige Fehlvorstellung

DP eignet sich für jedes Optimierungsproblem.

Was Sie stattdessen lehren sollten

DP erfordert überlappende Subprobleme und optimale Substruktur. Gruppenmodellierung mit Beispielen wie Rucksack vs. Sortieren zeigt Kriterien. Diskussionen klären, wann Greedy oder andere Methoden passen.

Häufige Fehlvorstellung

DP verbraucht immer viel Speicher.

Was Sie stattdessen lehren sollten

Top-down mit Memoisation spart Speicher im Vergleich zu Bottom-up-Tabellen. Individuelle Implementierungen und Vergleiche machen Trade-offs erlebbar und fördern nuanciertes Denken.

Ideen für aktives Lernen

Pair-Programming: Fibonacci mit DP

Paare implementieren die rekursive Fibonacci-Funktion und messen die Laufzeit. Dann erweitern sie sie mit einem Memoisations-Array und vergleichen die Ergebnisse. Abschließend diskutieren sie den Speicherbedarf.

30 Min.·Partnerarbeit

Gruppenaufgabe: Rucksackproblem tabellarisch

Gruppen modellieren das 0/1-Rucksackproblem mit einer Tabelle: Zeilen für Items, Spalten für Gewichte. Sie füllen Zellen iterativ und finden die optimale Lösung. Präsentation der Tabelle schließt ab.

45 Min.·Kleingruppen

Whole-Class-Diskussion: DP vs. Greedy

Die Klasse analysiert ein Problem wie Münzenwechsel. Jede Gruppe testet Greedy und DP, teilt Ergebnisse und diskutiert, wann DP überlegen ist. Lehrer moderiert mit Whiteboard.

20 Min.·Ganze Klasse

Individual: Eigene DP-Lösung entwerfen

Schüler wählen ein Problem wie längste gemeinsame Unterfolge, skizzieren die Rekurrenzrelation und implementieren in Python. Peer-Review folgt optional.

50 Min.·Einzelarbeit

Bezüge zur Lebenswelt

• In der Routenplanung, wie sie von Navigationssystemen (z.B. Google Maps, Waze) verwendet wird, hilft dynamische Programmierung, den kürzesten oder schnellsten Weg zwischen zwei Punkten zu finden, indem sie verschiedene Routenoptionen und Verkehrsdaten berücksichtigt.
• In der Bioinformatik wird dynamische Programmierung zur Sequenzalignment eingesetzt, um die Ähnlichkeit zwischen DNA- oder Proteinsequenzen zu bestimmen, was für das Verständnis von Genfunktionen und evolutionären Beziehungen entscheidend ist.
• Finanzanalysten nutzen dynamische Programmierung für Portfoliooptimierung, um die beste Verteilung von Investitionen zu ermitteln, die eine Rendite maximiert oder ein Risiko minimiert, basierend auf historischen Daten und Marktprognosen.

Ideen zur Lernstandserhebung

Lernstandskontrolle

Geben Sie den Schülern die Aufgabe, die ersten 10 Fibonacci-Zahlen mit und ohne dynamische Programmierung (rekursiv vs. tabellarisch) zu berechnen. Sie sollen die Anzahl der notwendigen Berechnungen für beide Ansätze vergleichen und eine kurze Erklärung abgeben, warum die DP-Methode effizienter ist.

Kurze Überprüfung

Stellen Sie den Schülern ein einfaches Problem vor (z.B. Münzwechselproblem mit wenigen Münzarten). Bitten Sie sie, zu identifizieren, ob es überlappende Teilprobleme und optimale Substrukturen aufweist. Sie sollen dann die ersten Schritte zur Entwicklung einer DP-Lösung skizzieren.

Diskussionsfrage

Diskutieren Sie in Kleingruppen: 'Wann ist dynamische Programmierung die beste Wahl zur Problemlösung, und wann könnten andere Algorithmen (z.B. Greedy-Algorithmen) besser geeignet sein?' Die Gruppen sollen konkrete Beispiele anführen und ihre Argumente begründen.

Häufig gestellte Fragen

Was ist das Prinzip der dynamischen Programmierung?

Dynamische Programmierung löst Probleme, indem sie Subprobleme speichert und wiederverwendet. Sie basiert auf optimaler Substruktur (Lösung aus optimalen Teillösungen) und überlappenden Subproblemen. Statt redundanter Berechnungen in Rekursionen füllt man Tabellen oder verwendet Memoisation, was die Zeitkomplexität von exponentiell auf polynomiell reduziert. Beispiele sind Fibonacci oder kürzeste Pfade.

Wann wendet man dynamische Programmierung an?

DP ist ideal bei Optimierungsproblemen mit überlappenden Subproblemen, wie Sequenzabgleich in Bioinformatik oder Matrixkettenmultiplikation. Sie verbessert Effizienz, wo naive Rekursion zu langsam ist. Schüler lernen durch Analyse von Key Questions, Kriterien zu prüfen und Alternativen wie Divide-and-Conquer abzuwägen.

Wie hilft aktives Lernen beim Verständnis dynamischer Programmierung?

Aktives Lernen macht DP greifbar: Durch Pair-Programming bauen Schüler Tabellen hands-on, messen Laufzeiten und debuggen gemeinsam. Gruppenaufgaben zu Rucksack oder Fibonacci fördern Diskussionen über Subprobleme. Solche Methoden reduzieren abstrakte Hürden, steigern Retention und verbinden Theorie mit Praxis, wie KMK-Standards fordern.

Wie implementiert man Fibonacci mit DP?

Rekursiv: fib(n) = fib(n-1) + fib(n-2). Mit Memoisation: Array memo[0..n], wenn memo[i] gefüllt, zurückgeben, sonst berechnen und speichern. Bottom-up: Tabelle von fib(0)=0, fib(1)=1 iterativ füllen. Python-Beispiel: def fib_dp(n): dp = [0]*(n+1); dp[1]=1; for i in range(2,n+1): dp[i]=dp[i-1]+dp[i-2]; return dp[n]. Zeit: O(n).