FU Berlin, Fachbereich Mathematik und Informatik, Institut für Informatik
Prof. Dr. Knut Reinert lädt ein:
Making Dynamic Programming Fun
Prof. Dr. Robert Giegerich
Faculty of Technology, Bielefeld University
Dynamic programming (DP) is a widely used programming technique in
bioinformatics and beyond. It solves combinatorial optimization problems by
recursive decomposition and tabulation of intermediate results. DP looks
straightforward with textbook-size examples, but tends to become quite difficult
with real world tasks. DP algorithms are often intricate to develop, difficult
to implement, tedious to debug, and impossible to re-use. They also are
considered theoretically boring - in other words, DP is no fun at all.
This has started to change recently. The discipline of ALGEBRAIC dynamic
programming has added some theory and abstraction mechanisms to the DP
programming paradigm. It advocates a strict separation between the control
structure of a DP algorithm and the scoring scheme employed. The former is
modelled by tree grammars producing strings, and the latter by signatures and
algebras. No recurrences, no subscripts, (almost) no errors.
This offers a number of conveniences, but the fun really starts with the
introduction of a generic product operation on scoring schemes, such that the
same algorithm can be run using two or more scoring schemes simultaneously. The
clue of the product operation lies with an asymmetric combination of two
different optimization objectives. This leads to a surprising variety of
applications. We discuss backtracing, enumeration of multiple, co-optimal or
near-optimal solutions, redundancy checking, maximizing or minimizing under
lexicographic orderings, and holistic evaluation of the search space. All these
tasks can be achieved by suitable product schemes, with no added programming
effort.
Ort: Takustr. 9, SR 049 Zeit: Fr, 2.12.2005, 14 Uhr c.t., Kaffee/Tee ab 13.45 im Raum 137
[ home ] [ up ] | webmaster@inf.fu-berlin.de |