Cette publication est accessible gratuitement
Télécharger
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