Depuis le début de votre cursus en NSI vous avez déjà abordé des techniques générales d'algorithmique :
Les algorithmes gloutons
la récursivité
diviser pour régner
...
Ces techniques ne consistent pas en la simple résolution d'un problème (recherche de maximum, calcul de moyenne, tri de tableau), mais sont bien des principes généraux qui nous aident, dans certains cas, à résoudre des problèmes complexes.
Nous allons maintenant aborder un nous principe algorithmique : la programmation dynamique
Programmation dynamique : les principes
La programmation dynamique est un principe algorithmique permettant d'améliorer la complexité temporelle de la résolution d'un problème dans certaines situations.
Cette définition est un peu vague et nous en verrons une plus précise par la suite. Nous retrouverons dans cette partie des notions de récursivité et même des similitudes avec le principe de diviser pour régner.
Nous allons donc tenter de ...
distinguer la programmation dynamique de ces différentes situations
définir les principes de la programmation dynamique
mettre en applications les principes de la programmation dynamique dans différentes situations.
Mais nous allons commencer par un exemple que vous avez déjà vu en récursivité.
La suite de Fibonacci
La suite de Fibonacci a été inventée au Moyen-Age dans le but de tenter de modéliser l'évolution d'une population de lapins ( plus de détails ici
par exemple )
Elle est définie ainsi :
pour n = 0 : F0 = 0
pour n = 1 : F1 = 1
pour n >=2 : Fn = Fn-1 + Fn-2
→ en dehors des deux premiers cas, chaque terme de la suite de Fibonacci est donc égal à la somme des deux termes précédents :
n
Fn
0
0
1
1
2
0 + 1 = 1
3
1 + 1 = 2
4
1 + 2 = 3
5
2 + 3 = 5
6
3 + 5 = 8
...
...
Vous avez déjà programmé cette suite grâce à une fonction récursive que vous pouvez voir ci-dessous :
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return fib(n-2)+fib(n-1)
Cette écriture est très simple, et très lisible : on retrouve bien à la ligne 10 la définition de la suite de Fibonacci pour n >=2
Cependant, la complexité en temps de cette fonction est très mauvaise, elle est de l'ordre de 2n ( exactement 1,6n ), c'est à dire exponentielle.
Ne cherchez même pas à calculer le terme de rang n = 1000, le temps est déjà très long pour n = 50 !
Nous allons donc tenter d'optimiser cette fonction grâce au principe de la programmation dynamique.
Pour cela nous allons analyser les appels récursifs réalisés lors de l'appel de fib(6).
Une fois que tout ces appels sont réalisés, il faut bien sur les additionner en "remontant l'arbre"...Vous pouvez imaginer la complexité du processus pour fib(30) !
On peut remarquer qu'ici, si la récursivité présente un code particulièrement lisible, mais ce code n'est pas efficace du tout !
Si l'on regarde de plus près l'arbre précédent, on peut constater que l'on fait plusieurs fois la même chose :
On calcule par exemple deux fois le terme fib(4) et même si l'on analyse encore plus ...
On peut remarquer que l'on calcule 3 fois fib(3) et 5 fois fib(2)...
Il va falloir optimiser tout cela grâce à la programmation dynamique.
Nous allons travailler par mémoïsation (non ce n'est pas une faute de frappe !), c'est à dire que l'on va conserver les résultats intermédiaires dans un tableau afin de remplacer un nouveau calcul par un appel mémoire, beaucoup plus économe en temps.
La mémoïsation fait partie de la programmation dynamique.
def fibonacciProgDyna(n):
tableau = [None] * (n+1)
return fibonacciRec(n, tableau)
def fibonacciRec(n, tableau):
if tableau[n] != None:
return tableau[n]
if n == 0 or n == 1:
tableau[n] = n
else:
tableau[n] = fibonacciRec(n-1, tableau) + fibonacciRec(n-2, tableau)
return tableau[n]
Nous pouvons constater que dans ce code :
La structure est assez proche de celle de la version récursive
Les résultats sont stockés dans un tableau.
Le calcul nécessite de travailler sur deux fonctions (la création du tableau de mémoïsation ne peut pas se faire à l'intérieur de la fonction récursive).
Avant d’effectuer les appels récursifs on vérifie que le terme n’a pas déjà été calculé. Chaque valeur n’est donc calculée qu’une seule fois.
Le code précédent propose une approche mettant en œuvre la récursivité et la mémoïsation, c'est une des deux approches de la programmation dynamique. Elle est appelée aussi "du haut vers le bas" ou encore "top-down" car elle part du haut de l'arbre des appels récursifs vu précédemment.
Les deux codes de calcul de la suite de Fibonacci ne sont pas si différents finalement. Nous allons tenter de tester leur efficacité.
Tester la durée de calcul du 30ème terme de la suite de Fibonacci avec les deux fonctions ci-dessus. Pour cela vous pourrez utiliser le module timeit que vous avez déjà utilisé lors de l'étude sur les dictionnaires.
Vous utiliserez un code du type :
Il existe aussi une autre approche possible en programmation dynamique, "du bas vers le haut" ou encore "bottom-up". Cette approche consiste à parcourir l'arbre ds appels récursifs en partant du bas.
On remarque alors que dans ce cas, il n'est plus nécessaire de faire appel à la récursivité.
Le code correspondant pour calculer la suite de Fibonacci serait :
def fiboBottomUp(n):
f = [None]*(n+1)
f[0] = 0
f[1] = 1
for i in range(2, n+1):
f[i] = f[i-1] + f[i-2]
return f[n]
On peut également remarquer que :
la dénomination "de bas en haut" est justifiée, on part bien du bas de l'arbre et on le remonte jusqu'à la racine.
le code ressemble beaucoup à ce que l'on à fait "à la main" dans le tableau de présentation de la suite de Fibonacci.
Dans le cas de la suite de Fibonacci, la programmation dynamique du bas vers le haut est en fait la solution "naïve" de résolution du problème.
Comme dans la solution "du haut vers le bas", les résultats intermédiaires sont stockés dans un tableau.
Pour conclure sur cet exemple, On peut remarquer que l'exemple de la suite de Fibonacci peut tout à fait être réglé de façon efficace sans récursivité ni programmation dynamique et donc sans les inconvénients de la mémoïsation...
def fibonacci(n):
#initialisation
n0, n1=0, 1
if n == 0:
return n0
elif n == 1:
return n1
# pour n supérieur à 1
else :
for i in range (2, n+1):
f = n0 + n1
n0 = n1
n1 = f
return f
Les principes fondamentaux de la programmation dynamique
Dans quelle situations utilises-t-on la programmation dynamique ?
La programmation dynamique résout un problème, comme "diviser pour régner", en combinant les solutions de sous problèmes similaires mais plus petits.
Contrairement à "diviser pour régner" les sous problèmes ne sont pas complémentaires (par exemple la recherche dans le tableau gauche ou le tableau droit lors d'une recherche par dichotomie)
Dans la programmation dynamique, les sous problèmes se chevauchent (comme les différents appels récursif lors du calcul de la suite de Fibonacci)
Les sous problèmes se "chevauchant", il est possible
Soit de stocker les résultats intermédiaires pour éviter de les calculer plusieurs fois. C'est la mémoïsation
Soit aborder le problème "de bas en haut" (en partant du bas de l'arbre représentant le problème) avec la possibilité là aussi de stocker les résultats intermédiaires.
Le mot "programmation" dans "programmation dynamique", ne fait par référence à l'utilisation d'un langage de programmation, mais plutôt comme synonyme de planification et ordonnancement
Contrairement à la récursivité, il n'est pas aisé de reconnaître la programmation dynamique dans un programme ou un algorithme.
Cependant à chaque fois que l'on utilise la récursivité il est important de se demander si une optimisation mettant en œuvre la programmation dynamique n'est pas envisageable.
Comment construire un code en programmation dynamique ?
Pour concevoir une fonction en programmation dynamique, il faut le plus souvent:
Repérer les sous problèmes.
Identifier une relation de récurrence entre les sous problèmes.
Repérer les chevauchements possibles (par exemple en construisant un arbre d'appels liés à la relation de récurrence).
En déduire l'algorithme correspondant :
Soit grâce à la récursivité et la mémoïsation (programmation dynamique de haut en bas)
Soit grâce au stockage des résultats successifs dans un tableau (programmation dynamique de bas en haut)
Comme vous pouvez le constater, pour les principes algorithmiques précédents (Les algorithmes gloutons, la récursivité, diviser pour régner...) il était relativement clair d'identifier un programme suivant un de ces principes.
Pour la programmation dynamique nous dirons que l'identification est plus fine...
Un peu d'histoire...
La programmation dynamique date des années 1950. On la doit à Richard Bellman, un chercheur américain. Il explique l'idée du terme programmation dynamique dans son autobiographie, "Eye of the Hurricane" :
"Les années 50 n'étaient pas de bonnes années pour la recherche mathématique. le mot "dynamique" a une propriété très intéressante en tant qu'adjectif, et qu'il est impossible d'utiliser le mot dynamique dans un sens péjoratif. Ainsi, je pensais que la programmation dynamique était un bon nom. C'était quelque chose auquel même un membre du Congrès ne pouvait s'opposer. Alors je l'ai utilisé comme parapluie pour mes activités. »
Cette expression de programmation dynamique n'est pas initialement un terme d'informatique, mais il désigne une technique de résolution de problème plus globale. On remarque aussi que le choix de ce terme n'est pas forcément guidé par une réalité scientifique mais plus un choix "politique".
*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper*
"What's that equal to?"
*counting* "Eight!"
*writes down another "1+" on the left*
"What about that?"
*quickly* "Nine!"
"How'd you know it was nine so fast?"
"You just added one more"
"So you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'"
