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

Publié par

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


Publié le : mardi 19 juin 2012
Lecture(s) : 70
Tags :
Source : di.ens.fr
Nombre de pages : 5
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
– Laplante fractale (ω0=X, µ(X) =F-[[X]+X]+F[+FX]-X, µ(F) =FF, angle=25˚). – etc. Exercice 2 (?enti´equelle´ne´G:)snoitare.Donanglenuzmhqerotipeuietrmdtecr´eeriωnla`ce´,nar en tempsO(|ω0|+|ω1|+∙ ∙ ∙+|ωn|) et en espaceO(n). Exercice 3 (??eotri´laesa`ecc:A). 1. Montrezqu’on peut calculer la longueur deωnen tempsO(lognpyto`hses,uolshesles)equetout op´erationsarithm´etiquesseectuententempsconstant.Cettehypothe`seest-elleraisonnable? 2. Donnezun algorithme qui produit leitcaraceme`-e`eredωnen tempsO(n),souslamˆemeh-opy the`se. 3.Quellecomplexit´eobtient-ondanslapremie`requestionsionnefaitpaslhypoth`eseenquestion?
4 Morphismesuniformes Un morphisme du mono¨ıde libre pourvu d’un entier`tel que|τ(α)|=`pour toutes les lettresα∈ A estappel´eunmorphismeuniforme,elpseL.prommsihunesorifsomedentpsorrp´itee´ts`resfortes.Parexem dans le cas des morphismes non-uniformes il n’existe (prouvablement!)pas d’algorithmeemrnie´etuqdi sideuxmorphismespeuventcoı¨ncidersuruneentr´eenontriviale(c.a.d.siτ(x) =µ(x) pourx6=). Ce proble`meinde´cidableclassique(quevousalleze´tudierplustard)sappelleleanceblrope`emedocrrseopdn de Post. Exercice 4 (?ecedreoronspncda:)borPme`lermfonituosePed. 1.Donnezunalgorithmequi,´etantdonne´deuxmorphismesuniformesµetτ,istesenxelite´dimre un mot non-vidextel queµ(x) =τ(x). 2.Donnezunalgorithmequi,´etantdonne´deuxmorphismesuniformesµetτ´d,reteenimlisisexte une paire de mots distincts et non-vides tels queµ(x) =τ(y).
Exercice 5 (?) : Point fixe d’un morphisme uniforme. Onsuppose (pour se simplifier la vie) que l’entier`ue.Onva´eg´egal`a2puopesqrlamenesttseuqalece´rpnoieentde´eitfaenstdω0=α, et queτ(α) commence par la lettreα. 1.D´emontrezqueωn´reutpnsedexeωn+1. Cela justifie qu’on parle de la“limite”ωelahtemuqeigne´`nreexilteisalunrigorac,i-`emelettreen temps fini (c’est une structure co-inductive). En fait,ωest le plus petit point fixe du morphisme qui commence parα. 2. Donnezun algorithme qui calculeω[i] en tempsO(logi).
Exercice 6 (??uesraftc´eenexitompl):Cun algorithme (donc un programme qui. Donneztermine) qui produit la liste des facteurs de taillekdeω.Ildoitˆetreaupirauqetardeuqialneiltadelenso r´esultat.
2
5 Solutions
Ilnyaaucunedicult´e. 1:i0 2:j0 3:whilei <|x|andj <|y|do 4:ifx[i] =y[j]thenii+ 1 5:jj+ 1 6:end while 7:return(i=|x|)
Solution de l’exercice 1
Solution de l’exercice 2 1.Larestrictionsurlespaceinterditdege´ne´rersuccessivementω1, . . . , ωn1, puisωn. Onpeutrepr´esenterleprocessusdege´ne´rationdeω1, . . . , ωnrd(orerbnaeummcoqaeuu`hc)eo,no´n noeudestd´ecor´eparunelettreαntfaecsdulo`eneste,auxlettrspondentducsroerahuqneeoes deτ(αrnqro`auehalaeuutarruopnonolorpti)t,ainf.Em,ianinlntessoietargercalibre`n, on lit directementωnsur ses feuilles. A
A
A
B
A
B
D
A
B
D
C
B
D
C
C
D
A B D C C D C D C Pour obtenir ce qu’il y a sur les feuilles de profondeurndans l’ordre, on effectue un parcours“en profondeur(ouunparcourspr´exe,commeonveut).Commeilvayavoirnapples,ifil´esrrscu estne´cessairedestockerO(nsiofenuetisivnoemom.C)erilepd´rvuioruop(sopitnoorma)inf chaquenoeud,etquonfaitunnombreconstantdope´rationsparnoeud,lacomplexite´este´tablie. Ilnestpasexcluquilsoitpossibledefaire¸caenespaceO(lognqu´e.)uscomplialalpriiam,ac¸s
Solution de l’exercice 3 n 1.Enfait,ilestsusantdeˆtrecapabledecalculer|τ(α)|ur¸cs.Poa,onlnsitiedrrtuesleleeolpivud observe qu’on a : X n n1 |τ(α)|=|τ(αi)|avecα1, . . . , α`=τ(α) i X n1 =z[α, β]∙ |τ(β)| β∈A
  i ou`z[α, βigeslenembnodreecesdrreno´cdc]uβdansτ(α). Si on pose le vecteurui=|τ(α)|, α∈A et qu’on voitzcomme une matrice, alors on a en fait :ui+1=zui, et donc en faitun= n n zu0. Calculer la puissance de matricezpeut se faire enO(logn) produits matrice-matrice avec
3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.