Corrigé du TD 5 : Plus longue sous-séquence commune
Plus longue sous-séquence commune La plus longue sous-séquence commune est un problème fondamental en algorithmique, souvent abordé dans le cadre de la programmation dynamique. Cet article explique comment déterminer la longueur d'une sous-séquence commune maximale entre deux séquences, ainsi que les algorithmes associés pour résoudre ce problème.
D'après le document Corrigé du TD 5 : Plus longue sous-séquence commune
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Algorithmics/Dynamic Programming · PDF · 2 pages
Afficher l'aperçu du document
Plus longue sous-séquence commune
La plus longue sous-séquence commune est un problème fondamental en algorithmique, souvent abordé dans le cadre de la programmation dynamique. Cet article explique comment déterminer la longueur d'une sous-séquence commune maximale entre deux séquences, ainsi que les algorithmes associés pour résoudre ce problème. Vous apprendrez également à construire une telle sous-séquence et à analyser la complexité des algorithmes impliqués.
Définition et exemples de sous-séquences
Une séquence est une suite finie de symboles pris dans un ensemble fini. Si u = ⟨a1, a2, ..., an⟩ est une séquence, où a1, a2, ..., an sont des lettres, l'entier n est la longueur de u. Une séquence v = ⟨b1, b2, ..., bm⟩ est une sous-séquence de u si des entiers i1, i2, ..., im existent tels que bk = aik pour k ∈ [1, m].
Par exemple, v = ⟨B, C, D, B⟩ est une sous-séquence de u = ⟨A, B, C, B, D, A, B⟩ correspondant à la suite d'indices ⟨2, 3, 5, 7⟩.
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 si elle est de longueur maximale. Par exemple, les séquences ⟨B, C, B, A⟩ et ⟨B, D, A, B⟩ sont des plus longues sous-séquences communes de ⟨A, B, C, B, D, A, B⟩ et de ⟨B, D, C, A, B, A⟩.
Résolution par programmation dynamique
Récurrence pour la longueur de la sous-séquence commune
Pour déterminer la longueur d'une sous-séquence commune maximale à u = ⟨a1, a2, ..., an⟩ et v = ⟨b1, b2, ..., bm⟩, on note L(i, j) la longueur d'une sous-séquence commune maximale à ⟨a1, a2, ..., ai⟩ et ⟨b1, b2, ..., bj⟩. La récurrence définissant L(i, j) est :
L(i, j) = {
0 si i = 0 ou j = 0,
1 + L(i - 1, j - 1) si ai = bj,
max(L(i, j - 1), L(i - 1, j)) sinon.
}
Si ai ≠ bj, une plus longue sous-séquence commune ne peut pas se terminer par une lettre égale à ai et à bj. Ainsi, elle peut se terminer par ai ou bj, ce qui nous donne les deux cas à considérer.
Algorithme récursif
Un algorithme récursif pour calculer la longueur de la plus longue sous-séquence commune est le suivant :
PLSSC-Récursif(A, i, B, j) {
si i = 0 ou j = 0 alors renvoyer 0
sinon si A[i] = B[j] alors renvoyer 1 + PLSSC-Récursif(A, i - 1, B, j - 1)
sinon renvoyer max(PLSSC-Récursif(A, i - 1, B, j), PLSSC-Récursif(A, i, B, j - 1))
}
Cet algorithme a une complexité exponentielle dans le cas où les deux séquences n'ont pas d'éléments en commun.
Algorithme de programmation dynamique
Pour améliorer l'efficacité, on peut utiliser la programmation dynamique. Voici l'algorithme :
PLSSC-ProgDyn(A, B) {
n ← longueur(A)
m ← longueur(B)
pour i ← 1 à n faire l[i, 0] ← 0
pour j ← 1 à m faire l[0, j] ← 0
pour i ← 1 à n faire
pour j ← 1 à 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]
}
La complexité de cet algorithme est O(nm) en raison des deux boucles imbriquées.
Construction de la sous-séquence commune
Pour construire la plus longue sous-séquence commune, on peut modifier l'algorithme précédent :
PLSSC-ProgDyn(A, B) {
n ← longueur(A)
m ← longueur(B)
pour i ← 1 à n faire l[i, 0] ← 0
pour j ← 1 à m faire l[0, j] ← 0
pour i ← 1 à n faire
pour j ← 1 à m faire
si A[i] = B[j] 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
}
Pour afficher la sous-séquence, on utilise :
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)
sinon
Affichage-PLSC(s, A, i, j - 1)
}
On appelle initialement PLSSC-ProgDyn(A, B) puis Affichage-PLSC(s, A, n, m) pour obtenir la sous-séquence.
Points clés à retenir
Voici les principaux points à retenir concernant la plus longue sous-séquence commune :
- Une sous-séquence est une suite d'éléments d'une séquence, conservant l'ordre.
- La programmation dynamique permet de résoudre le problème de manière efficace.
- La complexité de l'algorithme dynamique est O(nm).
- Il est possible de construire et d'afficher la sous-séquence commune.
Questions fréquentes
Qu'est-ce qu'une sous-séquence ?
Une sous-séquence est une séquence dérivée d'une autre séquence, où les éléments conservent leur ordre d'apparition. Par exemple, dans la séquence ⟨A, B, C, D⟩, ⟨B, D⟩ est une sous-séquence.
Comment fonctionne l'algorithme de programmation dynamique pour la plus longue sous-séquence commune ?
L'algorithme utilise une matrice pour stocker les longueurs des sous-séquences communes, en remplissant cette matrice selon des règles basées sur la comparaison des éléments des deux séquences.
Quelle est la complexité de l'algorithme récursif ?
L'algorithme récursif a une complexité exponentielle, car il explore toutes les combinaisons possibles des éléments des deux séquences, ce qui devient rapidement impraticable pour de grandes séquences.
Peut-on afficher la sous-séquence commune ?
Oui, en utilisant un algorithme modifié qui suit les décisions prises lors du remplissage de la matrice, on peut reconstruire et afficher la sous-séquence commune.
Commentaires
Aucun commentaire pour le moment. Posez la première question.