CHAPITRE III Programmation Dynamique III.1 Exemple introductif : la suite de Fi

CHAPITRE III Programmation Dynamique III.1 Exemple introductif : la suite de Fibonacci La suite de Fibonacci est la suite d’entier (un)n≥0 d´ efinie r´ ecursivement par :      u0 = 0 u1 = 1 un = un−1 + un−2 ∀n ≥2 On peut traduire directement cette d´ efinition en un algorithme r´ ecursif : Algorithm 1 Fibonacci 1: procedure Fibonacci(n) 2: if n ≤1 then 3: return n 4: else 5: return Fibonacci(n −1) + Fibonacci(n −2) 6: end if 7: end procedure Pour analyser la complexit´ e de cet algorithme, on remarque que chaque appel ` a Fibonacci() se fait en temps constant (si on ne tient pas compte des appels r´ ecursifs lanc´ es). Il suffit donc de compter le nombre d’appels, pour n en entr´ ee, que l’on va noter An. La suite An v´ erifie :      a0 = 1 a1 = 1 an = 1 + an−1 + an−2 ∀n ≥2 Cette suite ressemble ` a la suite de Fibonacci. On peut l’´ etudier math´ ematiquement et on trouve que An ∈Θ(φn), o` u φ = 1+ √ 5 2 ≈1, 6 est le nombre d’or. La complexit´ e de l’algorithme est donc exponentielle. D’o` u vient une telle complexit´ e ? Si on d´ eveloppe le calcul de u6, on a : u6 = u5 + u4 = u4 + u3 + u3 + u2 = u3 + u2 + u2 + u1 + u2 + u1 + u1 + u0 = · · · 1 On remarque que les mˆ emes calculs sont effectu´ es un nombre important de fois. Pour am´ eliorer la performance de l’algorithme, on peut stocker les r´ esultats interm´ ediaires obtenus et les r´ eutiliser directement quand on en a besoin au lieu de les recalculer. C’est l’id´ ee de la programmation dynamique. Cela donne : Algorithm 2 Fibonacci 1: procedure Fibonacci(n,T[ ]) 2: if n ≤1 then 3: return n 4: end if 5: if T[n] n’est pas d´ efini then 6: T[n] = Fibonacci(n −1) + Fibonacci(n −2) 7: end if 8: return T[n] 9: end procedure La complexit´ e devient alors lin´ eaire : on ne remplit la case T[n] qu’une fois, donc le nombre d’appels ` a Fibonacci(i), pour chaque valeur i ≤n est d’au plus 3, une fois pour le calculer, une fois quand on calcule Fibonacci(i + 1) et une fois quand on calcule Fibonacci(i + 2). On peut d´ e-r´ ecursiver l’algorithme. Il s’agit de remplir le tableau T directement case par case. On s’aper¸ coit qu’il faut faire le contraire de ce que fait l’algorithme r´ ecursif : commencer par les petites valeurs. Algorithm 3 Fibonacci 1: procedure Fibonacci(n) 2: Allouer T avec n + 1 cases 3: T[0] = 0 4: T[1] = 1 5: for i de 2 ` a n −1 do 6: T[i] = T[i −1] + T[i −2] 7: end for 8: return T[n] 9: end procedure Il est imm´ ediat que l’algorithme est bien lin´ eaire. Il prend aussi une quantit´ e de m´ emoire lin´ eaire. La derni` ere ´ etape consiste ` a essayer de gagner en m´ emoire en ne m´ emorisant que le n´ ecessaire. Pour notre exemple, il suffit de se rappeler des deux derniers termes pour calculer le nouveau. On peut donc n’utiliser qu’un espace m´ emoire constant (Voir l’algo 4). III.2 Principe g´ en´ eral On part d’un probl` eme dont on peut trouver une solution optimale ` a partir des solutions optimales de sous-probl` emes du mˆ eme type. Quand ses sous-probl` emes se recouvrent, c’est-` a- dire que leurs r´ esolutions ont des calculs en commun, on stocke en m´ emoire les calculs d´ ej` a effectu´ es afin de ne pas avoir ` a les refaire dans le traitement d’un autre sous-probl` eme. Pour r´ esoudre un probl` eme en utilisant la programmation dynamique il faut : 2 Algorithm 4 Fibonacci 1: procedure Fibonacci(n) 2: Allouer T avec n + 1 cases 3: a = 0 4: b = 1 5: for i de 2 ` a n −1 do 6: c = b 7: b = a + b 8: a = b 9: end for 10: return b 11: end procedure 1. Trouver un d´ ecoupage en sous-probl` emes plus petits, de sorte que les sous-probl` emes se recouvrent. 2. M´ emoriser les calculs d´ ej` a effectu´ es pour ne pas lancer plusieurs fois le mˆ eme appel. 3. Essayer de d´ e-r´ ecursiver l’algorithme, pour obtenir un algorithme it´ eratif. Il faut en g´ en´ eral commencer par les plus petits objets pour reconstruire des objets de plus en plus grands. 4. Essayer de gagner de l’espace m´ emoire en “jetant” ce qui ne sert plus, ou plutˆ ot en r´ eutilisant l’espace m´ emoire qui ne sert plus. Dans le cadre du cours on vous demande surtout de faire 1. et 2., parfois 3. III.3 Exemple : le sac ` a dos avec r´ ep´ etitions On dispose de n types d’objets diff´ erents. Le i-` eme objet xi a un poids poids[i] et un prix prix[i]. L’endroit contient plein d’exemplaires de chaque type d’objet. On dispose ´ egalement d’un sac de capacit´ e C, le poids maximal qui peut ˆ etre dedans. Le probl` eme est d’optimiser la valeur totale du sac : on met autant d’exemplaire de chaque objet que l’on veut, tant qu’on ne d´ epasse pas la capacit´ e, et on veut que la somme des prix soit maximale. On consid` ere que toutes les valeurs sont des entiers. La solution s’obtient en faisant le d´ ecoupage suivant : tout objet xi de poids inf´ erieur ou ´ egale ` a C est plac´ e dans le sac, il reste donc ` a traiter le sous-probl` eme avec C−poids[i], ce qu’on fait r´ ecursivement, en ajoutant le prix de xi pour avoir la valeur optimale d’un sac contenant xi. Une fois qu’on a calcul´ e la valeur optimale d’un sac contenant x1, la valeur optimale d’un sac contenant x2, . . . on prend la plus grande de toute ces valeurs. Math´ ematiquement, cela donne, en notant Sac(C) la valeur optimale pour une capacit´ e C : Sac(C) = ( 0 si tous les poids sont sup´ erieurs ` aC, maxi|poids[i]≤C (Sac(C −poids[i]) + prix[i]) sinon. On peut traduire directement l’expression math´ ematique en algorithme r´ ecursif, et utiliser la m´ emorisation sur les valeurs de la capacit´ e pour faire de la programmation dynamique. La complexit´ e du r´ esultat est en O(Cn). Quand on d´ er´ ecursive on obtient l’algorithme ci-dessous. 3 Algorithm 5 Sac ` a dos 1: procedure Sac(C) 2: Allouer S avec C + 1 cases 3: S[0] = 0 4: for p de 1 ` a C do 5: m = 0 6: for i de 0 ` a n −1 do 7: if poids[i] ≤p then 8: if S[p −poids[i]] + prix[i] ≥m then 9: m = S[p −poids[i]] + prix[i] 10: end if 11: end if 12: end for 13: T[p] = m 14: end for 15: return T[C] 16: end procedure III.4 Exemple : Distance d’´ edition Nous d´ eveloppons ` a pr´ esent un exemple classique d’utilisation de la programmation dyna- mique : le calcul de la distance d’´ edition. Soient u et v deux mots sur un alphabet A. La distance d’´ edition entre u et v est le nombre minimum d’op´ erations ` a effectuer pour transformer u en v. Les op´ erations autoris´ ees sont : – Insertion : on ajoute une lettre de A dans u, o` u on veut. – Suppression : on enl` eve une lettre de u. – Substitution : on change une lettre de u en une autre lettre (´ eventuellement la mˆ eme, ce qui ne change alors pas le mot). Exemple : u = verites et v = eviter. On peut faire la suite minimale de transformations suivante : verites 7→erites 7→evites 7→eviter Comme il n’y a pas de transformation en moins d’´ etapes (c’est affirm´ e, non prouv´ e, mais on peut tester toutes les possibilit´ es), la distance d’´ edition entre u et v est 3. Aligments : on repr´ esente les op´ erations effectu´ ees pour passer d’un mot ` a l’autre par un alignement. Voil` a un alignement entre chien et niche : w =  c h i e n − − − n i − c h e  Si on regarde colonne par colonne un alignement, on voit qu’on a une suite de transformations qui permettent de passer du mot en haut au mot en bas. Une colonne de la forme α −
correspond ` a une suppression de α. Une colonne de la forme − β
correspond ` a une insertion de β. Une colonne de la forme α β
correspond ` a une substitution de uploads/Religion/ suite-de-fibonicci.pdf

Documents similaires

Corrige TD-String Exercice 1 public class TestString { public static int string 0 0

Le Nei Yang Gong Qigong pour nourrir l’intérieur Partie dynamique Première part 0 0

Monsieur Jean Lassus Une image de saint Syméon le Jeune sur un fragment de reli 0 0

OFPPT Direction Régionale Nord-Ouest I Examen de fin de module régional – Sessi 0 0

1 Août 2021 Mon enthousiasme s’est accru alors que j’approchais de la fin d’une 0 0

• Détails
• Publié le Dec 03, 2022
• Catégorie Religion
• Langue French
• Taille du fichier 0.1024MB