Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Algorithmique et Programmation TD n1 : Recherche de motif Morphismes sur le mono¨ıde libre
Ecolenormalesupe´rieure D´epartementdinformatique td-algo@di.ens.fr 2011-2012
1 PetitsRappels Motsxetzsont, respectivement, unee´xrpet 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¸aey. Mono¨ıde libreattnodnn´eunEalphabetfiniAsd´ermfos)ni(tsomsedelbmesnel,edrtseleteAon´t,e Aoupr´deedrealteamtu´neiconc,nof,anitelroemmono¨ıde libreesil(biltidtesracers´el´ements nesatisfontaucunee´quationnon-triviale). ∗ ∗ MorphismeUnmorphismedu mono¨ıde libre est une fonctionτ:AA →telle queτ(x.y) =τ(x)(y). Ilend´ecoulequunmorphismeestentie`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(ouLhpbatedeealunadtln´onme`tse)esys-A, d’un morphismeτet d’un mot initialω0.Ond´endemeto: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´ciauxF,+et-,quonmunitdelaturtle interpretation, danslaquelleond´eplaceunetortuesurlaquelleestx´eeuncrayon.LeF(Forward)signieavancer, le+signietourner`agauche,etle-signietournera`droite.Langleduquelilfauttournerest spe´ci´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
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin