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:


La suite de Fibonacci: version naïve

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

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

  1. Calculer 𝐹5𝐹_5 à la main.

  2. Écrire la fonction récursive fibo_rec(n: int) qui implémente la suite de Fibonacci et renvoie le terme de rang nn.

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

F10F_{10} F11F_{11} F12F_{12} F13F_{13} F14F_{14} F15F_{15} F16F_{16} F17F_{17} F18F_{18} F19F_{19} F20F_{20}
55 89 144 233 377 610 987 1597 2584 4181 6765
  1. É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.

  1. 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 FnF_n pour les "grandes" valeurs de nn

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é nn à la valeur de FnF_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 nn, on vérifie si FnF_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 nn.

  1. É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 nn.

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

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

Approche itérative "Bottom-up": On calcule d’abord FnF_n pour les "petites" valeurs de nn:

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

  1. É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 nn.

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

  1. É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, ...]
  1. Écrire une fonction fibo_helper(n: int) qui initialise et retourne une liste de taille n+1n+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]
  1. 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
  1. 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) ...
  1. 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