Aller au contenu

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

TD d’algorithmique avancée

Algorithmique, programmation dynamique · 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. 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.

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