Faculty of Technology Bielefeld University

Advanced Dynamic Programming

Veranstalter: Prof. Dr. Robert Giegerich (mail: robert@techfak.uni-bielefeld.de)
Termin: Montag 10 - 12, U10-146
Semester: SS 2013
Veranstaltungsart: Vorlesung
EKVV: SS2013_392107 bzw. 37010218

Vorlesung

Folien zur Vorlesung

• Introduction
• Review and critique of classical DP
  • 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
• ADP Theory (Basics)
  • Example word generator for CFGs: gen.lhs
• Bellman's Principle of Optimality
  • Examples of testing Bellman's Principle: bp.lhs (call it via ghci)
• Introduction to Bellman's GAP
• Products of Algebras
• ADP as embedded Domain Specific Language (eDSL)
  • Parser combinators example (parsing bibtex files): parse.lhs
  • Haskell ADP Combinators repository
  • Interactive testing of ADP combinators
• Efficiency matters
• Compiling ADP
• 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
  with background report by M. Wilhelm
• 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:

Veranstalter: Stefan Janssen (office: M3-114)
Termin: Mi: 16-18, M3-115
Semester: SS 2012
Veranstaltungsart: Übung
EKVV: SS2012_392108 bzw. 29554060

• Übungsblatt 2 (edit distance)
• Übungsblatt 3 (tree grammars)
• Übungsblatt 4 (btrees)
• Übungsblatt 5 (palindromes)
• Übungsblatt 6 (efficiency)

$Date: 2013/06/05 14:25:07 $