Salut à toi, élève de NSI, comment puis-je t'aider ?
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é.
Un exemple : 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
...
...
Implémentation "naïve"...
L'implémentation récursive est la suivante :
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return fib(n-2)+fib(n-1)
print(fib(10))
Cette écriture est très simple, et très lisible : on retrouve bien à la ligne 9 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 !
Pour expliquer cela, nous allons analyser les appels récursifs réalisés lors de l'appel de fib(6) :
Arbre des appels récursifs pour n = 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 le même calcul :
→ 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.
Et pour cela, deux possibilités existent :
La mémoïsation ( approche "top-bottom" )
Nous pouvons travailler par mémoïsation (non ce n'est pas une faute de frappe !) :
La mémoïsation consiste à conserver les résultats intermédiaires afin de pouvoir les réutiliser au besoin plus tard, de façon à remplacer
un nouveau calcul par un simple appel mémoire, beaucoup plus économe en temps.
def fib_memo(n, tab):
if tab[n] != None:
return tab[n]
if n == 0 or n == 1:
tab[n] = n
else:
tab[n] = fib_memo(n-1, tab) + fib_memo(n-2, tab)
return tab[n]
n = 30
results = [None]*(n+1)
print(fib_memo(n, results))
La structure est assez proche de celle de la version récursive
Les résultats sont stockés dans un tableau : l'indice de chaque élément de ce tableau correspond à une valeur de n.
avant de faire les appels récursifs, on vérifie tout d'abord que le terme de rang n n’a pas déjà été calculé : si c'est le cas, on renvoie simplement ce résultat,
sinon, on réalise effectivement les appels récursifs.
Chaque résultat n’est donc calculé qu’une seule fois.
Les deux codes de calcul de la suite de Fibonacci ne sont pas si différents finalement. Nous allons tenter de tester leur efficacité.
from timeit import timeit
n = 30
results = [None]*(n+1)
print('fib(n) : ', timeit(stmt = 'fib(n)', globals = globals(), number = 10)) # version récursive
print('fib_memo(n) : ', timeit(stmt = 'fib_memo(n, results)', globals = globals(), number = 10)) # version récursive
Avantage : une bien moindre complexité puisqu'on supprime un (très) grand nombre d'appels récursifs.
Inconvénient : nécessite une mémoire supplémentaire pour stocker les résultats ( lors qu'un seul nous intéresse...)
Approche "bottom-up"
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 des appels récursifs, mais en partant du bas :
on part des résultats dont on connaît la valeur
à partir d'eux, on calcule les résultats suivants, et on les stocke pour pouvoir les réutiliser ensuite.
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 fib_botup(n):
f = [None]*(n+1) # tableau des résultats
f[0] = 0 # résultats
f[1] = 1 # déjà connus
for i in range(2, n+1): # calcul des résultats successifs,
f[i] = f[i-1] + f[i-2] # et stockage pour réemploi ultérieur.
return f[n]
print(fib_botup(30))
On peut 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.
On peut même souvent encore optimiser le code : le stockage de tous les résultats intermédiaires n'est pas indispensable, seuls les deux
derniers sont utiles pour calculer un terme donné :
def fib_optim(n):
# Initialisation
n0, n1 = 0, 1
if n == 0:
return n0
elif n == 1:
return n1
# Pour n supérieur à 1
for i in range (2, n+1):
f = n0 + n1 # calcul du terme courant;
n0 = n1 # l'avant-dernier devient le dernier,
n1 = f # le dernier devient le courant.
return f
print(fib_optim(30))
Les principes fondamentaux de la programmation dynamique
Dans quelles situations utilise-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.
Cependant :
avec l'approche "diviser pour régner", les sous-problèmes sont indépendants les uns des autres (par exemple, la recherche dans
le tableau gauche OU le tableau droit lors d'une recherche par dichotomie );
en programmation dynamique, les sous-problèmes doivent se "chevaucher" : le calcul d'un résultat dépend du calcul d'un (ou d') autre(s)
résultat(s) ( comme par exemple, 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'"
