Algorithmique et Programmation TD n Recherche de motif Morphismes sur le monoıde libre

Description

Algorithmique et Programmation TD n? 1 : Recherche de motif Morphismes sur le monoıde libre Ecole normale superieure Departement d'informatique 2011-2012 1 Petits Rappels Mots x et z sont, respectivement, un prefixe et un suffixe d'une chaıne de caracteres ? si on peut ecrire ? = x.z. De meme, y est un facteur de ? si on peut ecrire ? = x.y.z, ou x et z sont eventuellement vides. On dit aussi que x est un sous-mot de y si on peut obtenir x en effac¸ant des lettres de y. Monoıde libre Etant donne un alphabet fini A, l'ensemble des mots (finis) formes de lettres de A, note A?, muni de l'operateur de concatenation, forme le monoıde libre (il est dit “libre” car ses elements ne satisfont aucune equation non-triviale). Morphisme Un morphisme du monoıde libre est une fonction ? : A? ? A? telle que ?(x.y) = ?(x).?(y). Il en decoule qu'un morphisme est entierement determine par les images des lettres de A. 2 Echauffement Exercice 1 (?) : Sous-mot. Donnez un algorithme qui determine si un mot x est un sous-mot d'un autre mot y.

• lettres ? ?


• paire de mots distincts


• entier de la question precedente


• ?n


• croıt de fac¸on polynomiale


• matrice-matrice


• morphismes uniformes


• monoıde libre

Sujets

• exercice
• exercices

Informations

• Publié par: pefav
• Nombre de lectures: 70
• Langue: Français

Extrait

Algorithmique et Programmation ◦ TD n1 : Recherche de motif Morphismes sur le mono¨ıde libre

Ecolenormalesupe´rieure D´epartementd’informatique [e-mail] 2011-2012

1 PetitsRappels Motsxetzsont, respectivement, unee´xfirpet unsuffixesere`tcaracedenhaˆıunecd’ωeircr´eutpeonsi ω=x.zem.Dmeˆe,yest unfacteurdeωnpeut´ecrireoisω=x.y.z,`ouxetzsno´teltuenevntmele vides. On dit aussi quexest unsous-motdeysi on peut obtenirxtretdeestnaclsedne¸affey. Mono¨ıde libreattnodnn´eunEalphabetfiniAsd´ermfos)ni(fitsomsedelbmesne’l,edrtseleteAon´t,e ∗ Aoupr´deedrealt’eamtu´neiconc,nof,anitelroemmono¨ıde libreesil(bil“tidtesrac”ers´el´ements nesatisfontaucunee´quationnon-triviale). ∗ ∗ MorphismeUnmorphismedu mono¨ıde libre est une fonctionτ:AA →telle queτ(x.y) =τ(x).τ(y). Ilend´ecoulequ’unmorphismeestentie`rementde´termin´eparlesimagesdeslettresdeA.

2 Echauffement

Exercice 1 (?) : Sous-motoDnn.laogzenusenimnuitothriqume´eidrmtexest un sous-mot d’un autre moty.aLocpmelixerteˆtiode´tO(|y|).

3syst`emedeLindenmayer UnayerdenmeLinemedsy`ts(ouLhpbated’eealunadtln´onme`tse)esys-A, d’un morphismeτet d’un mot initialω 0 .Ond´efindemeto:stialustiω i+1 =τ(ω i ). On va supposer dans toute la suite que |τ(α)| ≥1 pour toutes les lettresα∈ Ae´er:rxerePa.disnoctuepnoelpm τ(A) =AB, τ(B) =D, τ(C) =CD, τ(D) =C Et on a : ω 0 =A ω 1 =AB ω 2 =ABD ω 3 =ABDC ω 4 =ABDCCD ω 5 =ABDCCDCDC . Cessyst`emesdere´e´critureont´et´eintroduitnotammentpourdessinerdesfractales.Pourcela,onse donneunalphabetavecdessymbolesspe´ciaux“F”,“+”et“-”,qu’onmunitdelaturtle interpretation, danslaquelleond´eplaceunetortuesurlaquelleestfix´eeuncrayon.Le“F”(Forward)signifie“avancer”, le“+”signifie“tourner`agauche”,etle“-”signifie“tournera`droite”.L’angleduquelilfauttournerest spe´cifi´eunefoispourtoute.Lesautressymbolesnesontpasinterpre´t´es.Exemples: – lacourbe de Koch (ω 0 =F, µ(F) =F+F-F-F+F, angle=90˚). – Lacourbe de Hilbert (ω 0 =L, µ(L) =+RF-LFL-FR+, µ(R) =-LF+RFR+FL-, angle=90˚). – Lacourbe du Dragon (ω 0 =FX, µ(X) =X+YF+, µ(Y) =-FX-Y, angle=90˚).

1