Aller au contenu

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

Corrigé du TD 5 : Plus longue sous-séquence commune

Algorithmics/Dynamic Programming · PDF · 2 pages

Afficher l'aperçu du document

Consulter le document original →

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.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions