Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

5 pages
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


Voir plus Voir moins
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