Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Plus longue sous-séquence commune
Résumé
En informatique théorique, la plus longue sous-séquence commune à deux suites, ou deux chaînes de caractères, est une sous-suite extraite des deux suites, et de taille maximum. La résolution de ce problème peut être obtenue par programmation dynamique.
La généralisation à un nombre arbitraire de suites est un problème NP-difficile : le temps d'exécution de tout algorithme est exponentiel en le nombre de séquences.
Pour les deux séquences de caractères suivantes :
« abcde »,
« ceij »,
la plus longue sous-séquence commune est « ce ».
Dans ce problème, il est nécessaire que les éléments communs soient dans le même ordre dans les différentes séquences, mais pas qu’ils soient obligatoirement consécutifs : « e » n’est pas consécutif à « c » dans la première séquence.
On constate par dénombrement qu'il existe sous-séquences pour une chaîne de longueur . Les essayer toutes par force brute pour trouver la plus longue qui soit une sous-séquence d'une autre chaîne a donc une complexité exponentielle, ce qui n'est pas souhaitable en pratique.
Une telle sous-séquence peut être obtenue par un algorithme de programmation dynamique dont le temps d'exécution est proportionnel au produit des longueurs des deux séquences.
Il est possible de ramener le problème de recherche de plus longue sous séquence commune (PLSC) entre deux chaînes données à une recherche entre deux chaînes de taille inférieure grâce au théorème suivant (où désigne les premiers caractères de la séquence ):
Les trois cas , et sont exhaustifs, ce qui permet bien de se ramener à un problème de taille inférieure.
On crée un tableau à deux dimensions dans lequel chaque case est destiné à contenir la longueur des PLSCs entre et . On peut alors calculer de proche en proche pour chaque couple d'indice et . Du théorème précédent découle en effet la formule:
Le calcul du contenu des cases de peut être effectué avec une complexité , car le contenu de chaque case est calculable à partir des cases précédente en .
La formule précédente permet de calculer de proche en proche les cases de .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.