Programmation dynamique polymorphe, vérifiable et efficace

Mattéo Delabre (chargé de cours, DIRO) — André-Aisenstadt 1207

16/02/2024 à 12h30

La programmation dynamique est une technique permettant de résoudre efficacement certains problèmes d’optimisation combinatoire. Elle est appliquée avec succès dans des domaines aussi variés que la recherche opérationnelle, la bio-informatique, l’intelligence artificielle ou la linguistique. Les algorithmes en programmation dynamique sont classiquement développés et présentés sous forme de tables et d’équations de récurrence. Cette approche limite cependant les possibilités de réutilisation et rend l’implantation sujette à des bogues. La programmation dynamique algébrique propose de pallier ces problèmes en séparant les aspects de description de l’espace des solutions, d’évaluation et de sélection des candidats, et d’efficacité du calcul. Après des rappels sur les bases de la programmation dynamique, nous introduirons sa déclinaison algébrique et démontrerons qu’elle facilite la conception, la réutilisation et la vérification des algorithmes.