L'oracle des facteurs

Thèmes abordés

Oracle des facteurs, interface graphique, construction, alphabet, mot vide

Résumé du document

Un alphabet est un ensemble fini non vide dont les éléments sont appelés des lettres.
Exemple : l'alphabet A={a,b,c}.
Un mot sur un alphabet A est une suite finie d'éléments de A.
Exemple : le mot « bbca ».
La suite de zéro lettre est appelée le mot vide et notée E.
L'ensemble de tous les mots sur l'alphabet A est noté A*.
L'ensemble de tous les mots sur l'alphabet A excepté le mot vide est noté A+.

Extraits

[...] Un mot accepté par l'Oracle des Facteurs d'une séquence s n'est pas toujours facteur de s. Nous avons élargis notre recherche sur l'oracle d'un ensemble de mots < number > Introduction Construction de l'oracle des facteurs Application Tests et interface graphiques Conclusion Application : Exemples d'application Année universitaire 2011-2012 < number > L'oracle des facteurs a prouvé son efficacité dans plusieurs domaines tels que: La recherche de motifs dans une ou plusieurs séquences . La compression de textes . La détection de motifs répétés dans de grandes séquences . Improvisation musicale assistée par ordinateur . [...]

[...] pour un mot ω de longueur ω = m l'oracle des facteurs de ω est donc l'automate ) où : – ,m. – q0=0 est l'état initial. – F=Q est l'ensemble des états terminaux. – est la fonction de transition. Delta.jpgImage1.png Introduction Construction de l'oracle des facteurs Application Tests et interface graphiques Conclusion Construction de l'oracle des facteurs : Définition Algorithme de construction Exemples < number > Année universitaire 2011-2012 Pour un mot ω de longueur m L'Oracle des facteurs de ω: Reconnait au moins tous les facteurs de ω Possède exactement m+1 états. [...]

[...] Illustration par une interface graphique . Toutefois les questions qui se pose c'est celle qui concerne la caractérisation du langage reconnu par l'automate d'Oracle Des Facteurs ainsi la taille de l'automate minimale en nombre des transitions. Nous avons également introduit une définition complète de la construction d'Oracle des facteurs puis une application illustratif pour mieux comprendre puis une partie de l'interface graphique basé sur les bibliothèques Swing et AWT, à fin de facilite la manipulation. [...]

[...] Exemple : le mot « bbca » La suite de zéro lettre est appelée le mot vide et notée Ԑ . L'ensemble de tous les mots sur l'alphabet A est noté A*. l'ensemble de tous les mots sur l'alphabet A excepté le mot vide est noté A+. Soit un mot ω sur un Alphabet * tel que ω =uxv avec u,v,x x est appelé un facteur de ω. u est appelé un préfixe de ω. v est appelé un suffixe de ω. [...]

[...] L1 ,ab,ba, ,abcc, ,acbcc,accbc ,aabb,abab ,accbbbccaac Opérations rationnelles sur les langages: Union L1 L2={ω tq ω L1 ou ω L2} Intersection L1 L2={ω tq ω L1 et ω L2} Concaténation L1L2={ω= ω1 ω2 tq ω1 L1 et ω2 L2} Image1.pngCapture-1.jpgapartient.jpgapartient.jpginter.jpgapartient.jpgapartient.jpgapartient.jpgapartient.jpg Introduction Construction de l'oracle des facteurs Application Tests et interface graphiques Conclusion Introduction : Alphabet et Mots Langages Automates < number > Année universitaire 2011-2012 Définition: Un automate fini déterministe (AFD) est un modèle mathématique qui consiste en : - Q un ensemble d'états. - un ensemble de symboles d'entrée (alphabet). une fonction de transition qui prend comme argument un état et un symbole d'entrée et qui retourne un état. q0, un état initial appartenant à Q. F , un ensemble d'états finals ou états d'acceptation. [...]