TD d’algorithmique avancée

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.

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.

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.