FU Berlin, Fachbereich Mathematik und Informatik, Institut für Informatik

Vortrag des Informatik-Kolloquiums 

Prof. Dr. Knut Reinert lädt ein:

 Making Dynamic Programming Fun

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