CATEGORIES‚ RELATIONS AND DYNAMIC PROGRAMMING

Abstract

Dynamic programming is a strategy for solving optimisation problems. In this thesis, it is shown how many problems that may be solved by dynamic programming are instances of the same abstract specification. This specification is phrased using the calculus of relations offered by tapas theory. The main theorem that underlies dynamic programming can then be proved by straightforward equational reasoning. This is the first contribution of this thesis: to provide an elegant formulation of dynamic programming in a categorical setting.