Fiche de révision : Programmation dynamique

Limites de la version récursivité simple

• La suite de Fibonacci est à la fois un exemple classique de programmation récursive et une bonne illustration des limites de la récursivité.
• La définition mathématique de la suite de Fibonacci se transpose très littéralement en algorithme récursif.
• Le calcul et l’affichage des nombres sont quasiment instantanés.
• Toutefois on constate que même pour des nombres relativement petits, le temps de calcul augmente très rapidement.
• On peut le constater avec le calcul des nombres de Fibonacci à partir de $n = 30$.
• Au total, calculer les 50 premiers nombres de la suite nécessite environ trois heures de calcul avec un ordinateur moderne.
• Les temps de calcul des valeurs de la suite forment une courbe exponentielle.
• En effet, un nombre de Fibonacci étant la somme des deux nombres qui le précèdent, son calcul fait référence à deux nombres qui doivent eux-mêmes être calculés ou retournés.
• Si on matérialise un arbre des appels, on remarque qu’un même calcul est demandé à plusieurs reprises. Par exemple :
• fibonacci(4) est appelé deux fois ;
• fibonacci(3) est appelé trois fois ;
• fibonacci(2) est appelé cinq fois.
• La programmation dynamique peut nous permettre d’optimiser les appels de fonction réitérés pour une même valeur.

Principes généraux de la programmation dynamique

• La programmation dynamique est une approche de résolution de problèmes qui consiste à décomposer un problème complexe en sous-problèmes plus simples et à faire en sorte de ne résoudre qu’une seule fois chaque sous-problème quand celui-ci se répète.
• En programmation dynamique, chaque résultat obtenu est conservé pour pouvoir être réutilisé.
• Elle repose sur deux caractéristiques complémentaires du problème à résoudre :
• la notion de sous-structure optimale ;
• le chevauchement des sous-problèmes.
• Un problème présente une sous-structure optimale si une solution optimale peut être obtenue à partir des solutions optimales de ses sous-problèmes.
• Un problème présente des sous-problèmes récurrents s’il peut être divisé en sous-problèmes et que cette décomposition en sous-problèmes entraîne des chevauchements.
• Notez que ce qui différencie la programmation dynamique de « diviser pour régner » c’est qu’ici les sous-problèmes ne sont pas indépendants, ils se chevauchent.
• La mise en œuvre des principes de programmation dynamique peut s’effectuer de deux manières :
• approche de haut en bas (conservation des résultats des calculs après leur exécution) ;
• Dans l’approche de haut en bas, on ne s’intéresse pas à l’ordre dans lequel les calculs ont lieu, on évite seulement de les répéter inutilement.
• approche de bas en haut (on part des sous-problèmes simples et on évolue de manière ascendante pour résoudre le problème global en stockant les résultats intermédiaires).
• Dans les deux cas on utilise de l’espace mémoire pour nous permettre de réduire les temps de calculs et donc de gagner du temps.

Application à la suite de Fibonacci

• Nous souhaitons faire évoluer notre algorithme récursif initial pour disposer d’une structure de données nous permettant de stocker les calculs à mesure qu’ils sont effectués.
• Ainsi, lors d’un appel pour un calcul, on commencera par vérifier si la valeur a déjà été calculée :
• si c’est le cas, on pourra la retourner directement à partir de la structure de données, sans avoir à lancer de nouveaux calculs ;
• si la valeur n’a pas encore été calculée, les appels correspondants seront lancés comme dans notre implémentation initiale, et on ajoutera le résultat obtenu à notre structure de données afin de pouvoir l’exploiter les fois suivantes.

memo = {}

def fibonacci(n):

• Si on lance le calcul pour $n = 6$, le dictionnaire de données contiendra # affiche {1: 1, 0: 0, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}
• Ainsi le calcul pour $n = 50$ qui nécessitait plus d’une heure dans notre implémentation récursive simple est désormais quasiment instantané.
• Toutefois si on augmente les valeurs de $n$, on finit par atteindre une limite liée au nombre d’appels récursifs : il s’agit de la limite permise par défaut par l’interpréteur Python.
• Nous avons donc réalisé une implémentation manuelle de la mémoïsation (fonctionnalité est disponible dans la bibliothèque standard de Python, avec le cache LRU de la bibliothèque functools).

• On effectue les mêmes calculs que dans l’approche de haut en bas, mais en prenant en compte l’ordre dans lequel ils sont effectués.
• Les valeurs supérieures sont calculées en séquence à partir des valeurs initiales préalablement définies ou calculées.

conteneur = {}
def fibomontant(n):

print(fibomontant(50))
# affiche (instantanément) la valeur 12586269025

• Cet algorithme n’est plus récursif mais itératif.
• Son fonctionnement séquentiel nous permet de le simplifier davantage en se passant totalement du conteneur de données puisqu’il suffit de connaître les deux valeurs précédentes pour pouvoir calculer les suivantes.

def fibiteratif(n):