Il existe un type de problème qui est résoluble en combinant les solutions des sous-problèmes qui le composent. C'est le cas par exemple de la méthode diviser-pour-régner. Mais contrairement à un algorithme de tri diviser-pour-régner, les sous-problèmes ne sont pas toujours indépendants et un traitement récursif peut faire apparaître les mêmes sous-problèmes plusieurs fois.
Répéter des calculs identiques est coûteux en temps machine et complexité. Une stratégie peut être de conserver les résultats des sous-problèmes dans un tableau par exemple. Ainsi, plutôt que d'effectuer N fois le même appel de fonction récursif (avec les mêmes paramètres), on peut lire le résultat qu'on a stocké dans le tableau après le premier appel: c'est le principe de la programmation dynamique.
En résumé, la méthode de la programmation dynamique:
On définit la suite de Fibonacci par
Calculer à la main.
Écrire la fonction récursive
fibo_rec(n: int)
qui implémente la suite de Fibonacci et renvoie le terme de rang .
On peut tester la bonne implémentation de la suite de Fibonacci sur quelques-unes de ces valeurs:
55 | 89 | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 | 6765 |
Écrire à la main l’arbre des appels à
fibo_rec
lorsqu'on exécutefibo_rec(5)
.
Vocabulaire: En informatique le terme mémoïsation désigne la sauvegarde des valeurs de retour d'une fonction selon ses valeurs d'entrée. Dans le cadre de la programmation dynamique, on peut utiliser le mot "mémorisation" et "mémoïsation" de façon interchangeable, le second étant plus précis.
Exécuter la fonction
fibo_rec(50)
. Quel est le problème?
On peut améliorer la complexité en implémentant la suite de Fibonacci en mémoïsant les appels à notre fonction à l'aide d'un dictionnaire.
L'algorithme top-down est proche de l'implémentation naïve fibo_rec
mais avec de la mémoïsation. Pour cet algorithme, on peut utiliser un dictionnaire associant la clé à la valeur de comme représenté ci-dessous:
memo = {
# n: F(n)
0: 0,
1: 1,
2: 1,
...
}
Ainsi, avant chaque appel de la fonction récursive au rang , on vérifie si n'est pas déjà présent dans le dictionnaire, auquel cas on peut se contenter de lire sa valeur. Sinon on sauvegarde ce que retourne la fonction dans le dictionnaire à l'indice .
Écrire la fonction récursive
fibo_rec_mem(n: int)
(plus d'autres paramètres si besoin) qui implémente l'approche top-down et renvoie le terme de Fibonacci de rang .
>>> memo = {0: 0, 1: 1}
>>> fibo_rec_mem(10)
55
On peut tester l'avantage de la programmation dynamique sur des grandes valeurs comme ou même .
L'algorithme bottom-up consiste à calculer les termes de la suite de Fibonacci itérativement, c'est-à-dire en commençant par , puis , etc. avant de chercher à résoudre les derniers termes. Pour cet algorithme on n'a pas besoin d'appel récursif, une boucle for
suffit à remplir le dictionnaire de mémoïsation en additionant les 2 précédents termes stockés.
Écrire la fonction
fibo_it_mem(n: int)
(plus d'autres paramètres si besoin) qui implémente l'approche bottom-up et renvoie le terme de Fibonacci de rang .
>>> memo = {0: 0, 1: 1}
>>> fibo_it_mem(10)
55
On peut utiliser la propriété de la suite de Fibonacci qui n'impose que de connaître les 2 valeurs précédant pour calculer le terme de rang . Il n'est donc pas nécessaire de conserver toutes les valeurs que prend dans un tableau, mais on peut se contenter de 2 variables représentants et .
Écrire la fonction
fibo_it(n: int)
(plus d'autres paramètres si besoin) qui implémente l'approche bottom-up sans utiliser de tableau/dictionnaire pour la mémoïsation.
>>> fibo_it(10)
55
Une suite comme celle de Fibonacci est indexée par les entiers naturels en commençant par 0, exactement comme une liste python. On peut se servir de cette propriété pour faire de la mémoïsation en utilisant les termes de la suite de Fibonacci comme indices d'une liste:
# n: 0 1 2 3
memo = [0, 1, 1, ...]
Écrire une fonction
fibo_helper(n: int)
qui initialise et retourne une liste de taille contenant des valeurs par défaut (None
,-1
,0
ouFalse
).
>>> fibo_helper(10)
[0, 1, None, None, None, None, None, None, None, None, None]
a. Proposer une version modifiée de
fibo_it_mem(n: int)
(question 6) qui utilise la liste générée parfibo_helper
pour la mémoïsation.
b. Idem pourfibo_rec_mem(n: int)
(question 5).
>>> memo = fibo_helper(10)
>>> fibo_it_mem(10)
55
a. Proposer une version
fibo_it_mem(n: int, memo: list)
qui prend en paramètre la liste de mémoïsation générée.
b. Idem pourfibo_rec_mem(n: int, memo: list)
.
>>> memo = fibo_helper(10)
>>> fibo_it_mem(10, memo)
55
En python, on peut déclarer une fonction interne à une autre qui sera utilisable dans la fonction principale, mais pas depuis l'extérieur:
def fonction_principale(n):
# Déclaration de la fonction interne
def fonction_interne(n):
if n > 3:
return [1]*n
else:
return [0, 0, 0]
# Traitement de la fonction principale
tab = fonction_interne(n)
...
a. Proposer une version
fibo_it_mem(n: int)
qui utilise une fonction interne pour générer une liste de mémoïsation.
b. Idem pourfibo_rec_mem(n: int, memo: list)
. Attention à ne pas recréer la liste de mémoïsation à chaque appel récursif!
>>> fibo_it_mem(10)
55