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 :

  • « 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.

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 Portail de l’informatique
Ce document provient de « Plus longue sous-s%C3%A9quence commune ».

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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”