La programmation dynamique: suite de Fibonacci

Introduction à la programmation dynamique

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:

s'applique aux problèmes décomposables en sous-problèmes similaires mais plus petits
ne concerne que les problèmes dont un traitement récursif fait apparaitre les mêmes sous-problèmes plusieurs fois
consiste à mémoriser les résolutions de sous-problèmes pour économiser des calculs

La suite de Fibonacci: version naïve

On définit la suite de Fibonacci $𝐹_𝑛 (𝑛∈𝑵)$ par

𝐹_𝑛 = \begin{cases} 0 & \text{si } n = 0 \\ 1 & \text{si } n = 1\\ 𝐹_{𝑛−1} + 𝐹_{𝑛−2} & \text{pour tout entier } 𝑛 ≥ 2 \end{cases}

Calculer $𝐹_5$ à la main.
Écrire la fonction récursive fibo_rec(n: int) qui implémente la suite de Fibonacci et renvoie le terme de rang $n$ .

On peut tester la bonne implémentation de la suite de Fibonacci sur quelques-unes de ces valeurs:

$F_{10}$	$F_{11}$	$F_{12}$	$F_{13}$	$F_{14}$	$F_{15}$	$F_{16}$	$F_{17}$	$F_{18}$	$F_{19}$	$F_{20}$
55	89	144	233	377	610	987	1597	2584	4181	6765

Écrire à la main l’arbre des appels à fibo_rec lorsqu'on exécute fibo_rec(5).

Mémoïsation

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.

Approche récursive "Top-down": On calcule d’abord $F_n$ pour les "grandes" valeurs de $n$

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é $n$ à la valeur de $F_n$ 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 $n$ , on vérifie si $F_n$ 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 $n$ .

É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 $n$ .

>>> memo = {0: 0, 1: 1}
>>> fibo_rec_mem(10)
55

On peut tester l'avantage de la programmation dynamique sur des grandes valeurs comme $F_{100}$ ou même $F_{500}$ .

Approche itérative "Bottom-up": On calcule d’abord $F_n$ pour les "petites" valeurs de $n$ :

L'algorithme bottom-up consiste à calculer les termes de la suite de Fibonacci itérativement, c'est-à-dire en commençant par $n=2$ , puis $n=3$ , 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 $n$ .

>>> 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 $F_n$ pour calculer le terme de rang $n$ . Il n'est donc pas nécessaire de conserver toutes les valeurs que prend $F_n$ dans un tableau, mais on peut se contenter de 2 variables représentants $F_{n-1}$ et $F_{n-2}$ .

É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

Pour aller plus loin: la mémoïsation sous toutes ses formes

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 $n+1$ contenant des valeurs par défaut (None, -1, 0 ou False).

>>> 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 par fibo_helper pour la mémoïsation.
b. Idem pour fibo_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 pour fibo_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 pour fibo_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