Kapitel 2
Wie funktioniert Dynamic Programming für Subset Sum?
Wie funktioniert Dynamic Programming für Knapsack?
Welche anderen Beispiele und Prinzipien gibt es?
Vorlesung 3
- Datum: Donnerstag, 07.05.2020
- Inhalt: Dynamic Programming für Subset Sum
- Video: VL3 bei YouTube
- Folien:
HIER (PDF, 31MB)
- Weitere Links:
Wikipedia-Seite zu Dynamic Programming
Vorlesung 4
- Datum: Donnerstag, 14.05.2020
- Inhalt: Dynamic Programming für Knapsack; Dynamic Programming für zwei geometrische Probleme
- Video: VL4 bei YouTube
- (Korrigierte) Folien:
HIER (PDF, 26MB)
- Weitere Links:
Dynamic Programming by Richard Bellman, 1957 (Originalarbeit als PDF)
Finding a largest convex subset at Stack Overflow
On the Chromatic Art Gallery Problem (Forschungsartikel von 2014, gezeigt hatte ich das Bild auf Seite 5.)
A graphical introduction to Dynamic Programming (ganz nett gestaltet, erstes Beispiel ist die Berechnung der Fibonacci-Zahlen, also gut zugänglich)
(Wieso ist die zweite Methode schneller - und wie bekommt man das hin?)
Übung 2
- Datum: Mittwoch, 20.05.2020
- Inhalt: Dynamic Programming, Longest Common Subsequence
- Video: U2 bei YouTube
- Folien: HIER (PDF, 0.99MB)
- Weitere Links:
Video zu Matrix Chain Multiplication. (Disclaimer: Das ist nach der Übung noch spontan entstanden.)