Informatik · Klasse 12

Ideen für aktives Lernen

Dynamische Programmierung

Aktives Lernen eignet sich besonders für dynamische Programmierung, weil Schülerinnen und Schüler durch das eigene Implementieren und Vergleichen von Algorithmen die abstrakten Konzepte der Rekursion, Memoisation und Tabellenbildung direkt erfahren. Die Kombination aus praktischer Anwendung und konkreten Beispielen hilft, die oft als trocken empfundene Theorie greifbar zu machen und die Vorteile von DP gegenüber naiven Ansätzen zu erkennen.

KMK BildungsstandardsKMK: Sekundarstufe II - Modellieren und ImplementierenKMK: Sekundarstufe II - Problemlösen und Handeln
20–50 Min.Partnerarbeit → Ganze Klasse4 Aktivitäten

Aktivität 01

Fallstudienanalyse30 Min. · Partnerarbeit

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.

Erklären Sie das Grundprinzip der dynamischen Programmierung und wann sie angewendet wird.

ModerationstippFordern Sie die Paare auf, während der Pair-Programming-Session systematisch die Anzahl der Funktionsaufrufe mit und ohne Memoisation zu zählen und in einer Tabelle festzuhalten, um den Unterschied sichtbar zu machen.

Worauf zu achten istGeben 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.

AnalysierenBewertenErschaffenEntscheidungsfähigkeitSelbststeuerung
Komplette Unterrichtsstunde erstellen

Aktivität 02

Fallstudienanalyse45 Min. · Kleingruppen

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.

Analysieren Sie, wie dynamische Programmierung die Effizienz bei überlappenden Teilproblemen verbessert.

ModerationstippTeilen Sie die Gruppen für die Rucksackaufgabe in zwei Teile: Eine Hälfte arbeitet tabellarisch von oben nach unten, die andere von unten nach oben, um den Vergleich der Ansätze direkt in der Klasse zu ermöglichen.

Worauf zu achten istStellen 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.

AnalysierenBewertenErschaffenEntscheidungsfähigkeitSelbststeuerung
Komplette Unterrichtsstunde erstellen

Aktivität 03

Fallstudienanalyse20 Min. · Ganze Klasse

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.

Entwerfen Sie eine dynamische Programmierlösung für ein Problem wie die Fibonacci-Folge.

ModerationstippLegen Sie für die Diskussion klare Kriterien fest, z.B. eine Liste mit Beispielproblemen, die nach DP-Tauglichkeit bewertet werden sollen, um die Argumentation zu strukturieren.

Worauf zu achten istDiskutieren 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.

AnalysierenBewertenErschaffenEntscheidungsfähigkeitSelbststeuerung
Komplette Unterrichtsstunde erstellen

Aktivität 04

Fallstudienanalyse50 Min. · Einzelarbeit

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.

Erklären Sie das Grundprinzip der dynamischen Programmierung und wann sie angewendet wird.

Worauf zu achten istGeben 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.

AnalysierenBewertenErschaffenEntscheidungsfähigkeitSelbststeuerung
Komplette Unterrichtsstunde erstellen

Vorlagen

Vorlagen, die zu diesen Informatik-Aktivitäten passen

Nutzen, bearbeiten, drucken oder teilen.

Einige Hinweise zum Unterrichten dieser Einheit

Erfahrene Lehrkräfte setzen dynamische Programmierung als Brücke zwischen Rekursion und effizienten Algorithmen ein und vermeiden es, DP als reine Technik zu unterrichten. Stattdessen zeigen sie zunächst an einfachen Beispielen wie der Fibonacci-Folge, wie naive Lösungen scheitern, und entwickeln dann gemeinsam mit den Schülerinnen und Schülern schrittweise die Optimierungsidee. Wichtig ist, den Fokus auf die Problemstruktur zu legen: Erst wenn überlappende Subprobleme und optimale Substruktur erkannt sind, macht DP Sinn. Vermeiden Sie es, DP als Zauberformel für jedes Optimierungsproblem zu präsentieren.

Erfolgreiches Lernen zeigt sich darin, dass Schülerinnen und Schüler nicht nur DP-Algorithmen korrekt umsetzen, sondern auch erklären können, warum bestimmte Probleme dafür geeignet sind und wie Speicher- und Laufzeitoptimierungen funktionieren. Sie sollten erkennen, wann DP sinnvoll ist und wann andere Methoden wie Greedy-Algorithmen besser passen.

Vorsicht vor diesen Fehlvorstellungen

  • Während der Pair-Programming-Aktivität 'Fibonacci mit DP' beobachten Sie, ob Schüler die Memoisation nur als Optimierung der Rekursion sehen oder erkennen, dass die Tabelle Subprobleme speichert und somit redundante Berechnungen vermeidet.

    Fragen Sie die Paare konkret, wie viele Male die Fibonacci-Funktion ohne DP für n=5 aufgerufen wird und wie viele mit DP. Die Diskrepanz macht den Unterschied zwischen rekursivem Aufrufstapel und Tabellenspeicherung deutlich.

  • Während der Gruppenaufgabe 'Rucksackproblem tabellarisch' achten Sie darauf, ob Schüler denken, DP sei ein universelles Werkzeug für alle Optimierungsprobleme.

    Fordern Sie die Gruppen auf, zwei weitere Probleme zu benennen: eines, das sich für DP eignet, und eines, das nicht. Diskutieren Sie im Plenum, welche Kriterien (überlappende Subprobleme, optimale Substruktur) erfüllt sein müssen.

  • Während der Individualaufgabe 'Eigene DP-Lösung entwerfen' achten Sie darauf, ob Schüler annehmen, DP erfordere immer große Speichermengen.

    Bitten Sie die Schülerinnen und Schüler, ihre Lösungen mit Memoisation und Tabellen zu vergleichen und die Speicheranforderungen zu dokumentieren. So erkennen sie, dass Top-down-Ansätze oft sparsamer sind.

In dieser Übersicht verwendete Methoden

Mehr in Datenstrukturen und Algorithmen

Grundlagen der Algorithmen

Die Schülerinnen und Schüler definieren Algorithmen und analysieren ihre Eigenschaften wie Endlichkeit, Eindeutigkeit und Effektivität.

2 methodologies

Arrays und Listen

Die Schülerinnen und Schüler vergleichen statische Arrays mit dynamischen Listen hinsichtlich ihrer Eigenschaften und Einsatzgebiete.

2 methodologies

Stacks und Queues

Die Schülerinnen und Schüler implementieren und analysieren die Funktionsweise von Stacks (LIFO) und Queues (FIFO) und deren Anwendungen.

2 methodologies

Binäre Bäume und Traversierung

Die Schülerinnen und Schüler untersuchen binäre Bäume als nicht-lineare Datenstrukturen und implementieren verschiedene Traversierungsverfahren.

2 methodologies

Graphen und ihre Darstellung

Die Schülerinnen und Schüler lernen Graphen als Modell für komplexe Beziehungen kennen und verschiedene Darstellungsformen (Adjazenzmatrix, Adjazenzliste).

2 methodologies