TD d’algorithmique avancée
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 < ... <
Publicité
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
Publicité
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.
2. Écrivez alors un algorithme récursif calculant la longueur de la plus longue sous-séquence commune de
deux séquences.
3. Montrez que cet algorithme est de complexité au moins exponentielle dans le cas où les deux séquences
Publicité
n’ont pas d’éléments en commun.
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.
5. Quelle est la complexité de cet algorithme ?
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.