Plus longue sous-séquence commune
- Plus longue sous-séquence commune
-
La détermination de la plus longue sous-séquence commune à différentes (super-) séquences et un problème NP-complet difficile.
Pour les deux séquences de caractères suivantes :
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.
Informatique
La résolution de ce problème peut être faite par programmation dynamique. Le temps d'exécution de l'algorithme est exponentiel en le nombre de séquences, ce qui est prévisible pour un problème NP-complet. Néanmoins, il est polynomial pour un nombre de séquences fixé.
Catégorie :
- Algorithme sur les chaînes de caractères
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Plus longue sous-séquence commune de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Plus longue sous-sequence commune — Plus longue sous séquence commune La détermination de la plus longue sous séquence commune à différentes (super ) séquences et un problème NP complet difficile. Pour les deux séquences de caractères suivantes : « abcde »,… … Wikipédia en Français
Plus grand commun diviseur — Pour une introduction à cette notion, consulter l article : PGCD de nombres entiers. En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui… … Wikipédia en Français
Influenzavirus A Sous-Type H5N1 — Virus A (H5N1) … Wikipédia en Français
Influenzavirus A sous-type H5N1 — Virus A (H5N1) … Wikipédia en Français
Influenzavirus a sous-type h5n1 — Virus A (H5N1) … Wikipédia en Français
Comparaison de fichiers — En informatique, la comparaison de fichiers consiste à comparer leur contenu, en isolant leurs différences de leur contenu commun. Le résultat de la comparaison peut être affiché en environnement graphique, en mode texte, ou comme partie de… … Wikipédia en Français
Liste des films tournés dans le Val-d'Oise — Plus de 400 films auraient été tournés dans le Val d Oise depuis 1950[1] ainsi qu un certain nombre d œuvres cinématographiques et télévisuelles. Voici une liste à compléter de films, téléfilms, feuilletons télévisés, films documentaires...… … Wikipédia en Français
MÉMOIRE — La mémoire est la propriété de conserver et de restituer des informations. Cette propriété n’est pas exclusivement propre à l’homme. Celui ci la partage avec les organismes vivants et certaines machines, de sorte qu’il est nécessaire de préciser… … Encyclopédie Universelle
Spectacles de Johnny Hallyday — Cette page recense en respectant la chronologie les spectacles de Johnny Hallyday. Nous y indiquons également les tournées à caractères exceptionnelles, à l exemple du Johnny Circus de 1972. sont recensés aussi les concerts données dans divers… … Wikipédia en Français
RÉCEPTEURS MEMBRANAIRES — Le transfert d’information d’un organe à l’autre ou à l’extérieur des organes fait appel, chez les animaux comme chez les plantes, à des signaux chimiques . La caractérisation de ces signaux et l’analyse des règles de leur émission et de leur… … Encyclopédie Universelle
