Advanced Dynamic Programming

:: Advanced Dynamic Programming SS 2012 ::

Vorlesung

Termin: Montag 10 - 12, U10-146
Veranstalter: Georg Sauthoff

Folien zur Vorlesung

Session 1: Introduction: adp1-Intro.pdf
Session 2: Review and critique of classical DP: adp2-Classic.pdf
Slides from invited talk at JOBIM2007: jobim.pdf, use especially slides 5 -- 26
Example implementation of a simple aligment score computation and backtracing scheme: ali.cc
Session 3: ADP Theory 1: adp3-Basics.pdf
Example word generator for CFGs: gen.lhs
Session 4: ADP Theory 2: adp4-Bellman.pdf
Examples of testing Bellman's Principle: bp.lhs (call it via ghci)
Session 4a: Introduction to Bellman's GAP
Session 5: ADP Theory 3: adp5-Products.pdf
Session 6: The ADP language: adp6-Language.pdf
Session 7: Efficiency matters: adp7-Efficiency.pdf
Session 8: Bellman's GAP: adp8-BellmansGAP.pdf
Session 9: Stochastic models: adp9-Stochastics.pdf
Session 10: Ambiguity: adp10-Ambiguity.pdf
Session 11: Classified DP: adp11-Classified.pdf
Session 12: Solving Satisfiability with ADP adp12-Satisfiability.pdf
Session 13: Reconstructing duplication histories of minisatellites adp13-minisatellite.pdf

background report

Session 14: Problem Session: Bring your questions and problems!

Literatur zur Vorlesung

Just for fun: The Oldest DP Problem in the world
R. Giegerich, C. Meyer and P. Steffen. A Discipline of Dynamic Programming over Sequence Data , SCP, 51(3), 2004.
P. Steffen and R. Giegerich. Versatile and declarative dynamic programming using pair algebras. BMC Bioinformatics, 6(224), 2005.
J. Reeder, P. Steffen, and R. Giegerich: Effective ambiguity checking in biosequence analysis. In BMC Bioinformatics, 6(153) , 2005.
C. Braband, R. Giegerich, and A. Moeller: Analyzing ambiguity of context-free grammars. In Proc. 12th Int. Conf. on Implementation and Application of Automata, CIAA '07, 2007.
Richard Bellman: Dynamic Programming. Princeton University Press, 1975.
Dan Gusfield: Algorithms on strings, trees and sequences. Cambridge University Press, 1997.
Durbin, Eddy, Krogh, Mitchison: Biological Sequence Analysis. Cambridge University Press, 1998.

Bellman's GAP Café enthält eine noch umfangreichere Literatursammlung und einige Beispiele. Viele Beispiele zu Dynamic Programming finden sich auch auf den alten ADP-Seiten und einen interaktiven Kurs zu DP gibt es auch.

Übungen zur Vorlesung:

Termin: Mi: 16-18, M3-115
Veranstalter: Stefan Janssen, M3-114