Plus longue sous-sequence commune
- 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 :
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
Du fait de son caractère NP-complet, il est possible de proposer un algorithme de résolution de ce problème. Un tel algorithme est généralement basé sur les principes de programmation dynamique.
- Portail de l’informatique
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-sequence commune de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
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 », « ceij », la plus longue sous… … 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