École Nationale d’Ingénieurs de Carthage
Département d’Informatique
—***—
Examen de la session principale en
Algorithmique Avancée & Complexité
12 janvier 2014
Classe : 2IngInfoA,B,C,D,E Durée : 1h 300 Nombre de pages : 3 pages
Il est conseillé de lire attentivement les énoncées avant de se plonger sur la feuille des
réponses. Les copies propres et bien soignées sont très appréciées. Il sera tenu
compte de la lisibilité des réponses. Le barème donné est indicatif. Aucun document
n’est autorisé.
Bonne chance !
Problème I
En biologie, on doit souvent comparer l’ADN de deux (ou plusieurs) organismes. Un
échantillon d’ADN est une suite de molécules appelées bases, les bases possibles étant
« l’adénine », « la guanine », « la cytosine » et « la thymine ». Si l’on repré-
sente chacune des ces bases par son initiale, un échantillon d’ADN s’exprime sous la forme
d’une séquence prise sur l’ensemble fini {A,C,G,T}.
Ainsi, l’ADN d’un organisme sera S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA alors que
l’ADN d’un autre sera S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA.
Comparer deux échantillons d’ADN permet, entre autres, de déterminer leur degré
de « similitude », qui mesure en quelque sorte la façon dont les deux organismes sont
apparentés.
La similitude peut se définir de bien des façons différentes. Par exemple, on peut dire
que deux échantillons d’ADN sont semblables si l’un est une sous-séquence de l’autre.
Autre possibilité : on pourrait dire que deux échantillons sont semblables si le nombre de
modifications (distance d’édition) nécessaires pour transformer l’un en l’autre est faible.
Un autre moyen de mesurer la similitude des échantillons S1 et S2 est de trouver un
troisième échantillon S3 tel que les bases de S3 apparaissent dans S1 et dans S2 ; ces bases
doivent apparaître dans le même ordre, mais pas forcément de manière consécutive. Plus
l’échantillon S3 trouvé est long, plus S1 et S2 sont semblables. Dans notre exemple, le
plus long S3 est GTCGTCGGAAGCCGGCCGAA.
Nous formaliserons cette dernière notion de similitude sous le nom de problème de
la plus longue sous-séquence commune (PLSC). Une sous-séquence d’une séquence
donnée est tout simplement constituée de la séquence de départ, à laquelle on a retiré
certains éléments (éventuellement zéro).
Par exemple, Z =< B, C, D, B > est une sous-séquence de X =< A, B, C, B, D, A, B >,
correspondant à la séquence d’indices < 2, 3, 5, 7 >.
Étant données deux séquences X et Y , on dit qu’une séquence Z est une sous-séquence
commune de X et Y si Z est une sous-séquence à la fois de X et de Y .
Par exemple, si X =< A, B, C, B, D, A, B > et Y =< B, D, C, A, B, A >, la séquence
< B, C, A > est une sous-séquence commune de X et de Y . Toutefois, la séquence <
B, C, A > n’est pas une plus longue sous-séquence commune (PLSC) de X et Y , puisqu’elle
est de longueur 3 et que la séquence < B, C, B, A >, qui est aussi commune à X et Y ,
est de longueur 4. La séquence < B, C, B, A > est une PLSC de X et Y , de même que la
séquence < B, D, A, B >, puisqu’il n’existe pas de sous-séquence commune de longueur
supérieure ou égale à 5.
Dans le problème PLSC, on dispose au départ de deux séquences X =< x1 , x2 , ..., xm >
et Y =< y1 , y2 , ..., yn >, et on souhaite trouver une sous-séquence commune à X et Y de
longueur maximale.
Partie A. Caractérisation d’une plus longue sous-séquence commune (6 pts)
La technique primaire de résolution du problème de la PLSC consiste à énumérer toutes
les sous-séquences de X et les tester pour voir si elles sont aussi des sous-séquences de Y .
1. Soit X =< x1 , x2 , . . . , xm > une séquence de m bases. Dans les sous séquences de
X, chaque base peut (ou non) apparaître. Montrer que X admet 2m sous séquences
possibles (y compris X et la séquence vide ).
Étant donnée une séquence X =< x1 , x2 , . . . , xm >, on définit le ième préfixe de X, pour
i = 0, 1, . . . , m, par Xi =< x1 , x2 , . . . , xi >. Par exemple, si X =< A, B, C, B, D, A, B >,
alors X4 =< A, B, C, B > et X0 représente la séquence vide.
Soient deux séquences X =< x1 , x2 , . . . , xm > et Y =< y1 , y2 , . . . , yn >, et soit Z =<
z1 , z2 , . . . , zk > une PLSC de X et Y .
a. Si m = 0 ou n = 0 alors la longueur de la PLSC serait 0 ;
b. Si xm = yn , alors zk = xm = yn et Zk 1 est une PLSC de Xm 1 et Yn 1 .
c. Si xm 6= yn , alors Zk serait la PLSC de Xm 1 et Yn ou la PLSC de Xm et Yn 1 . On
retient le plus long.
2. Justifier la récurrence plus haut ;
3. Montrer, à travers un petit exemple, que les sous-problèmes de la PLSC sont super-
posés (C’est-à-dire les mêmes sous-problèmes sont rencontrés plusieurs fois).
Partie B. Approche récursive (6 pts)
4. Écrire une procédure récursive qui calcule la longueur de la PLSC de deux séquences.
La fonction prend en argument deux séquences et leurs longueurs respectives.
5. Donner une estimation asymptotique de la complexité au pire des cas de cette
procédure.
Partie C. Résolution par programmation dynamique (8 pts)
L’inconvénient avec la versions récursive est que les mêmes sous-prblèmes sont traîtés
plusieurs fois. Il serait plus judicieux de sauvegarder les solutions des sous-problèmes
dans un tableaux.
Nous considèrons le tableaux C de dimension (m + 1) ⇥ (n + 1). La première ligne et la
première colonne du tableau concernent la séquence vide. La procédure LONGUEUR-PLSC
prend deux séquences X =< x1 , x2 , . . . , xm > et Y =< y1 , y2 , . . . , yn > en entrée. Elle
stocke les valeurs C[i, j] dans un tableau C[0..m, 0..n] dont les éléments sont calculés dans
l’ordre des lignes. Chaque case est déduite d’aprés les cases voisines (3 cases). La longueur
de la PLSC se trouve dans la dernière case (C[m, n]).
X x0 x1 x2 ... xm
Y i\j 0 1 2 ... m
y0 0
y1 1
y2 2
.. ..
. .
yn n
6. Écrire la procédure LONGUEUR-PLSC() ;
7. Calculer la complexité de cette procédure ;
8. On peut maintenant déterminer la PLSC en remontant le tableaux C depuis la
dernière case jusqu’à une case qui contient la valeur 0.
Écrire une procédure qui prend en argument le tableau C que nous avons calculé
avec la procédure précédante et les deux séquences X et Y et affiche leur PLSC.
