Exercices
177
© Dunod – Toute reproduction non autorisée est un délit.
4. Sup po sons main te nant qu’à la phase k, pour la valeur d, x k 5 0 soit dans
une solu tion opti male.
Mon trer que dans ce cas z k 1 d 2 5 z k21 1 d 2 .
5. Déduire des ques tions pré cé dentes que pour k 5 2, c , n et
d 5 0, c , b on a :
z k 1 d 2 5 b
z k21 1 d 2
max 1 z k21 1 d2 , c k 1 z k21 1 d 2 a k 2 2
si a k . d,
si a k < d.
6. Consi dé rons l’exemple sui vant :
max 16x 1 1 19x 2 1 23x 3 1 28x 4 5 z
2x 1 1 3x 2 1 4x 3 1 5x 4 < 7
x 1 ,
x 2 ,
x 3 ,
x 4 H 50, 16
Appli quer l’algo rithme de pro gram ma tion dyna mique à cet exemple. On
pourra tracer le graphe des décisions pour illustrer le calcul de l’optimum.
***4.2 Déter mi na tion de la plus longue sous- séquence com mune
à deux séquences, par appli ca tion de la pro gram ma tion dyna mique
Soit deux séquences (ou mots) A 5 a 1 c a n et B 5 b 1 c b k . On dira que
B 5 b 1 c b k est une sous- séquence de A, s’il existe une suite d’indices i 1 , c , i k
stric te ment crois sante (mais non néces sai re ment consé cu tifs) extraite de 1, c , n
telle que, pour tout j 5 1, c , k, on ait : a ij 5 b j . Par exemple, la séquence
B 5 cnam est une sous- séquence de la séquence A 5 reconstituames.
Étant données deux séquences A et B, Ζ est une sous- séquence com mune de A et
B si et seule ment si Ζ est une sous- séquence de A et de B. Par exemple Ζ 5 mai est
une sous- séquence com mune de A 5 com bi na toire et B 5 opti mi sation.
Le pro blème que l’on veut résoudre est la déter mi na tion d’une sous- séquence
com mune à deux séquences don nées, qui soit de lon gueur maximale.
Ce pro blème admet de nom breuses appli ca tions, notam ment dans l’étude de
séquences d’ADN en bio lo gie.
1. Mon trer que le nombre de sous séquences d’une séquence de lon gueur
n est 2
n
(par conven tion la séquence vide, de lon gueur nulle, est une sousséquence de toute séquence). En déduire la com plexité d’un algo rithme qui
cal cu le rait toutes les sous séquences de A et de B et les com pa re rait deux à
deux pour déter mi ner une plus longue sous séquence com mune.
L’objet de cet exer cice est de conce voir un algo rithme de pro gram ma tion
dyna mique de com plexité moindre.
Soit une séquence A 5 a 1 c a n , on défi nit le ième pré fixe de A, pour
i 5 0, c , n, par A i 5 a 1 c a i . Par exemple, si A 5 modé li sa tion alors
A 4 5 mode.
177
© Dunod – Toute reproduction non autorisée est un délit.
4. Sup po sons main te nant qu’à la phase k, pour la valeur d, x k 5 0 soit dans
une solu tion opti male.
Mon trer que dans ce cas z k 1 d 2 5 z k21 1 d 2 .
5. Déduire des ques tions pré cé dentes que pour k 5 2, c , n et
d 5 0, c , b on a :
z k 1 d 2 5 b
z k21 1 d 2
max 1 z k21 1 d2 , c k 1 z k21 1 d 2 a k 2 2
si a k . d,
si a k < d.
6. Consi dé rons l’exemple sui vant :
max 16x 1 1 19x 2 1 23x 3 1 28x 4 5 z
2x 1 1 3x 2 1 4x 3 1 5x 4 < 7
x 1 ,
x 2 ,
x 3 ,
x 4 H 50, 16
Appli quer l’algo rithme de pro gram ma tion dyna mique à cet exemple. On
pourra tracer le graphe des décisions pour illustrer le calcul de l’optimum.
***4.2 Déter mi na tion de la plus longue sous- séquence com mune
à deux séquences, par appli ca tion de la pro gram ma tion dyna mique
Soit deux séquences (ou mots) A 5 a 1 c a n et B 5 b 1 c b k . On dira que
B 5 b 1 c b k est une sous- séquence de A, s’il existe une suite d’indices i 1 , c , i k
stric te ment crois sante (mais non néces sai re ment consé cu tifs) extraite de 1, c , n
telle que, pour tout j 5 1, c , k, on ait : a ij 5 b j . Par exemple, la séquence
B 5 cnam est une sous- séquence de la séquence A 5 reconstituames.
Étant données deux séquences A et B, Ζ est une sous- séquence com mune de A et
B si et seule ment si Ζ est une sous- séquence de A et de B. Par exemple Ζ 5 mai est
une sous- séquence com mune de A 5 com bi na toire et B 5 opti mi sation.
Le pro blème que l’on veut résoudre est la déter mi na tion d’une sous- séquence
com mune à deux séquences don nées, qui soit de lon gueur maximale.
Ce pro blème admet de nom breuses appli ca tions, notam ment dans l’étude de
séquences d’ADN en bio lo gie.
1. Mon trer que le nombre de sous séquences d’une séquence de lon gueur
n est 2
n
(par conven tion la séquence vide, de lon gueur nulle, est une sousséquence de toute séquence). En déduire la com plexité d’un algo rithme qui
cal cu le rait toutes les sous séquences de A et de B et les com pa re rait deux à
deux pour déter mi ner une plus longue sous séquence com mune.
L’objet de cet exer cice est de conce voir un algo rithme de pro gram ma tion
dyna mique de com plexité moindre.
Soit une séquence A 5 a 1 c a n , on défi nit le ième pré fixe de A, pour
i 5 0, c , n, par A i 5 a 1 c a i . Par exemple, si A 5 modé li sa tion alors
A 4 5 mode.