Lektion 10: Dynamic Programming

Diese Lektion behandelt dynamic programming (DP), eine vielfältige und mächtige Klasse von Algorithmen. Mit DP-Ansätzen kann man viele Probleme lösen, die auf den ersten Blick völlig unzugänglich erscheinen.

DP basiert auf einer Zerlegnung eines Problems in Teilprobleme, sodass sich die Lösung »irgendwie« aus den Lösungen der Teilprobleme zusammensetzen lässt; anders als bei divide&conquer sind aber deutlich flexiblere Varianten von »Zusammensetzen« möglich. Indem man sich alle schon gelösten Teilprobleme speichert, kann man zu effizienten Algorithmen für komplizierte Probleme kommen.

Lernziele

• Prinzip von dynamic programming kennen,
• DP-Algorithmen für (einfache) Probleme entwerfen können.

Material

Die Videos entstammen der Aufzeichung der Vorlesung Introduction to Algorithms von Erik Demaine und Srinivas Devadas. Die Videos sind Teil der MIT Open Courseware.

Die Videos dieser Lektion sind nicht Teil (des Klausur-relevanten Stoffes von) von A&DS. Sie sind hier gesammelt, weil ich Interessierten die Videos nicht vorenthalten möchte.

1 – Introduction to DP: Fibonacci numbers

In diesem Video führt Demaine anhand eines einfachen Beispiels (der Berechnung der Fibonacci-Zahlen) die Idee von DP ein.

Der zweite Teil (den wir hier auslassen) betrachtet den Bellman-Ford Kürzeste-Wege-Algorithmus durch die DP-Brille.

2 – DP-Algorithms: Text Justification

In diesem Video gibt Demaine den ersten »echten« DP-Algorithmus für ein Problem, das sich anderweitig wohl gar nicht lösen ließe: Die Berechnung guter Positionen für Zeilenumbrüche für Text im Blocksatz. Das vorgestellte Verfahren ist eine nur leicht vereinfachte Version des tatsächlich in der Praxis erfolgreichsten Verfahrens. (Im Wesentlichen fehlt die Möglichkeit der Silbentrennung.)

3 – DP-Algorithms: Edit Distance

Als zweites »echtes« Beispiel, wir betrachten die Berechnung der edit distance, einem Maß für die »Ähnlichkeit« zweiter Strings. Varianten des vorgestellten Algorithmus spielen in der Bioinformatik eine große Rolle um beispielsweise DNA-Stränge verschiedener Individuen zu vergleichen.