Programmation dynamique : ce n’est pas ce que vous pensez

Le terme « programmation dynamique » dans les études d’algorithmes est souvent source de confusion. « Dynamique » ne fait pas référence à sa variabilité, mais plutôt à l’aspect planification de la « programmation », provenant des années 1950, lorsque les ingénieurs planifiaient les projets de construction comme des « planifications de processus ». En informatique, la programmation dynamique signifie planifier l’ordre des sous-étapes nécessaires pour résoudre un problème. Par exemple, pour calculer la suite de Fibonacci, le « programme » est la séquence d’étapes pour calculer fib(2) à fib(10) dans l’ordre des dépendances. Cela peut être planifié de haut en bas ou de bas en haut ; le plan final est le même, et les deux sont considérés comme de la programmation dynamique. Richard Bellman a inventé ce terme pour éviter l’aversion d’un secrétaire à la Défense pour la « recherche mathématique », choisissant habilement « programmation dynamique » parce que l’adjectif « dynamique » ne peut pas être utilisé de manière péjorative.