Towards a discipline of dynamic programming
| dc.contributor.author | Giegerich, Robert | |
| dc.contributor.author | Meyer, Carsten | |
| dc.contributor.author | Steffen, Peter | |
| dc.contributor.editor | Schubert, Sigrid E. | |
| dc.contributor.editor | Reusch, Bernd | |
| dc.contributor.editor | Jesse, Norbert | |
| dc.date.accessioned | 2019-11-28T09:31:13Z | |
| dc.date.available | 2019-11-28T09:31:13Z | |
| dc.date.issued | 2002 | |
| dc.description.abstract | Dynamic programming is a classic programming technique, applicable in a wide variety of domains, like stochastic systems analysis, operations research, combinatorics of discrete structures, ow problems, parsing ambiguous languages, or biosequence analysis. Yet, heretofore no methodology was available guiding the design of such algorithms. The matrix recurrences that typically describe a dynamic programming algorithm are di cult to construct, error-prone to implement, and almost impossible to debug. This article introduces an algebraic style of dynamic programming over sequence data. We de ne its formal framework including a formalization of Bellman's principle. We suggest a language for algorithm design on a convenient level of abstraction. We outline three ways of implementation, including an embedding in a lazy functional language. The workings of the new method are illustrated by a series of examples from diverse areas of computer science. | en |
| dc.identifier.isbn | 3-88579-348-2 | |
| dc.identifier.pissn | 1617-5468 | |
| dc.identifier.uri | https://dl.gi.de/handle/20.500.12116/30280 | |
| dc.language.iso | en | |
| dc.publisher | Gesellschaft für Informatik e.V. | |
| dc.relation.ispartof | Informatik bewegt: Informatik 2002 - 32. Jahrestagung der Gesellschaft für Informatik e.v. (GI) | |
| dc.relation.ispartofseries | Lecture Notes in Informatics (LNI) - Proceedings, Volume P-19 | |
| dc.title | Towards a discipline of dynamic programming | en |
| dc.type | Text/Conference Paper | |
| gi.citation.endPage | 44 | |
| gi.citation.publisherPlace | Bonn | |
| gi.citation.startPage | 3 | |
| gi.conference.date | 30. September - 3. Oktober 2002 | |
| gi.conference.location | Dortmund | |
| gi.conference.sessiontitle | Regular Research Papers |
Dateien
Originalbündel
1 - 1 von 1