Programmation dynamique

Sommaire du document

Mémoïsation

Lorsque nous implémentons un algorithme récursif, nous pouvons constater dans un grand nombre de cas qu'une même opération est souvent effectuée avec les mêmes valeurs en paramètre. A chaque fois ce calcul a un coût en temps processeur et en mémoire. Ce n'est pas conséquent lorsque nous traitons des données peu importantes, mais ce coût se révèle souvent être de type exponentiel, et nous nous retrouvons avec des programmes dont les performances ne sont plus acceptables (ou des programmes qui ne peuvent carrément plus s'exécuter) dès que la quantité de données à traiter devient plus importante.

Nous pouvons éviter de calculer inutilement une opération dont le calcul a déjà été effectué, en mémorisant le résultat lors du premier appel. A chaque appel, nous testons si le résultat est présent, mais ce test est généralement nettement mois coûteux que l'opération à calculer. Nous devrons donc modifier l'appel récursif pour invoquer une méthode "memo" comme le montre l'exemple ci-dessous.


Code Pascal (Fibonacci simple) (9 lignes) :
  1. function fibonacci(var n : integer) : integer;
  2. {Pre: n>=0}
  3. begin
  4. if n < 2
  5. then
  6. fibonacci := n;
  7. else
  8. fibonacci := fibonacci(n-1) + fibonacci(n-2);
  9. end;

Dans cette implémentation, nous pouvons remarquer deux appels récursifs[1], ce qui donne un ordre de grandeur de temps T(n) ≤ Ordre de grandeur(2n)


Code Pascal (Fibonacci avec mémoïsation) (35 lignes) :
  1. program fibonacci-memo;
  2.  
  3. cons undef = -1; {valeur qui n'est jamais employee et qui signifie une valeur non definie}
  4. cons maxIndice = 20;
  5.  
  6. var memoArray : packed array[0..maxIndice] of integer;
  7.  
  8. function fibonacci(var n : integer) : integer;
  9. {Pre: 0 <= n <= maxIndice}
  10. begin
  11. if n < 2
  12. then
  13. fibonacci := n;
  14. else
  15. fibonacci := fibonacciMemo(n-1) + fibonacciMemo(n-2);
  16. end;
  17.  
  18. function fibonacciMemo(var n : integer) : integer;
  19. {Pre: 0 <= n <= maxIndice}
  20. begin
  21. if memoArray[n] = undef
  22. then
  23. memoArray[n] := fibonacci(n);{il est necessaire de calculer la valeur}
  24. fibonacciMemo := memoArray[n];{la valeur est deja calculee}
  25. end;
  26.  
  27. {main program}
  28. begin
  29. var i : integer;
  30. var j : integer;
  31. j:=20;
  32. for i:=0 to maxIndice do
  33. memoArray[i]:=undef;
  34. writeln('Fibonacci(', j, ') = ', fibonacci(j));
  35. end.

Dans cette deuxième implémentation, nous pouvons remarquer que le point de départ est toujours notre fonction fibonacci(n), mais que chaque appel au calcul(anciennement un appel récursif) est remplacé par un appel à la nouvelle fonction de mémoïsation. La complexité en temps de ce deuxième exemple est de Ordre de grandeur(n) * Ordre de grandeur(Trecherche et/ou écriture; dans le tableau), donc de Ordre de grandeur(n) ou au maximum identique à l'exemple précédent.

La fonction de mémoïsation vérifie si le calcul a déjà été effectué(si c'est le cas une valeur est présente à l'indice n dans le tableau) et retourne cette valeur si c'est le cas, ou effectue le calcul et stocke la valeur dans le tableau avant de la renvoyer comme résultat.

mémoïsation, mémoization, ou programmation dynamique descendante ?

La mémoïsation est aussi appelée programmation dynamique descendante, car nous vérifions la présence de la valeur avant de faire l'appel récursif. Nous retrouvons aussi souvent ce type d'algorithme sous le nom de mémoization.

 

Récursivité ascendante

Comme pour la mémoïsation, la récursivité ascendante nous permet de construire une table des résultats intermédiaires, mais ici de manière à traiter le problème le plus simple en premier. Si nous calculons les résultats intermédiaires lors de la "remontée"[2] dans l'arbre, la probabilité que la valeur se trouve déjà dans le tableau des résultats est beaucoup plus importante.

La complexité de ce type d'algorithme est généralement de Ordre de grandeur(n)

La structure de notre programme est modifiée, car nous utiliserons une boucle au lieu d'appels récursifs. Nous économisons donc la pile induite par notre alorithme récursif (gain mémoire), et nous nous assurons un remplissage optimal des résultats.

Problème de la récursivité ascendante

Le bien fondé de l'approche dynamique est indiscutable lorsque tout résultat repose sur d'autres résultats antérieurs, mais ce n'est pas toujours le cas. Si ce n'est pas le cas, nous ne devrions mémoriser que les sous-résultats nécessaires, sinon nous risquons d'effectuer une série de calculs inutiles. Nous pouvons tenter de déterminer quels sont les sous-résultats nécessaires par un graphe : lorsque plusieurs flèches pointent vers la même valeur nous sommes en présence d'un "re-calcul".

Optimisation de la récursivité ascendante

Nous pouvons parfois réduire la place mémoire nécessaire, comme le montre le schéma aminé suivant qui ne mémorise que les 2 derniers résultats de sous-problèmes.

Fibonacci avec méoïsation

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

7 mots clés dont 0 définis manuellement (plus d'information...).

Avertissement

Cette page ne possède pas encore de mots clés manuels, ceci est donc un exemple automatique (les niveaux de pertinence sont fictifs, mais les liens sont valables). Pour tester le nuage avec une page qui contient des mots définis manuellement, vous pouvez cliquer ici.

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Notes

  1.  Double récursion : fibonacci(n-1) + fibonacci(n-2)

  2.  Monter/descendre dans un arbre : Lorsque nous parcourons la hauteur d'un arbre de sa racine vers une feuille, nous "descendons", et nous "montons" lorsque nous parcourons les nœuds depuis une feuille vers la racine.

 

Références

  1. livre Langue du document: fr IHDCB331 - Méthodes de Programmation : PY Schobbens, Cours de Méthodes de Programmation (Septembre 2009)
  2. Consulter le document html Langue du document: fr Programmation dynamique : Wikipedia (version 16/10/09)
  3. Consulter le document html Langue du document: uk 20bits : Jesse Farmer, Introduction to Dynamic Programming (version 18/10/09)
  4. Consulter le document html Langue du document: uk Memoization & Java : Tom White, Memoization in Java Using Dynamic Proxy Classes (version 16/10/09)
  5. Consulter le document html Langue du document: uk Memoization & C++ : Paul McNamee, Automated Memoization in C++ (version 16/10/09)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

 

Liste des images

  1. Fibonacci avec méoïsation (Référence : infobrol)

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-11346
Document créé le 19/10/09 21:14, dernière modification le Vendredi 17 Juin 2011, 12:12
Source du document imprimé : http:///www.gaudry.be/programmer-dynamique.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,13 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Le génie, c'est l'erreur dans le système.

Paul Klee
 
l'infobrol
Nous sommes le Mardi 23 Mai 2017, 22:27, toutes les heures sont au format GMT+1.00 Heure, heure d'été (+1)