Informatik Algorithmen – Dynamische Programmierung
Karteikarten zum Thema „Informatik“ · 15 Karten · von atrio. Beispiele: Was sind die zwei Voraussetzungen für Dynamische Programmierung? · Was ist der Unters…
Karten
15 KartenWas sind die zwei Voraussetzungen für Dynamische Programmierung?
Rückseite
Optimale Substruktur (optimale Lösung enthält optimale Teillösungen) und überlappende Teilprobleme (gleiche Teilprobleme werden mehrfach berechnet).
Was ist der Unterschied zwischen Memoization und Tabulation?
Rückseite
Memoization ist Top-Down: rekursiver Aufruf mit Cache. Tabulation ist Bottom-Up: iteratives Befüllen einer Tabelle ohne Rekursion.
Wie lautet die Rekursionsformel für die Fibonacci-Folge mit DP?
Rückseite
F(n) = F(n-1) + F(n-2) mit Basisfällen F(0)=0, F(1)=1. Ohne DP exponentiell, mit DP linear in Zeit und Speicher.
Wie definiert man den Zustand beim 0/1-Rucksackproblem?
Rückseite
dp[i][w] = maximaler Wert mit den ersten i Gegenständen bei Gewichtslimit w. Übergang: nehmen (Wert + dp[i-1][w-gewicht]) oder weglassen (dp[i-1][w]).
Was ist der Unterschied zwischen 0/1-Rucksack und unendlichem Rucksack?
Rückseite
0/1: jeder Gegenstand maximal einmal → Iteration über Gewichte absteigend. Unendlich: beliebig oft → Iteration aufsteigend, gleicher Index bleibt verfügbar.
Wie berechnet man die Länge der längsten gemeinsamen Teilfolge (LCS)?
Rückseite
dp[i][j] = LCS-Länge der Präfixe A[1..i], B[1..j]. Gleichheit: dp[i-1][j-1]+1. Ungleichheit: max(dp[i-1][j], dp[i][j-1]).
Wie rekonstruiert man die optimale Lösung aus der DP-Tabelle?
Rückseite
Rückwärts vom Tabellenende: bei Entscheidungsgleichheit (Wert unverändert) Pfad nach oben/links, bei Wertänderung gewählten Gegenstand/Zeichen notieren und diagonal/entsprechend weitergehen.
Wann ist Dynamische Programmierung nicht geeignet?
Rückseite
Bei fehlender optimaler Substruktur (z. B. längster Pfad in Graphen mit Zyklen), fehlenden überlappenden Teilproblemen oder wenn Gierige Strategie optimal ist (z. B. Aktivitätsauswahl).
Wie optimiert man den Speicher bei Fibonacci-DP auf O(1)?
Rückseite
Nur die letzten zwei Werte speichern (prev, curr), da dp[n] nur von dp[n-1] und dp[n-2] abhängt. Tabelle entfällt vollständig.
Was bedeutet 'optimale Substruktur' konkret?
Rückseite
Eine optimale Lösung des Gesamtproblems enthält optimale Lösungen aller Teilprobleme. Ohne diese Eigenschaft funktioniert DP nicht (z. B. längster einfacher Pfad).
Wie erkennt man überlappende Teilprobleme im Rekursionsbaum?
Rückseite
Derselbe Parameterkombination (z. B. fib(3)) erscheint mehrfach im Baum. Ohne Cache wird identische Arbeit wiederholt – genau das nutzt DP aus.
Wie lautet die Zeitkomplexität beim 0/1-Rucksack mit DP?
Rückseite
O(n × W) mit n Gegenständen und Kapazität W. Pseudopolynomiell, da W vom Zahlenwert abhängt, nicht von der Eingabelänge (log W).
Was ist der Unterschied zwischen Teilfolge und Teilstring?
Rückseite
Teilfolge: Elemente in Reihenfolge, nicht notwendigerweise zusammenhängend (LCS). Teilstring: zusammenhängender Block (longest common substring → andere DP-Formel).
Welche Fallstricke gibt es bei der DP-Implementierung?
Rückseite
Falsche Basisfälle, Off-by-one-Fehler bei Indizes, vergessene Initialisierung, falsche Iterationsrichtung (bei 0/1-Rucksack absteigend), Speicherzugriff außerhalb der Tabelle.
Wie löst man 'Edit Distance' (Levenshtein-Distanz) mit DP?
Rückseite
dp[i][j] = min. Operationen (Einfügen, Löschen, Ersetzen) für A[1..i] → B[1..j]. Gleichheit: dp[i-1][j-1]. Ungleichheit: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).