Dynamic Programming is concerned with the optimization problems defined over search spaces of exponential size, yet allowing exact solution in polynomial space and time. It is on of the earliest computational paradigms, in fact developed by mathematicians before the term computer science had been established. Interest in dynamic programming has increased dramatically, as manyfold problems arising in biosequence analysis lend themselves to dynamic programming solutions. Still, the successful construction of a dynamic programming algorithm is a matter of experience, talent and luck.
The lecture will introduce dynamic programming using classical examples from biosequence analysis. It will then introduce the recent algebraic method of dynamic programming, which increases programming productivity by an order of magnitude.
Richard Bellman: Dynamic Programming.Princeton University Press, 1975.
Dan Gusfield: Algorithms on strings, trees and sequences.Cambridge University Press, 1997.
Durbin, Eddy, Krogh, Mitchell: Biological Sequence Analysis.Cambridge University Press, 1998.
Rhythmus | Tag | Uhrzeit | Format / Ort | Zeitraum |
---|
Modul | Veranstaltung | Leistungen | |
---|---|---|---|
39-M-Inf-ADP Algebraische Dynamische Programmierung | Algebraische Dynamische Programmierung | Studieninformation | |
- | benotete Prüfungsleistung | Studieninformation |
Die verbindlichen Modulbeschreibungen enthalten weitere Informationen, auch zu den "Leistungen" und ihren Anforderungen. Sind mehrere "Leistungsformen" möglich, entscheiden die jeweiligen Lehrenden darüber.
Studiengang/-angebot | Gültigkeit | Variante | Untergliederung | Status | Sem. | LP | |
---|---|---|---|---|---|---|---|
Bioinformatik und Genomforschung / Master | (Einschreibung bis SoSe 2012) | Vertiefung Sequenzanalyse | Wahlpflicht | 2. | 5 | unbenotet LP V+Ü | |
Naturwissenschaftliche Informatik / Diplom | (Einschreibung bis SoSe 2004) | BioI | HS | ||||
Naturwissenschaftliche Informatik / Master | (Einschreibung bis SoSe 2012) | Vertiefung Sequenzanalyse | Wahlpflicht | 2. | 5 | unbenotet LP für V+Ü |