TD d’algorithmique avancée
Corrigé du TD 5 : plus longue sous-séquence commune
Jean-Michel Dischler et Frédéric Vivien
Problématique
Une séquence est une suite finie de symboles pris dans un ensemble fini. Si u = (cid:104)a1, a2, ..., an(cid:105) est une
séquence, où a1, a2, ..., an sont des lettres, l’entier n est la longueur de u. Une séquence v = (cid:104)b1, b2, ..., bm(cid:105)
est une sous-séquence de u = (cid:104)a1, a2, ..., an(cid:105) s’il existe des entiers i1, i2, ..., im (1 ≤ i1 < i2 < ... <
im ≤ n) tels que bk = aik pour k ∈ [1, m]. Par exemple, v = (cid:104)B, C, D, B(cid:105) est une sous-séquence de
u = (cid:104)A, B, C, B, D, A, B(cid:105) correspondant à la suite d’indice (cid:104)2, 3, 5, 7(cid:105).
Une séquence w est une sous-séquence commune aux séquences u et v si w est une sous-séquence de u et
de v. Une sous-séquence commune est maximale ou est une plus longue sous-séquence si elle est de longueur
maximale. Par exemple : les séquences (cid:104)B, C, B, A(cid:105) et (cid:104)B, D, A, B(cid:105) sont des plus longues sous-séquences
communes de (cid:104)A, B, C, B, D, A, B(cid:105) et de (cid:104)B, D, C, A, B, A(cid:105).
Résolution par programmation dynamique
1. On cherche a déterminer la longueur d’une sous-séquence commune maximale a u = (cid:104)a1, a2, ..., an(cid:105) et
v = (cid:104)b1, b2, ..., bm(cid:105). On note L(i, j) la longueur d’une sous-séquence commune maximale à (cid:104)a1, a2, ..., ai(cid:105)
et (cid:104)b1, b2, ..., bj(cid:105) (0 ≤ j ≤ m, 0 ≤ i ≤ n). Donnez une récurrence définissant L(i, j). Indication : on
pourra distinguer les cas ai = bj et ai (cid:54)= bj.
L(i, j) =
0
1 + L(i − 1, j − 1)
max(L(i, j − 1), L(i − 1, j))
si i = 0 ou j = 0,
sinon et si ai = bj,
sinon.
Publicité
(1)
En effet, si ai (cid:54)= bj, une plus longue sous-séquence commune de (cid:104)a1, a2, ..., ai(cid:105) et (cid:104)b1, b2, ..., bj(cid:105) ne peut
pas se terminer par une lettre c égale a ai et a bj, et donc une plus longue sous-séquence commune
– soit ne se termine pas par ai et elle est alors une plus longue sous-séquence commune des séquences
(cid:104)a1, a2, ..., ai−1(cid:105) et (cid:104)b1, b2, ..., bj(cid:105), et est de longueur L(i − 1, j) ;
– soit ne se termine pas par bj et elle est alors une plus longue sous-séquence commune des séquences
(cid:104)a1, a2, ..., ai(cid:105) et (cid:104)b1, b2, ..., bj−1(cid:105), et est de longueur L(i, j − 1).
Si, par contre, ai = bj, alors une plus longue sous-séquence commune de (cid:104)a1, a2, ..., ai(cid:105) et (cid:104)b1, b2, ..., bj(cid:105)
se termine par ai = bj (sinon on peut la rallonger par ai) et son préfixe (la sous-séquence moins son
dernier élément) est une plus longue sous-séquence commune de (cid:104)a1, a2, ..., ai−1(cid:105) et (cid:104)b1, b2, ..., bj−1(cid:105).
2. Écrivez alors un algorithme récursif calculant la longueur de la plus longue sous-séquence commune de
deux séquences.
PLSSC-Récursif(A, i, B, j)
si i = 0 ou j = 0
alors renvoyer 0
sinon si A[i] = B[j]
alors renvoyer 1+ PLSSC-Récursif(A, i − 1, B, j − 1)
sinon renvoyer max(PLSSC-Récursif(A, i − 1, B, j), PLSSC-Récursif(A, i, B, j − 1))
3. Montrez que cet algorithme est de complexité au moins exponentielle dans le cas où les deux séquences
n’ont pas d’éléments en commun.
1
Dans ce cas, on se trouve toujours dans le troisième cas de l’équation 1 et la complexité est définie par
la récurrence :
T (n, m) = (cid:26)
0
Publicité
T (n, m − 1) + T (n − 1, m)
si n = 0 ou m = 0,
sinon.
D’où T (n, m) = T (n, m − 1) + T (n − 1, m)
= (T (n, m − 2) + T (n − 1, m − 1)) + (T (n − 1, m − 1) + T (n − 2, m − 1))
≥ 2T (n − 1, m − 1).
Donc T (n, m) = Ω(2min(m,n)).
4. Écrivez alors un algorithme suivant le paradigme de la programmation dynamique et calculant la
longueur de la plus longue sous-séquence commune de deux séquences.
PLSSC-ProgDyn(A, B)
n ← longueur (A)
m ← longueur (B)
pour i ← 1 à n faire l[i, 0] ← 0
pour j ← 1 à m faire l[0, j] ← 0
pour i ← 1 à n faire
pour j ← 1 à m faire
si A[i] = B[j]
alors l[i, j] ← 1 + l[i − 1, j − 1]
sinon l[i, j] ← max(l[i − 1, j], l[i, j − 1])
renvoyer l[n, m]
5. Quelle est la complexité de cet algorithme ?
La complexité est due aux deux boucles imbriquées : T (n, m) = O(nm).
6. Modifiez l’algorithme précédent pour que l’on puisse en plus construire une plus longue sous-séquence
commune et affichez une telle sous-séquence.
PLSSC-ProgDyn(A, B)
n ← longueur (A)
Publicité
m ← longueur (B)
pour i ← 1 à n faire l[i, 0] ← 0
pour j ← 1 à m faire l[0, j] ← 0
pour i ← 1 à n faire
pour j ← 1 à m faire
si A[i] = B[j]
alors l[i, j] ← 1 + l[i − 1, j − 1]
s[i, j] ← « = »
sinon si l[i − 1, j] > l[i, j − 1])
alors l[i, j] ← l[i − 1, j]
s[i, j] ← « ← »
sinon l[i, j] ← l[i, j − 1]
s[i, j] ← « → »
renvoyer l[n, m] et s
Affichage-PLSC(s, A, i, j)
si i = 0 ou j = 0 alors renvoyer
si s[i, j] = « = »
alors Affichage-PLSC(s, A, i − 1, j − 1)
affiche A[i]
sinon si s[i, j] = « ← » alors Affichage-PLSC(s, A, i − 1, j)
si s[i, j] = « → » alors Affichage-PLSC(s, A, i, j − 1)
On appelle initialement PLSSC-ProgDyn(A, B) puis Affichage-PLSC(s, A, n, m).
2