TD d’algorithmique avanc´ee
Corrig´e du TD 5 : plus longue sous-s´equence commune
Jean-Michel Dischler et Fr´ed´eric Vivien
Probl´ematique
Une s´equence est une suite finie de symboles pris dans un ensemble fini. Si u = (cid:104)a1, a2, ..., an(cid:105) est une
s´equence, o`u a1, a2, ..., an sont des lettres, l’entier n est la longueur de u. Une s´equence v = (cid:104)b1, b2, ..., bm(cid:105)
est une sous-s´equence 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´equence de
u = (cid:104)A, B, C, B, D, A, B(cid:105) correspondant `a la suite d’indice (cid:104)2, 3, 5, 7(cid:105).
Une s´equence w est une sous-s´equence commune aux s´equences u et v si w est une sous-s´equence de u et
de v. Une sous-s´equence commune est maximale ou est une plus longue sous-s´equence si elle est de longueur
maximale. Par exemple : les s´equences (cid:104)B, C, B, A(cid:105) et (cid:104)B, D, A, B(cid:105) sont des plus longues sous-s´equences
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´esolution par programmation dynamique
1. On cherche a d´eterminer la longueur d’une sous-s´equence 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´equence commune maximale `a (cid:104)a1, a2, ..., ai(cid:105)
et (cid:104)b1, b2, ..., bj(cid:105) (0 ≤ j ≤ m, 0 ≤ i ≤ n). Donnez une r´ecurrence d´efinissant L(i, j). Indication : on
pourra distinguer les cas ai = bj et ai (cid:54)= bj.
L(i, j) =
0
Advertisement
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.
(1)
En effet, si ai (cid:54)= bj, une plus longue sous-s´equence 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 ´egale a ai et a bj, et donc une plus longue sous-s´equence commune
– soit ne se termine pas par ai et elle est alors une plus longue sous-s´equence commune des s´equences
(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´equence commune des s´equences
(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´equence 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´efixe (la sous-s´equence moins son
dernier ´el´ement) est une plus longue sous-s´equence commune de (cid:104)a1, a2, ..., ai−1(cid:105) et (cid:104)b1, b2, ..., bj−1(cid:105).
2. ´Ecrivez alors un algorithme r´ecursif calculant la longueur de la plus longue sous-s´equence commune de
deux s´equences.
PLSSC-R´ecursif(A, i, B, j)
si i = 0 ou j = 0
alors renvoyer 0
Advertisement
sinon si A[i] = B[j]
alors renvoyer 1+ PLSSC-R´ecursif(A, i − 1, B, j − 1)
sinon renvoyer max(PLSSC-R´ecursif(A, i − 1, B, j), PLSSC-R´ecursif(A, i, B, j − 1))
3. Montrez que cet algorithme est de complexit´e au moins exponentielle dans le cas o`u les deux s´equences
n’ont pas d’´el´ements en commun.
1
Dans ce cas, on se trouve toujours dans le troisi`eme cas de l’´equation 1 et la complexit´e est d´efinie par
la r´ecurrence :
T (n, m) = (cid:26)
0
T (n, m − 1) + T (n − 1, m)
si n = 0 ou m = 0,
sinon.
D’o`u 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. ´Ecrivez alors un algorithme suivant le paradigme de la programmation dynamique et calculant la
longueur de la plus longue sous-s´equence commune de deux s´equences.
PLSSC-ProgDyn(A, B)
n ← longueur (A)
Advertisement
m ← longueur (B)
pour i ← 1 `a n faire l[i, 0] ← 0
pour j ← 1 `a m faire l[0, j] ← 0
pour i ← 1 `a n faire
pour j ← 1 `a 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´e de cet algorithme ?
La complexit´e est due aux deux boucles imbriqu´ees : T (n, m) = O(nm).
6. Modifiez l’algorithme pr´ec´edent pour que l’on puisse en plus construire une plus longue sous-s´equence
commune et affichez une telle sous-s´equence.
PLSSC-ProgDyn(A, B)
n ← longueur (A)
m ← longueur (B)
pour i ← 1 `a n faire l[i, 0] ← 0
pour j ← 1 `a m faire l[0, j] ← 0
pour i ← 1 `a n faire
pour j ← 1 `a m faire
si A[i] = B[j]
Advertisement
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