Greedy and dynamic programming by calculation

Abstract

The mathematical study of the greedy algorithm provides a blueprint for the study of Dynamic Programming (DP), whose body of knowledge is largely unorganized, remaining obscure to a large part of the software engineering community. This study aims to structure this body of knowledge, narrowing the gap between a purely examplebased approach to DP and its scientific foundations. To that effect, matroid theory is leveraged through a pointfree relation algebra, which is applied to greedy and DP problems. A catalogue of such problems is compiled, and a broad characterization of DP algorithms is given. Alongside, the theory underlying the thinning relational operator is explored.

O estudo matemático do algoritmo ganancioso («greedy») serve como guia para o estudo da programação dinâmica, cujo corpo de conhecimento permanece desorganizado e obscuro a uma grande parte da comunidade de engenharia de software. Este estudo visa estruturar esse corpo de conhecimento, fazendo a ponte entre a abordagem popular baseada em exemplos e os métodos mais teóricos da literatura científica. Para esse efeito, a teoria dos matroides é explorada pelo uso de uma álgebra de relações pointfree, e aplicada a problemas «greedy» e de programação dinâmica. Um catálogo de tais problemas é compilado, e é feita uma caraterização geral de algoritmos de programação dinâmica. Em paralelo, é explorada a teoria do combinador relacional de «thinning».