TD d’algorithmique avancée
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. Ce document présente une méthode pour déterminer la longueur d'une sous-séquence commune maximale entre deux séquences, ainsi que des algorithmes récursifs et dynamiques pour résoudre ce problème.
D'après le document TD d’algorithmique avancée
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Algorithmique, programmation dynamique · 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. Ce document présente une méthode pour déterminer la longueur d'une sous-séquence commune maximale entre deux séquences, ainsi que des algorithmes récursifs et dynamiques pour résoudre ce problème. Les étudiants apprendront à définir les sous-séquences, à écrire des algorithmes et à analyser leur complexité.
Définition des 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
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 la suivante :
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 provenir soit de L(i − 1, j), soit de L(i, j − 1).
Algorithme récursif
Un algorithme récursif pour calculer la longueur de la plus longue sous-séquence commune est donné par :
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))
Complexité de l'algorithme récursif
La complexité de cet algorithme est exponentielle dans le cas où les deux séquences n’ont pas d’éléments en commun. La complexité est définie par la récurrence :
T(n, m) = { 0 si n = 0 ou m = 0, T(n, m − 1) + T(n − 1, m) sinon. }
Ce qui donne T(n, m) = Ω(2^min(m,n)).
Algorithme dynamique
Pour améliorer l'efficacité, un algorithme suivant le paradigme de la programmation dynamique peut être utilisé :
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]
Complexité de l'algorithme dynamique
La complexité de cet algorithme est due aux deux boucles imbriquées : T(n, m) = O(nm).
Construction de la sous-séquence
Pour construire la plus longue sous-séquence commune et l'afficher, on modifie 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).
Points clés à retenir
Voici les points essentiels à retenir concernant la plus longue sous-séquence commune :
- Une sous-séquence est une suite d'éléments d'une séquence originale.
- La programmation dynamique est une méthode efficace pour résoudre ce problème.
- 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 suite d'éléments d'une séquence originale, où les éléments sont pris dans le même ordre que dans la séquence d'origine, mais pas nécessairement consécutifs.
Comment fonctionne l'algorithme de programmation dynamique ?
L'algorithme de programmation dynamique construit une table pour stocker les longueurs des sous-séquences communes, en utilisant des relations de récurrence pour éviter de recalculer les mêmes valeurs.
Quelle est la complexité de l'algorithme récursif ?
La complexité de l'algorithme récursif est exponentielle, soit Ω(2^min(m,n)), en raison de la nature des appels récursifs lorsque les séquences n'ont pas d'éléments en commun.
Peut-on afficher la sous-séquence commune ?
Oui, en modifiant l'algorithme dynamique, il est possible de construire et d'afficher la plus longue sous-séquence commune en utilisant une table de suivi.
Commentaires
Aucun commentaire pour le moment. Posez la première question.