TD d’algorithmique avanc´ee
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)
Publicité
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
Publicité
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.
Publicité
2. ´Ecrivez alors un algorithme r´ecursif calculant la longueur de la plus longue sous-s´equence commune de
deux s´equences.
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.
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.
Publicité
5. Quelle est la complexit´e de cet algorithme ?
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.