Solu tions des exer cices du cha pitre 4
459
© Dunod – Toute reproduction non autorisée est un délit.
4.2 1) Chaque carac tère d’une séquence de lon gueur n peut être soit conservé soit sup primé
pour for mer une sous- séquence. Il y a donc 2
n
sous- séquences pos sibles.
Tester si deux séquences de lon gueur x sont iden tiques peut se faire avec un algo rithme
de com plexité, dans le pire des cas, O(x). Ainsi un algo rithme consis tant à énu mé rer les 2
n
sous- séquences de A et les 2
m
sous- séquences Β et à les com pa rer deux à deux serait de com -
plexité O(min(m,n) . 2
n + m
), prohibitive : ne pas énumérer dans le combinatoire !
2) Si z k , la der nière lettre de la plus longue sous- séquence com mune Z, n’était pas
a i = b j , on pour rait ajou ter z i après z k dans Z et on obtien drait une sous- séquence com mune Za i
plus longue que Z, ce qui est contra dic toire. Donc z k = a i = b j et z 1 c z k – 1 est une sousséquence com mune à A i – 1 et B j – 1 . Elle est de lon gueur maximale car s’il exis tait S une
sous- séquence com mune à A i – 1 et B j – 1 de lon gueur supé rieure, la séquence Sa i serait une
sous- séquence com mune à A i et B j de lon gueur supé rieure à Ζ qui est de lon gueur maximale :
contradiction.
3) z k , la der nière lettre de Z, ne peut pas être la der nière lettre de A i et de B j puisque a i 2 b j .
Alors Z est une plus longue sous- séquence com mune de A i – 1 et B j ou de A i et B j – 1 .
4) Si i = 0 ou j = 0 l’une des séquences A i ou B j est la séquence vide qui est de lon gueur 0 ;
il est donc évident que f (i, j) = 0.
Lorsque a i = b j , nous avons vu en 2) que z 1
c z k–1 est une plus longue sous- séquence
com mune de A i – 1 et B j – 1 . Comme f (i – 1, j – 1) est la lon gueur de z 1
c z k – 1 , il s’en suit
que z 1
c z k – 1 z k est la plus longue sous- séquence com mune à A i et B j ; elle est de lon gueur
f (i, j) = f (i – 1, j – 1) + 1.
Nous avons mon tré en 3) que lorsque a i 2 b j , la plus longue sous- séquence com mune de
A i et B j est une plus longue sous- séquence com mune de A i – 1 et B j de lon gueur f (i – 1, j), ou
de A i et B j – 1 de lon gueur f (i, j – 1). Il s’en suit donc que :
f (i, j ) = max (f (i – 1, j), f (i, j – 1)).
5) Si a i = b j , alors T(i, j ) = 1 + T(i – 1, j – 1).
Si a i 2 b j , alors T(i, j ) = max (T(i – 1, j ), T(i, j – 1)).
6) L’algo rithme sui vant, de com plexité O(mn), per met de cal cu ler les valeurs T(i, j ) :
Pour j ← 1 à n faire T(0, j ) ← 0
pour i ← 1 à m faire T(i, 0) ← 0
pour j ← 1 à n faire
si a i = b j alors T(i, j ) ← 1 + T(i – 1, j – 1)
sinon T(i, j ) ← max (T(i – 1, j ), T(i, j – 1))