Alice pose le problème suivant à Basile.
Elle dessine sur une feuille de papier une petite grille 2 x 3
![](\"https://sciencesappliquees.com/images/nsi/dyna1.png\")
et demande à Basile combien de chemins mènent du coin supérieur gauche (D) au coin inférieur droit (A), en se déplaçant uniquement le long de traits horizontaux vers la droite et le long de traits verticaux vers le bas.
![](\"https://sciencesappliquees.com/images/nsi/dyna2.png\")
Basile entame une énumération exhaustive mais perd rapidement le compte des chemins qu'il a ou non déjà construits.
Basile à alors l'idée de noter, à côté de chaque intersection, le nombre total de chemins qui mènent au coin inférieur droit.
![](\"https://sciencesappliquees.com/images/nsi/dyna3.png\")
Il commence naturellement par la fin et procède vers le haut et vers la gauche.
Ainsi, Basile n'a pas besoin de recompter à chaque fois le nombre de chemins pour les intersections qu'il à déjà traitées et il ne se perd plus dans ses caiculs.
Il parvient rapidement à ses fins avec la grille ainsi complétée qu'il montre fièrement à Alice en lui indiquant que la réponse est 10.
![](\"https://sciencesappliquees.com/images/nsi/dyna4.png\")
Alice remarque alors que chaque nombre est la somme du nombre situé à droite et du nombre situé en-dessous, ce que Basile confirme en expliquant qu'un chemin partira soit vers la droite, soit vers le bas.
Tout excités, Alice et Basile mettent à profit cette idée pour calculer en quelques instants qu'il y a 184756 chemins sur une grille 10 x 10.
Alice et Basile viennent d'inventer la programmation dynamique.
D'une manière générale, la programmation dynamique est une technique consistant à faire en sorte de ne pas calculer plusicurs fois la même chose, en stockant des résultats intermédiaires dans une structure de données.
Dans l'exemple ci-dessus, un tableau à deux dimensions permettrait de stocker les nombres de chemins déjà calculés.
Dans cette séquence, on illustre la programmation dynamique sur deux exemples
- le rendu de monnaie
- et l'alignement de séquences.
D'autres exemples sont proposés en exercices, dont le calcul des chemins donné en exemple ci-dessus.
Considérons le problème du rendu de monnaie, déjà abordé dans le programme de première.
On suppose un système monétaire utilisant des pièces, avec un certain nombre de pièces de différentes sortes, chacune ayant une valeur entière différente.
Par exemple, on peut imaginer un système avec trois sortes de pièces, avec les valeurs 1, 2 et 5. ![\"Pièces](\"https://123montessori.fr/1268-large_default/monnaie-pieces-et-billets-en-euro.jpg\")
Source:https://123montessori.fr/monnaie-pieces-et-billets-en-euro-259
On se pose alors la question, pour un système donné, du nombre minimal de pièces qui est nécessaire pour réaliser une somme donnée.
Ainsi, il faut au minimum 3 pièces pour réaliser la somme 12 avec le système ci-dessus.
Mais il n'en faudrait que 2 dans un système qui proposerait des pièces de valeurs 1, 6 et 10.
Dans le programme de première, on a vu qu'un algorithme glouton, qui favorise toujours la pièce la plus grande possible, répond au problème du rendu de monnaie sous certaines conditions.
C'est le cas notamment pour un système monétaire comme les euros, c'est-à-dire
(1,2,5,10,20,50,100,200).
Dans le cas général, cependant, l'algorithme glouton ne donne pas toujours la réponse optimale.
Ainsi, pour faire la somme 12 avec le système (1,6, 10), l'algorithme glouton donne la réponse 3, correspondant à 10 + 1 + 1, au lieu de 2 (6 + 6).
Dans cette section, on étudie un autre algorithme de rendu de monnaie qui donne toujours la solution optimale quelque soit le système monétaire utilisé.
On cherche à écrire sous la forme d'une fonction :
rendu_monnaie(pieces, s)
où pieces est la liste des valeurs des pièces, telle que [1, 2, 5] par exemple, et s la somme que l'on souhaite obtenir.
La fonction doit renvoyer le nombre minimal de pièces pour obtenir s.
On suppose que la liste pieces contient toujours la valeur 1. Ainsi, toute somme peut être obtenue, dans le pire des cas, comme 1+1+ ... +1.
L'algorithme que nous proposons n'est pas vraiment subtil:
il va considérer toutes les façons possibles de parvenir à la somme s.
Pour cela, il procède récursivement. Le cas de base est la somme s = 0, pour laquelle il ne faut aucune pièce.
On renvoie donc 0.
Lorsque s > 0, on considère chaque valeur p dans la liste pieces et on calcule récursivement le nombre minimal de pièces pour faire la somme s—p.
À chacune des valeurs obtenues on ajoute 1 (la pièce de valeur p) et on prend le minimum de toutes ces réponses.
Le programme ci-dessous contient le code Python d'une fonction récursive rendu_monnaie qui réalise cet algorithme.
Programme — Rendu de monnaie, naïf
def rendu_monnaie(pieces, s):
\"\"\"renvoie le nombre minimal de pièces pour faire
la somme s avec le système pieces\"\"\"
if s == 0:
return 0
r = s # s = 1 + 1 + ... + 1 dans le pire des cas
for p in pieces:
if p <= s:
r = min(r, 1 + rendu_monnaie(pieces, s - p))
return r
On prendra le temps de bien lire et de bien comprendre ce programine.
Le programme fonctionne correctement mais il est assez peu performant.
Mettre le résultat ici (code et figure).
On constate que le programme ne termine tout simplement pas pour la somme 100.
Essayons de comprendre ce qui se passe, en comptant le nombre d'appels à la fonction rendu_monnaie.
Lorsqu'on l'appelle avec 100 comme argument, elle se rappelle deux fois récursivement, une fois avec 99 comme argument et une fois avec 98 comme argument.
Puis l'appel sur 99 va provoquer deux appels récursifs, sur 98 et 97 respectivement.
On constate qu'on va donc faire deux fois un appel avec 98 comme argument, ce qui provoquerait au total trois appels avec 97 comme argument. Et ainsi de suite d'une façon rapidement dramatique.
Essayons d'être plus précis encore, en calculant pour chaque valeur de s le nombre exact d'appels à la fonction rendu_monnaie.
Pour s = 0, il n'y a qu'un seul appel, à savoir l'appel initial.
Pour s = 1, à y en a deux, à savoir l'appel initial et l'appel sur s = 0.
Dans le cas général, il faut compter l'appel initial et les nombres d'appel pour s — 1 ct s — 2, c'est-à-dire les deux nombres obtenus précédemment.
Pour les premières valeurs de s, en partant de 0, on obtient la suite suivante :
1,2,4,7,12,20,33,...
Si on ajoute un à ces valeurs, on reconnaît la célèbre suite de Fibonacci:
2,3,5,8,13,21,34,...
Dit autrement, le nombre d'appels à rendu_monnaie dans le calcul de
rendu_monnaie([1, 2], n)
est égal à Fn+3 — 1 où Fn désigne le n-ième terme de la suite de Fibonacei.
Or, c'est là une suite qui croît exponentiellement rapidement.
Ainsi, F50 = 12 586 269 025, ce qui veut dire que le calcul de rendu_monnaie([1, 2], 47) demanderait plus de 12 milliards d'appels.
Il n'est pas étonnant que le calcul de rendu_monnaie([1, 2], 100) ne semblait pas terminer, quand on sait que F103 dépasse 1500 milliards de milliards.
Bien évidemment, dans le cas précis du système [1,2] la réponse est tellement simple qu'on peut la calculer de tête.
Mais cet exemple minimal montre à quel point notre solution récursive est rapidement trop coûteuse.
Mieux encore, il nous a permis d'identifier la source du problème :
on appelle la fonction rendu_monnaie de très nombreuses fois sur le même argument.
Ainsi, pendant le calcul de rendu_monnaie([1,2], 35), qui prend plus de 8 secondes, on appelle 1346 273 fois la fonction rendu_monnaie avec s = 5.
C'est là qu'intervient l'idée de la programmation dynamique :
faire en sorte de ne pas calculer plusieurs fois la même chose.
La mise en œuvre de cette idée n'est pas si difficile que cela. On va utiliser un tableau dans lequel on va stocker successivement la réponse de la fonction rendu monnaie pour toutes les valeurs de 0 jusqu'à s.
Ainsi, on ne recalculera jamais deux fois la même réponse pour une certaine somme:
on se contentera de lire sa valeur dans ce tableau.
Notre nouvelle fonction rendu_monnaie commence donc par allouer un tableau, appelé nb pour «nombre de pièces», dont les indices vont de 0 à s inclus.
def rendu_monnaie(pieces, s):
nb = [0] * (s+1)
Ce tableau est ici initialisé avec 0, ce qui est notamment la bonne valeur pour la somme 0.
Ainsi, la première case du tableau est correctement initialisée.
Il s'agit maintenant de remplir ce tableau pour toutes les sommes de 1 à s.
On le fait avec une boucle for. Pour chaque indice n, c'est-à-dire pour chaque
On le fait avec une boucle for. Pour chaque indice n, c'est-à-dire pour chaque somme n, on commence par initialiser nb[n] avec n car on sait que, dans le pire des cas, on peut faire la somme n avec n pièces, à savoir :
n = 1+1+ ... + 1.
for n in range(i, s + 1):
nb[n] = n
Il faut maintenant se poser la question de savoir si on peut faire mieux.
Comme dans le programme récursif rendu_monnaie, on considère successivement toutes les valeurs de la liste pieces.
Pour chaque valeur p, on a une solution
en 1 + nb[n - p] pièces, à savoir une pièce de valeur p et la meilleure solution possible pour la somme n - p, déjà calculée.
for p in pieces:
if p<=n:
nb[n] = min(nb[n], 1 + nb[n - p])
Avec cette boucle, on calcule donc le minimum de toutes les solutions possibles, ce qui donne bien la solution pour la somme n.
Une fois sorti de ces deux boucles, on à calculé la solution pour toutes les sommes jusqu'à s inclus.
Il n'y à donc plus qu'à renvoyer la valeur de nb[s].
return nb[s]
Le programme ci-dessous contient l'intégralité du code.
Programme — Rendu de monnaie par programmation dynamique
def rendu_monnaie1(pieces, s):
\"\"\"renvoie le nombre minimal de pièces pour faire
la somme s avec le système pieces\"\"\"
nb = [0] * (s + 1)
for n in range(1, s + 1):
nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas
for p in pieces:
if p <= n:
nb[n] = min(nb[n], 1 + nb[n - p])
return nb[s]
On constate qu'il a la même structure que le programme précédent, si ce n'est que l'appel récursif est maintenant remplacé par la consultation du tableau nb.
Tester la fonction rendu_monaie1 avec les instructions suivantes :
r = rendu_monnaie1([1, 2], 10)
print(r)
et ensuite avec:
r = rendu_monnaie1([1, 2], 47)
print(r)
et enfin avec:
r = rendu_monnaie1([1, 2], 100)
print(r)
Conclure
Mettre le résultat ici (code et figure).
Efficacité
Notre version de rendu monnaie qui utilise la programmation dynamique est bien plus efficace que la version récursive initiale.
Ainsi, le calcul de rendu _monnaie([1,2], 47), qui demandait beaucoup de temps, est maintenant instantané.
En effet, on a maintenant l'allocation d'un tableau de taille 48, une boucle qui parcourt 47 valeurs possibles pour la variable n et, pour chacune, une boucle interne qui parcourt deux valeurs possibles pour la variable p.
Le nombre total d'opérations est donc de l'ordre de la centaine, ce qui est ridicule.
D'une manière générale, le coût est maintenant proportionnel à
len(pieces) x s
en temps et à s en espace (pour le tableau nb).
C'est potentiellement plus coûteux que l'algorithme glouton, mais cela fonctionne maintenant pour tous les systèmes monétaires.
Construire une solution
Notre programme renvoie le nombre minimal de pièces pour obtenir la somme s mais il ne donne pas la solution pour autant, c'est-à-dire la liste des pièces à utiliser pour atteindre ce minimum.
Il est cependant facile de le modifier pour construire une telle solution.
Il suffit d'ajouter ur second tableau qui contient, pour chaque somme entre 0 et s, une solution minimale pour cette somme.
On remplit ce tableau exactement au même moment où on remplit le tableau nb.
Le programme ci-dessous contient une version du programme rendu_monnaie modifié en suivant cette idée.
Programme — Rendu de monnaie, avec solution
def rendu_monnaie_solution(pieces, s):
\"\"\"renvoie une liste minimale de pièces pour faire
la somme s avec le système pieces\"\"\"
nb = [0] * (s + 1)
sol = [[]] * (s + 1)
for n in range(1, s + 1):
nb[n] = n
sol[n] = [1] * n
for p in pieces:
if p <= n and 1 + nb[n - p] < nb[n]:
nb[n] = 1 + nb[n - p]
sol[n] = sol[n - p].copy()
sol[n].append(p)
return sol[s]
Le second tableau s'appelle sol. Pour chaque indice n, l'élément sol[n] est un tableau d'entiers, de taille nb[n], qui donne une solution pour la somme n.
On initialise sol avec un tableau vide dans chaque case, ce qui est en particulier correct pour n = 0.
La structure du programme est la même qu'auparavant.
Pour chaque somme n, de 1 jusqu'à s, on commence par stocker un tableau contenant n fois la valeur 1 dans sol[n], ce qui correspond à la solution 1+1+...+1.
Puis on examine toutes les pièces possibles et, lorsqu'une pièce p permet d'améliorer la solution, la valeur des deux tableaux est mise à jour.
Pour mettre à jour la valeur de sol[n], on commence par faire une copie du tableau sol[n - op], avec la méthode copy, puis on y ajoute la valeur p, avec la méthode append.
Tester la fonction rendu_monaie_solution avec les instructions suivantes :
r = rendu_monnaie_solution([1, 2], 10)
print(r)
et ensuite avec:
r = rendu_monnaie([1, 2], 47)
print(r)
Conclure
Pour une somme donnée, il n'y à pas nécessairement une solution unique.
Ainsi, avec le système [1, 3, 6, 7, 10], il y a deux solutions minimales pour faire la somme 13, à savoir 3 + 10 ct 6 + 7.
Tester avec:
r = rendu_monnaie_solution([1, 3, 6, 7, 10], 13)
print(r)
Notre programme va renvoyer une seule de ces solutions.
En l'occurrence, ici, il va renvoyer le
tableau [10, 3] correspondant à la première solution.
En effet, lorsque le programme parvient à n = 13, il considère les pièces par ordre croissant.
Pour p = 1, il détermine qu'on obtient une solution à trois pièces en considérant la solution déjà calculée 12 = 6 + 6 à deux pièces.
Puis, pour p = 3, il détermine qu'on obtient de nouveau une meilleure solution, à deux pièces cette fois, en considérant la solution déjà calculée pour la somme 10, à une seule pièce, ce qui nous fait une solution à deux pièces 3 + 10.
Quand on considère ensuite p - 6, on obtient de nouveau une solution à deux pièces, qui n'est donc pas strictement meilleure et qui n'est donc pas considérée.
De même quand on considère p = 7 et p = 10. On est donc resté sur la solution 13=3+10, qui est celle renvoyée au final.
On pourrait encore modifier le programme ci-dessous pour qu'il renvoie toutes les solutions pour faire la somme s en minimisant le nombre de pièces.
Il suffirait pour cela que le tableau sol stocke, pour chaque somme, non pas une solution minimale mais toutes les solutions minimales.
Mais il faut être alors conscient que le temps et l'espace consacrés au stockage de toutes les solutions vont dégrader les performances de notre programme.
Mettre le résultat ici (code et figure).
Dans le contexte de la bio-informatique, un problème algorithmique essentiel est celui de l'alignement de séquences, typiquement pour comparer des séquences d'ADN.
![](\"https://upload.wikimedia.org/wikipedia/commons/thumb/3/3d/Radioactive_Fluorescent_Seq.jpg/220px-Radioactive_Fluorescent_Seq.jpg\")
Source: https://en.wikipedia.org/wiki/DNA_sequencing
On peut le formaliser en ces termes:
étant données deux chaînes de caractères, il s'agit de mettre en correspondance «le plus possible» les caractères de la première chaîne avec ceux de la seconde, en conservant l'ordre des caractères mais en s'autorisant à insérer des trous dans l'une ou l'autre chaîne.
Si on considère par exemple les chaînes \"GENOME\" et \"ENORME\", on peut aligner leurs caractères de la façon suivante, où le caractère - est utilisé pour désigner un trou:
GENO-ME
ENORME
Bien entendu, il existe de nombreuses autres façons d'aligner ces deux chaînes.
En voici une:
G--ENOME
—ENOR--ME
La seule contrainte est que l'on doit utiliser tous les caractères de chaque chaîne, dans l'ordre, et que l'on n'aligne jamais deux trous (c'est-à-dire deux caractères - ).
Parmi tous les alignements possibles, on cherche celui qui donne le score maximal.
Le score est ainsi calculé:
l'alignement de deux caractères identiques donne un point;
en revanche, l'alignement de deux
caractères différents, ce qui inclut l'alignement avec le caractère -, enlève un point.
Ainsi, le premier alignement proposé ci-dessus donne le score 3, car on a 5 caractères correctement alignés et deux mauvais alignements.
Parmi tous les alignements possibles des chaînes \"GENOME\" et \"ENORME\", c'est celui
qui a le score maximal.
À noter que les deux chaînes n'ont pas forcément la même longueur.
Ainsi, l'alignement
ASTUCIEUX
-STUDIEUX
a le score 5, ce qui est là encore maximal.
Comme pour le problème du rendu de monnaie de la section précédente, nous allons commencer par chercher une solution récursive à notre problème (mais cette fois sans écrire le code Python), puis en améliorer l'efficacité grâce à la programmation dynamique.
Reprenons l'exemple des mots \"GENOME\" et \"ENORME\" et voyons ce qu'il en est de leur dernier caractère.
Ici, il s'agit du caractère E dans les deux cas.
Il y à trois cas de figure :
- soit ces deux E sont alignés, on marque un point et on doit aligner les mots “GENOM\" et \"ENORM\";
- soit le E final de \"GENOME\" est aligné avec -, on perd un point et on doit aligner le mot \"GENOM\" avec le mot \"ENORME\";
- soit enfin le E final de \"ENORME\" est aligné avec -, on perd un point et on doit aligner le mot \"GENOME\" avec le mot \"ENORM\",
Comme il n'y a pas d'autre cas possible, le score maximal sera le maximum des trois scores ainsi obtenus. Et comme on s'est ramené à des mots plus petits, plus précisément à une longueur totale des deux mots strictement plus petite, on peut procéder récursivement.
Ainsi, dans le premier cas on calcule le score maximal de l'alignement de \"GENOM\" et \"ENORM\", dans le deuxième cas de \"GENOM\" et \"ENORME\", et dans le troisième cas de \"GENOME\" ct \"ENORM\",
À chaque fois, il y à de nouveau trois cas de figure, qui nous ramènent à des mots plus courts. Et ainsi de suite.
Le processus termine lorsque l'un des deux mots n'a plus de caractères.
Quand par exemple on parvient au calcul du score de l'alignement du mot vide \"\" et du mot \"GE\", la réponse est —2 car il n'y à pas d'autre choix que d'aligner les deux caractères de \"GE\" avec des caractères -.
On pourrait ainsi écrire une fonction récursive aligne qui applique l'algorithme ci-dessus.
Mais exactement comme pour le rendu de monnaie, elle serait très inefficace car elle passerait son temps à recalculer ia même chose.
En effet, si l'on examine les trois cas ci-dessus, on voit que dans le deuxième
cas, le calcul de l'alignement de \"GENOM\" et \"ENORME\" va nous ramener en particulier au calcul de l'alignement de \"GENOM\" et \"ENORM\", déjà fait dans le
premier cas. Et de même, dans le troisième cas, le calcul de l'alignement de \"GENOME\" et \"ENDRM\" va nous ramener une troisième fois au calcui de l'alignement de \"GENOM\" et \"ENORM\".
Ce phénomène de duplication des calculs
va se répéter à chaque étape, provoquant une explosion exponentielle des appels récursifs et donc du temps de calcul.
Ainsi, le calcul du meilleur alignement de deux mots de 10 caractères chacun prend plus de 3 secondes et celui de deux mots de 20 caractères chacun ne se termine pas en un temps raisonnable.
Mais comme pour le rendu de monnaie, on
peut améliorer notre programme en évitant les calculs redondants grâce à la programmation dynamique.
Mettre le résultat ici (code et figure).
Dans le cas du rendu de monnaie, on à utilisé un tableau dans lequel on a stocké, pour chaque somme, la solution optimale.
Ici, on va utiliser un tableau à deux dimensions dans lequel on va stocker, pour chaque paire de mots, le score maximal.
Plus précisément, pour deux entiers i et j, on va stocker dans la case (i,j) de ce tableau le score maximal de l'alignement
des à premiers caractères du premier mot et des j premiers caractères du second mot.
Notre fonction aligne commence par calculer la longueur de chacun des deux mots et par allouer un tableau sc de la bonne taille.
def aligne(s1, s2):
\"\"\"le score du meilleur alignement de s1 et s2\"\"\"
n1, n2 = len(s1), len(s2)
sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
Il y a plusieurs remarques importantes ici. D'une part, le premier indice va
de 0 à n1 inclus et le second de 0 à n2 inclus. C'est pourquoi on à écrit n1+1
(resp. n2+1). Le tableau à donc la taille (n1 +1) x (n2 + 1).
D'autre part, on a utilisé la construction par compréhension pour construire ce tableau à deux dimensions.
Écrire simplement [[0] * (n2+1)] * (n1+1) aurait été incorrect.
Enfin, on à initialisé les cases de ce tableau avec la valeur 0. En particulier, c'est la bonne valeur pour la case (0,0) c'est-à-dire l'alignement de deux mots vides.
Il faut maintenant remplir toutes les autres cases de ce tableau, en mettant dans sc[i][j] le score de l'alignement maximal des mots s1[0:i] et s2[0:j].
On va le faire en progressant dans le sens des indices croissants.
En effet. le calcul de sc[i][j] va utiliser les trois valeurs :
sc[i-1][j],sc[i][j-1] et sc[i-1][j-1].
Il faut donc les avoir calculées auparavant.
En particulier, on peut commencer par initialiser les valeurs sc[0][j], c'est-
à-dire la première ligne, et sc[i][0], c'est-à-dire la première colonne.
Dans les deux cas, il s'agit de l'alignement avec un mot vide, pour lequel la réponse est facile à calculer:
il faut supprimer tous les caractères, ce qui produit un score égal à l'opposé de la longueur du mot considéré.
for i in range(1, n1 + 1):
sc[i][0] = -i
for j in range(1, n2 + 1):
sc[0][j] = -j
On peut maintenant attaquer le remplissage du reste du tableau, avec une
double boucle pour parcourir toutes les cases restantes.
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
Pour chaque case sc[i][j], il s'agit de calculer le score maximal pour aligner les mots s1[0:i] et s2[0:j].
Comme expliqué plus haut, il y a trois cas de figure, selon l'alignement du dernier caractère de chacun de ces deux mots.
On commente par les deux cas où l'un de ces deux caractères est aligné avec -. Le score est alors obtenu avec un point de pénalité et l'alignement maximal, déjà calculé, pour un mot raccourci d'un caractère, c'est-à-dire soit sc[i-1][j], soit sc[i][j-1].
s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])
1] reste alors le cas où les deux derniers caractères sont alignés.
Dans ce cas, on marque un point si les caractères coïncident et on perd un point sinon.
Dans les deux cas, on utilise l'alignement maximal déjà calculé pour les deux mots raccourcis chacun d'un caractère, c'est-à-dire sc[i-1][j-1].
if s1[i - 1] == s2[j - 1]:
sc[i][j] = max(s, 1 + sc[i - 1][j - 1])
else:
sc[i][j] = max(s, -1 + sc[i - 1][j - 1])
Une fois sorti de la double boucle, le tableau est correctement rempli. Il ne reste plus qu'à renvoyer la valeur située dans la toute dernière case, qui correspond au score d'alignement des deux mots complets.
return sc[n1][n2]
Le programme ci-dessous contient l'intégralité du code:
Programme — Alignement de séquences
def aligne(s1, s2):
\"\"\"le score du meilleur alignement de s1 et s2\"\"\"
n1, n2 = len(s1), len(s2)
sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
# première ligne et première colonne
for i in range(1, n1 + 1):
sc[i][0] = -i
for j in range(1, n2 + 1):
sc[0][j] = -j
# le reste
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])
if s1[i - 1] == s2[j - 1]:
sc[i][j] = max(s, 1 + sc[i - 1][j - 1])
else:
sc[i][j] = max(s, -1 + sc[i - 1][j - 1])
return sc[n1][n2]
Tester la fonction aligne avec:
s2 = \"ENORME\"
s1 = \"GENOME\"
sc = aligne(s1,s2)
Mettre le résultat ici (code et figure).
Il est utile de visualiser et de bien comprendre le tableau sc que ce programme construit. Si on reprend l'exemple des mots \"GENOME\" et \"ENORME\", le tableau obtenu au final est celui-ci:
![](\"https://sciencesappliquees.com/images/nsi/dyna5.png\")
On peut examiner par exemple comment a été calculé le résultat final, c'est-
à-dire sc[6][6]. Puisque les caractères s1[5] et s2[5] coïncident, on a :
sc[6][6] = max(1+sc[5][5],—1+sc[5][6], —1 + sc[6][5])
= max(1+2,-1+1,-1+1)
= 3
Si on prend un autre cas de figure où les caractères ne coïncident pas, comme par exemple le cas de sc[4][5], on a:
sc[4][5] = max(1+sc[3][4],—1+sc[3][5], —1 + sc[4][4])
= max(-1+-1,-1+-2,-1+1)
= 0
Une autre façon de lire ce tableau est la suivante:
quand on monte, c'est qu'on aligne le caractère correspondant à la ligne avec -;
quand on va à gauche, c'est qu'on aligne le caractère correspondant à la colonne avec -;
enfin, quand on va en diagonale vers le haut et la gauche, c'est qu'on aligne
les deux caractères correspondant à la ligne et à la colonne.
En particulier, le score maximal obtenu au final correspond à un certain chemin de la case en bas à droite jusqu'à la case en haut à gauche qui, à chaque étape, choisit entre aller vers le haut, aller vers la gauche ou aller en diagonale vers le haut et la gauche.
Comme pour le rendu de monnaie, il est possible de modifier le programme pour qu'il renvoie la solution, c'est-à-dire l'alignement réalisant le score maximal. Vous aurez à le faire dans un des exercices.
Mettre le résultat ici (code et figure).
Efficacité
L'efficacité de ce programme est facile à évaluer. Si les deux mots s1 at s2 ont une longueur respective N et M, on a alloué un tableau de taille N x M.
On l'a ensuite rempli avec quelques calculs élémentaires pour chaque case, ce qui prend un temps proportionnel à N x M.
En particulier, le calcul de l'alignement de deux mots de 20 caractères chacun, qui n'aurait jamais terminé en un temps raisonnable avec une simple fonction récursive, termine maintenant instantanément, avec quelques centaines d'opérations élémentaires seulement.
Mettre le résultat ici (code et figure).
Mémoïsation
La programmation dynamique n'est pas la seule façon d'éviter les calculs redondants.
Une autre technique consiste à utiliser
un dictionnaire, dans lequel on stocke les calculs déjà effectués.
Plus précisément, pour effectuer le calcul de f(a), on commence par regarder
dans le dictionnaire, indexé par a, si la valeur de f(a) est déjà connue.
Le cas échéant, on la renvoie. Sinon, on calcule la valeur v de f(a), on remplit le dictionnaire avec a -> v, puis on renvoie v.
Ainsi, si on cherche plus tard à recalculer f pour la même valeur a, alors le calcul sera immédiat.
Voici par exemple le programme rendu_monnaie réécrit avec cette idée.
def rendu_monnaie2(pieces, s):
if s in memo:
return memo[s]
r=s
for p in pieces:
if p <= s:
r = min(r, 1 + rendu_monnaie(pieces, s - p))
memo[s] = r
return r
Tester le code avec:
from time import time
start = time()
r = rendu_monnaie2([1, 3, 6, 7, 10], 30)
print(\"appel fct 1ère fois\",time()-start,\"s\")
print(r)
start = time()
r = rendu_monnaie2([1, 3, 6, 7, 10], 30)
print(\"appel fct 2ème fois avec memo\",time()-start,\"s\")
print(r)
Conclure sur l'avantage de la mémoïsation.
IL a toujours la structure récursive du programme rendu_monnaie mais il est maintenant aussi efficace que le programme rendu_monnaie1 (modulo les limites de la récursion de Python).
La programmation dynamique et la mémoïsation sont deux techniques différentes pour atteindre le même objectif, à savoir améliorer la complexité en évitant de calculer deux fois la même chose.
Dans l'immense majorité des cas, elles sont interchangeables.
Il existe cependant quelques cas de figure où la programmation dynamique permet un contrôle plus fin de la mémoire utilisée (en «oubliant» des valeurs précédemment calculées dont on sait qu'elles ne seront plus utiles).
À l'inverse, la mémoïsation est bien plus simple à mettre en œuvre. Mais tout ceci dépasse le cadre du programme de terminale.
Mettre le résultat ici (code et figure).
Lien avec la technique «diviser pour régner»
La programmation dynamique présentée dans cette séquence n'est pas sans rapport avec la technique «diviser pour régner» présentée dans la séquence précédente.
En effet, il n'est pas rare de commencer par concevoir une décomposition récursive d'un problème, comme dans la séquence précédente, pour se rendre compte ensuite que certains appels récursifs vont être effectués plusieurs fois avec les mêmes arguments.
On peut alors employer la programmation dynamique ou la mémoïsation pour y
remédier.
Mettre le résultat ici (code et figure).
La programmation dynamique est une technique pour améliorer l'efficacité d'un algorithme en évitant les calculs redondants.
Pour cela, on stocke dans un tableau les résultats intermédiaires du calcul, afin de les réutiliser au lieu de les recalculer.
Les problèmes du rendu de monnaie ou de l'alignement de séquences sont deux exemples où la programmation dynamique améliore grandement l'efficacité par rapport à une solution récursive.
Mettre le résultat ici (code et figure).
Expliciter (à la main) tous les appels récursifs à la fonction rendu_monnaie (version naïve) quand on lance rendu_monnaie([1, 2], 3).
Identifier les calculs redondants.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
Il y a sept appels au total (en comptant le tout premier):
rendu_monnaie([1,2], 3)
rendu_monnaie([1,2], 2)
rendu_monnaie([1,2], 1)
rendu_monnaie([1,2], 0)
rendu_monnaie([1,2], 0)
rendu_monnaie([1,2], 1)
rendu_monnaie([1,2], 0)
On constate qu’on a fait deux fois l’appel pour s = 1 et trois fois l’appel
pour s = 0.
Quel est le tableau construit par le programme rendu_monnaie2 quand on
calcule rendu_monnaie2([1, 6, 10], 12)? (Le calculer à la main.)
Mettre le résultat ici (code et figure).
[0, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 2]
La réponse est dans la dernière case (donc 2 ici).
def rendu_monnaie1(pieces, s):
\"\"\"renvoie le nombre minimal de pièces pour faire
la somme s avec le système pieces\"\"\"
nb = [0] * (s + 1)
for n in range(1, s + 1):
nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas
for p in pieces:
if p <= n:
nb[n] = min(nb[n], 1 + nb[n - p])
return nb[s]
Modifier le programme rendu_monnaie1 pour qu'il renvoie, plutôt que le nombre minimal de pièces nécessaires, la liste des pièces constituant la solution optimale.
Tester avec:
print(rendu_monnaie3([1,2,5],47))
Résultat:
[2, 5, 5, 5, 5, 5, 5, 5, 5, 5]
Mettre le résultat ici (code et figure).
À côté du tableau nb qui contient le nombre minimal
de pièces nécessaires pour chaque entier, on ajoute un second tableau, sol,
qui contient la solution, sous la forme d’une liste de pièces.
def rendu_monnaie3(pieces, s):
\"\"\"renvoie le nombre minimal de pièces pour faire
la somme s avec le système pieces\"\"\"
nb = [0] * (s + 1)
sol = [[]] * (s + 1)
for n in range(1, s + 1):
nb[n] = n # n = 1 + 1 + ... + 1 dans le pire des cas
sol[n] = [1] * n
for p in pieces:
if p <= n:
nb[n] = min(nb[n], 1 + nb[n - p])
sol[n] = sol[n - p].copy()
sol[n].append(p)
return sol[s]
La suite de Fibonacci est la suite d'entiers (Fn) définie par
F0 = 0,
F1 = 1
et pour n>1, on a Fn = Fn-1 + Fn-2
Écrire une fonction fibonacci(n) qui calcule la valeur de Fn en utilisant la programmation dynamique.
Tester avec:
print(fib(1200))
Résultat:
373026809482509284562310031170172380127627214493597616743856443016039972205847405917634660750474914561879656763268658528092195715626073248224067794253809132219056382939163918400
Mettre le résultat ici (code et figure).
On se sert d’un tableau f dans lequel on calcule successivement toutes les valeurs F0, F1,...,Fn.
def fib(n):
f = [0] * (n+1)
f[1] = 1
for i in range(2, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]
Calculer à la main le tableau des scores d'alignement pour les deux mots \"CHAT\" et \"CAT\".
Mettre le résultat ici (code et figure).
C A T
0 -1 -2 -3
C -1 1 0 -1
H -2 0 0 -1
A -3 -1 1 0
T -4 -2 0 2
Le score maximal est donc 2.
Quel est le score maximal de l'alignement des mots \"AAAAAAAAAA\" et \"BBBBBBBBBB\" (10 caractères chacun)?
Quelle est la forme du tableau calculé par le programme aligne(s1,s2) sur ces deux mots?
Mettre le résultat ici (code et figure).
Le score maximal est -10.
Le tableau a la forme suivante:
B B B B B B B B B B
0 -1 -2 -3 -4 -5 -6 -7 -8 -9-10
A -1 -1 -2 -3 -4 -5 -6 -7 -8 -9-10
A -2 -2 -2 -3 -4 -5 -6 -7 -8 -9-10
A -3 -3 -3 -3 -4 -5 -6 -7 -8 -9-10
A -4 -4 -4 -4 -4 -5 -6 -7 -8 -9-10
A -5 -5 -5 -5 -5 -5 -6 -7 -8 -9-10
A -6 -6 -6 -6 -6 -6 -6 -7 -8 -9-10
A -7 -7 -7 -7 -7 -7 -7 -7 -8 -9-10
A -8 -8 -8 -8 -8 -8 -8 -8 -8 -9-10
A -9 -9 -9 -9 -9 -9 -9 -9 -9 -9-10
A-10-10-10-10-10-10-10-10-10-10-10
Écrire une fonction affiche(s1, s2, sc) qui affiche la table des scores calculée par le programme aligne(s1, s2), sous la forme suivante:
E N O R M E
0 -1 -2 -3 -4 -5 -6
G -1 -1 -2 -3 -4 -5 -6
E -2 0 -1 -2 -3 -4 -4
N -3 -1 1 0 -1 -2 -3
O -4 -2 0 2 1 0 -1
M -5 -3 -1 1 1 2 1
E -6 -4 -2 0 0 1 3
Pour obtenir un tel alignement, on pourra utiliser la commande:
print('{:>3}'.format(n), end=\"\")
qui affiche la valeur n sur exactement trois caractères, qu'il s'agisse d'un entier ou d'un caractère.
Tester avec:
def aligne(s1, s2):
\"\"\"le score du meilleur alignement de s1 et s2\"\"\"
n1, n2 = len(s1), len(s2)
sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
# première ligne et première colonne
for i in range(1, n1 + 1):
sc[i][0] = -i
for j in range(1, n2 + 1):
sc[0][j] = -j
# le reste
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
s = max(-1 + sc[i - 1][j], -1 + sc[i][j - 1])
if s1[i - 1] == s2[j - 1]:
sc[i][j] = max(s, 1 + sc[i - 1][j - 1])
else:
sc[i][j] = max(s, -1 + sc[i - 1][j - 1])
#return sc[n1][n2]
return sc
et
s2 = \"ENORME\"
s1 = \"GENOME\"
sc = aligne(s1,s2)
affiche(s1,s2,sc)
Mettre le résultat ici (code et figure).
def affiche(s1, s2, sc):
print (\" \", end=\"\")
for c in s2:
print ('{:>3}'.format(c), end=\"\")
print()
for i in range(len(sc)):
if i > 0:
print ('{:>3}'.format(s1[i - 1]), end=\"\")
else:
print(\" \", end=\"\")
for v in sc[i]:
print ('{:>3}'.format(v), end=\"\")
print()
Modifier le programme aligne(s1,s2) pour qu'il renvoie également la solution donnant le meilleur score, sous la forme d'un couple de chaînes de caractères de même longueur contenant d'éventuels caractères -.
Ainsi, sur les deux chaînées \"GENOME\" et \"ENORME\", le programme doit renvoyer:
(3, (\"GEND-ME\", \"-ENORME\"))
On pourra s'inspirer de ce qui à été fait
dans le programme rendue_monnaie_solution.
Tester avec:
s2 = \"ENORME\"
s1 = \"GENOME\"
print(aligne2(s1,s2))
Résultat:
(3, ('GENO-ME', '-ENORME'))
Mettre le résultat ici (code et figure).
Comme dans le programme rendu_monnaie_solution, on ajoute un second tableau, sol, à côté du tableau sc, l’idée étant que so1[i][j] contient une solution pour l'alignement des chaînes s1[0:i] et s2[0:j].
L’initialisation se fait avec des couples de chaînes vides:
sol = [[(\"\", \"\")] * (n2 + 1) for _ in range(n1 + 1)]
Pour initialiser les bords du tableau, on écrit respectivement
sol[i][0] = (s1[0:i], \"-\" * i)
et
sol[0][j] = (\"-\" * j, s2[0:j])
ce qui correspond à des alignements avec le caractère -. Enfin, il y a quatre
cas de figure pour déterminer so1[i] [j], selon la situation qui maximise le
score. On peut réécrire la double boucle ainsi:
# le reste
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
s = -1 + sc[i - 1][j]
x,y = sol[i - 1][j]
sol[i][j] = (x + s1[i - 1], y + \"-\")
if s < -1 + sc[i][j - 1]:
s = -1 + sc[i][j - 1]
x,y = sol[i][j - 1]
sol[i][j] = (x + \"-\", y + s2[j-1])
if s1[i-1] == s2[j-1] and s < 1 + sc[i-1][j-1]:
s = 1 + sc[i - 1][j - 1]
x,y = sol[i - 1][j - 1]
sol[i][j] = (x + s1[i - 1], y + s2[j - 1])
if s1[i-1] != s2[j-1] and s < -1 + sc[i-1][j-1]:
s = -1 + sc[i - 1][j - 1]
x,y = sol[i - 1][j - 1]
sol[i][j] = (x + s1[i - 1], y + s2[j - 1])
sc[i][j] = s
On constate qu’on ne se sert plus de la fonction max. En effet, le calcul de sol[i][j] est différent à chaaue fois.
Le programme complet est le suivant:
def aligne2(s1, s2):
\"\"\"le score du meilleur alignement de s1 et s2\"\"\"
n1, n2 = len(s1), len(s2)
sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
sol = [[(\"\", \"\")] * (n2 + 1) for _ in range(n1 + 1)]
# première ligne et première colonne
for i in range(1, n1 + 1):
sc[i][0] = -i
sol[i][0] = (s1[0:i], \"-\" * i)
for j in range(1, n2 + 1):
sc[0][j] = -j
sol[0][j] = (\"-\" * j, s2[0:j])
# le reste
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
s = -1 + sc[i - 1][j]
x,y = sol[i - 1][j]
sol[i][j] = (x + s1[i - 1], y + \"-\")
if s < -1 + sc[i][j - 1]:
s = -1 + sc[i][j - 1]
x,y = sol[i][j - 1]
sol[i][j] = (x + \"-\", y + s2[j-1])
if s1[i-1] == s2[j-1] and s < 1 + sc[i-1][j-1]:
s = 1 + sc[i - 1][j - 1]
x,y = sol[i - 1][j - 1]
sol[i][j] = (x + s1[i - 1], y + s2[j - 1])
if s1[i-1] != s2[j-1] and s < -1 + sc[i-1][j-1]:
s = -1 + sc[i - 1][j - 1]
x,y = sol[i - 1][j - 1]
sol[i][j] = (x + s1[i - 1], y + s2[j - 1])
sc[i][j] = s
return (s , sol[n1][n2])
Dans le problème de l'alignement de séquences d'ADN, on utilise en pratique un calcul des scores plus subtil, qui dépend des caractères qui sont alignés (pour tenir compte du nombre d'acides aminés identiques ou similaires qui sont mis en correspondance).
Pour cela, on se donne une matrice de similarités.
Par exemple, pour des chaînes formées uniquement des caractères A, G, C et T, on peut se donner la matrice suivante:
![](\"https://sciencesappliquees.com/images/nsi/dyna6.png\")
Indiquer comment représenter une telle matrice en Python (dans une variable globale sim).
Par ailleurs, on se donne aussi une variable globale gap pour le score d'un alignement avec le caractère - (par exemple gap = -5).
Modifier le programme aligne(s1,s2) pour qu'il utilise ces deux variables dans le calcul du score.
Tester avec:
sim = {
'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},
'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},
'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },
'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }
}
gap = 5
s1 = \"AGCT\"
s2 = \"AGCT\"
print(aligne3(s1,s2))
Résultat:
40
Mettre le résultat ici (code et figure).
On peut se donner la matrice de similarités sous la forme d’un dictionnaire de dictionnaires:
sim = {
'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},
'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},
'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },
'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }
}
Le calcul du score est alors modifié ainsi. Pour les bords, on utilise respec-
tivement
sc[i][0] = i * gap
et
sc[0][j] = j * gap
Et dans la double boucle, on utilise maintenant :
s = max(gap + sc[i - 1][j], gap + sc[i][j - 1])
sc[i][j] = max(s, sim[s1[i - 1]][s2[j - 1]]
+ sc[i - 1][j - 1])
Le programme complet est le suivant:
global sim,gap
sim = {
'A':{'A':10, 'G':-1, 'C':-3, 'T':-4},
'G':{'A':-1, 'G':7 , 'C':-5, 'T':-3},
'C':{'A':-3, 'G':-6, 'C':9 , 'T':0 },
'T':{'A':-4, 'G':-3, 'C':0 , 'T':8 }
}
gap = 5
def aligne3(s1, s2):
\"\"\"le score du meilleur alignement de s1 et s2\"\"\"
global sim,gap
n1, n2 = len(s1), len(s2)
sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
# première ligne et première colonne
for i in range(1, n1 + 1):
sc[i][0] = i * gap
for j in range(1, n2 + 1):
sc[0][j] = j * gap
# le reste
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
s = max(gap + sc[i - 1][j], gap + sc[i][j - 1])
sc[i][j] = max(s, sim[s1[i - 1]][s2[j - 1]]
+ sc[i - 1][j - 1])
return sc[n1][n2]
#return sc
Écrire une fonction chemins(n, m) qui calcule le nombre de chemins, sur une grille n x m, qui mènent du coin supérieur gauche au coin inférieur droit, en se déplaçant uniquement le long des traits horizontaux vers la droite et le long des traits verticaux vers le bas.
Vérifier les valeurs trouvées par Alice et Basile en introduction à cette séquence.
Tester avec:
print(chemins1(2,3))
Résultat:
10
Mettre le résultat ici (code et figure).
On crée un tableau de taille
(n+1) x (m+1),
comme pour le problème de l’alignement de séquences.
def chemins(n, m):
grille = [[1] * (m +1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
grille[i][j] = grille[i - 1][j] + grille[i][j - 1]
#print(grille[i][j])
return grille#[n][m]
ou avec for décroissant:
def chemins1(n, m):
grille = [[1] * (m +1) for _ in range(n + 1)]
for i in range(n-1, -1, -1):
for j in range(m-1,-1,-1):
grille[i][j] = grille[i + 1][j] + grille[i][j + 1]
#print(grille[i][j])
return grille#[n][m]
#return grille[0][]