[PDF] Détection de carrés dans les mots

View - Download Détection de carrés dans les mots

Previous PDF

Next PDF

ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2017FILIEREMP{CONCOURS INFO

COMPOSITION D'INFORMATIQUE-MATH

EMATIQUES { (ULCR)

(Duree : 4 heures) L'utilisation des calculatrices n'est pas autorisee pour cette epreuve.

Ce sujet comprend 10 pages numerotees de 1 a 10.

Detection de carres dans les mots

Ce sujet traite de la recherche de repetitions dans un texte. Plus particulierement, on s'interesse aux repetitions appeleescarres. La partie I introduit le probleme de la recherche de repetitions dans un texte et donne un premier algorithme permettant de le resoudre. La partie II est consacree a la construction d'un mot inni sans carre. Enn, les parties III et IV sont consacrees a la mise au point d'un algorithme ecace de detection de carres. Lacomplexite, ou leco^ut, d'un programmePest le nombre d'operations elementaires (addition, soustraction, aectation, test, lecture ou ecriture dans un tableau, etc...) necessaires a l'execution dePdans le cas le pire. Lorsque cette complexite depend d'un ou plusieurs pa- rametresn1;:::;nk, on dira quePa une complexite enO(f(n1;:::;nk)), s'il existe une constanteK >0 telle que, pour toutes les valeurs den1;:::;nksusamment grandes (c'est-a- dire plus grandes qu'un certain seuil), pour toute instance du probleme de parametresn1;:::;nk, la complexite dePest au plusKf(n1;:::;nk). Lorsqu'il est demande de garantir une certaine complexite, le candidat devra justier cette derniere. 1 On considere unalphabet, c'est-a-dire un ensemble ni d'elements appeleslettres. On appelle l'ensemble de tous les mots de longueur nie utilisant les lettres de l'alphabet . La longueurd'un motx, c'est-a-dire le nombre de lettres qui le composent, est noteejxj. Lemot vide, de longueur 0 et note", appartient egalement a . Le mot obtenu parconcatenation de deux motsxety, notexy, a pour longueurjxj+jyjet est compose des lettres dex, suivies des lettres dey. Uncarreest un mot egal axxouxest un mot non vide. On dit qu'un motmcontient un carres'il existe un mot non videxet deux mots (eventuellement vides)yetztels que : m=yxxz On dit alors quexxest uncarre dem. Laperioded'un carrexxest la longueur du motx. Par exemple, le motbonbonest un carre de periode 3, et le motrepetitioncontient le carretiti de periode 2. On choisit de representer les mots par des tableaux de caracteres. Les cases d'un tableau de longueurnsont numerotees de 0 an1. Pour des raisons de coherence entre les notations mathematiques et les representations en machine, on notex0,x1, ...,xjxj1les lettres qui composent le motxde . On a donc pour tout mot non videx: x=x0:::xjxj1 On dit aussi quexiest la lettre qui appara^t a lapositionidu motx. La numerotation des lettres d'un mot permet de parler de laposition a laquelle un carre appara^t dans un

mot. Par exemple, le mottintinnabulerest represente par le tableau decrit ci-dessous.Numero de la case0 1 2 3 4 5 6 7 8 9 10 11 12

Caractere contenu dans la caset i n t i n n a b u l e r On dit que le mot (ou le tableau qui le represente) contient le carretintinde periode 3, a la position 0. En eet, la premiere lettre detintinappara^t a la case 0 du tableau. Le mot contient aussi le carrennde periode 1, a la position 5. Le sujet de ce devoir s'appuie sur le langage informatique Caml Light. Le candidat pourra rediger ses reponses dans ce langage, ou dans un format pseudo-code proche. On rappelle quelques fonctions Caml Light pour manipuler les tableaux. |vectlength mrenvoie le nombre de cases du tableaum. |subvect m x yrenvoie le sous-tableau demconstitue desycases a partir de la casex.

|makevect x yrenvoie un tableau dexcases qui contiennent toutes la valeury.(* Caml *) vectlength:'a vect -> int

(* Caml *) subvect:'a vect -> int -> int -> 'a vect (* Caml *) makevect:int -> 'a -> 'a vect2

Partie I. Existence d'un carre

Question 1On considere le programme suivant :

let carre_pe_pos m p i = let j = ref 0 in while !j < p && i + !j + p < (vect_length m) && m.(i + !j + p) = m.(i + !j) do j := !j + 1 done; !j;;(* Caml *) carrepepos:char vect -> int -> int -> intDonner les valeurs des appels suivants. carre_pe_pos [|`c`; `o`; `u`; `c`; `o`; `u` |] 3 0;; carre_pe_pos [|`c`; `o`; `u`; `c`; `o`; `o` |] 3 0;; carre_pe_pos [|`a`; `b`; `a`; `b`; `a`; `b`; `a`; `b` |] 2 4;; carre_pe_pos [|`a`; `b`; `a`; `b`; `a`; `b`; `a`; `b` |] 2 5;; Question 2On supposep >0 eti0. Denir precisement ce que renvoie la fonction carrepeposen fonction de ses argumentsm,peti. Que signie le fait que la valeur ren- voyee est egale ap?

Question 3

Ecrire une fonctioncarrepequi prend en entree un motmet un entierp >0, et

qui renvoietruesi le motmcontient un carre de periodepetfalsesinon.(* Caml *) carrepe:char vect -> int -> boolQuestion 4

Ecrire une fonctioncarrenaifqui prend en entree un motmet renvoietruesi

le mot contient un carre de longueur quelconque, etfalsesinon.(* Caml *) carrenaif:char vect -> boolQuestion 5Dans cette question, on suppose que pour l'alphabet considere, pour tout entier

`1, il existe des mots de longueurs`sans carre. Donner alors la complexite dans le pire des cas de la fonctioncarrenaifdenie precedemment. 3 Question 6On considere l'alphabet =fa;bg. Montrer que tout mot susamment long contient un carre. Donner un algorithme ecace (s'executant en temps constant) permettant de decider l'existence d'un carre pour les motsmconstruits sur l'alphabet =fa;bg. On pourra supposer ici que la fonctionvectlengths'execute en temps constant.

Partie II. Construction d'un mot inni sans carre

Le but de cette partie est de construire un mot sur un alphabet de quatre lettres, de longueur innie, et sans carre. La notion de carre s'etend naturellement aux mots innis. Un mot inni est une suite de lettres indicees par les entiers deN. Le mot obtenu parconcatenationd'un mot nixet d'un mot inniyest le mot innixycompose des lettres dex, suivies des lettres dey. Dans ce contexte, uncarrereste un mot ni de la formexx, avecxun mot non vide. Un mot innimcontient un carres'il existe un mot ni non videx, un mot niy(eventuellement vide) et un mot inniztels quem=yxxz. Unbitest un nombre entier egal a 0 ou 1. Soit (bi)i2Nune suite de bits tous nuls a partir d'un certain rang (c'est-a-dire qu'il existeNtel que pour toutiN,bi= 0). On dit que (bi)i2Nest larepresentation binaired'un nombre entier naturelnsi n=+1X i=0b i2i: On rappelle que tout nombre entier naturel possede une unique representation binaire. On rappelle qu'en pratique, pour donner la representation binaire d'un nombre entier dont les bits sont tous nuls a partir du rangN, on ecrit simplementbN1bN2:::b0. Soitnun nombre entier naturel et (bi)i2Nsa representation binaire. On notep(n) laprofon- deurden, a savoir le plus petit entieritel quebi= 0. On notec(n) =bp(n)+1, le (p(n) + 1)-eme bit de la representation binaire den. On etudie le mot inniMsur l'alphabetf0;1gdeni par

M=c(0)c(1)c(2)c(3):::

Question 7Donner les huit premieres lettres deMet verier queMcontient des carres de periode 1 et 3. Question 8Soientd0 etk1 deux nombres entiers. On deniti(d;k) comme l'unique nombre entier de l'ensemblefd;d+1;:::;d+2k1gegal a 2k11 modulo 2k. Soitnun nombre entier naturel. En comparant les representations binaires denet denmodulo 2k, montrer que p(i(d;k)) =k1.

Question 9Montrer que pour tous entiersd0 etk1,

c(i(d;k) + 2k) =c(i(d;k)) + 1 mod 2: Question 10Montrer que le motMne contient aucun carre de periodepavecp= 2ketk1. Question 11Generaliser le raisonnement precedent pour en deduire que le motMne contient aucun carre de periode paire. 4 Question 12Denir un alphabet sur quatre lettres et donner, sur cet alphabet, un mot inni, c'est-a-dire une suite de lettres indicee par les entiers deN, qui ne contient aucun carre. Il existe egalement des mots innis sur trois lettres sans carre, mais leur construction n'est pas demandee dans ce devoir. Dans la suite, on ne considere que des mots nis.

Partie III. Recherche ecace des carres

Nous souhaitons mettre en place un algorithme ecace permettant la recherche de carres dans un mot. Dans cette partie, nous nous interessons a la detection de carres crees lors de la concatenation de deux mots. Il s'en deduit un algorithme de test d'existence d'un carre dans un mot par la strategie \diviser pour regner". A titre d'exemple, considerons les motsu=tinetv=tinnabuler. Le carretintinapparais- sant au debut du motuvest cree lors de la concatenation des motsuetvalors que le carrenn apparaissant dans le motuvn'est pas cree lors de la concatenation deuet dev. Il apparaissait deja dans le motv. Un motyest unprexed'un motxs'il existe un motztel quex=yz. Un motyest un suxed'un motxs'il existe un motztel quex=zy. Noter que le mot vide est prexe et suxe de n'importe quel mot. Pour tous motsuetvsur un alphabet et tout indiceitel que 0i jvj 1, on denit :

1.lms(u;v;i) est la longueur maximum d'un suxe deuqui appara^t dansven se terminant

a la positionidev. Par exemple,lms(lebon;dubonnet;4) = 3 parce que le suxebonde lebon, de longueur 3, appara^t dansdubonnetet se termine a la position 4 dedubonnet.

2.lmp(u;v;i) est la longueur maximum d'un prexe deuqui appara^t dansven commencant

a la positionidev. Par exemple,lmp(pabon;pabonpapa;5) = 2 car le prexepadepabon de longueur 2 appara^t a la position 5 depabonpapa. Question 13On considere =fa;b;cg. Soientu=cabacbabetv=cbacbabcbab. Calculer lms(u;v;i) etlmp(v;v;i) pouricompris entre 0 et 10. Faites bien attention a lire correctement ce qui est demande : pourlms, on demandeuetv, mais pourlmp, on demandevetv. Donner votre reponse en recopiant et completant le tableau suivant.i012345678910 v icbacbabcbab lms(u;v;i)lmp(v;v;i)Soientuetvdeux mots. On appellenouveau carre pour la concatenation deuetv, ou simplementnouveau carrequand il n'y a pas de risque de confusion, tout carre deuvqui est la concatenation d'un suxe non-vide deuet d'un prexe non-vide dev(de maniere plus imagee, le carre est a cheval sur les deux mots, ou est cree par la concatenation deuetv). 5 Un nouveau carrewwqui appara^t en positionisur le motuvest uncarre centre suru lorsquei+jwjjujalors on dit qu'il estcentre surv. Par exemple, avec les motsuetvdenis ci-dessus,cbabcbacbabcbaest un nouveau carre de periode 7 qui appara^t en position 4 sur le motuv. Il est centre surv. On remarquera que sii+jwj=juj, alorswwest un nouveau carre qui n'est centre ni suru, ni surv. Le schema ci-dessous montre le cas general d'un nouveau carre obtenu lors de la concatenation deuet dev, centre surv, de periodepet se terminant a la positionidev. u motwv ip+1::::::::::::vi|{z} motwv i+1:::vjvj1 Question 14Dans l'hypothese ou il existe dansuvun nouveau carrewwcentre surv, de periodepet se terminant a la positionidev, calculer en fonction depl'indicejtel que : v

0:::vip=vj+1:::vi

Que peut-on dire des motsujuj2p+i+1:::ujuj1etvip+1:::vj? Question 15Montrer qu'il existe un carre de periodepdansuvse terminant a la positioni devet centre survsi et seulement si (a)

1 p (b)pi <2p1, et (c)

2 plms(u;v;p1)1ip+lmp(v;v;p)1.

Question 16Donner sans preuve une condition necessaire et susante similaire a celle de la question precedente pour les carres centres suru. On commencera par ecrire le schema montrant le cas general d'un nouveau carre centre suru. Question 17Utiliser les resultats des questions precedentes pour donner les nouveaux carres de periode 7 centres survobtenus lors de la concatenation deu=cabacbabetv=cbacbabcbab. Dans cette partie, on suppose donnee une implementation des fonctionslmsetlmp. En fait, pour des raisons d'ecacite du calcul, on ne dispose pas directement des fonctionslmsetlmp, mais plut^ot des fonctions suivantes :(* Caml *) calcullms:char vect -> char vect -> int vect

(* Caml *) calcullmp:char vect -> char vect -> int vectLa fonctioncalcullmsappliquee auetvrenvoie un tableau d'entiers de taillejvjtel que

l'entier stocke a la positionisoit egal alms(u;v;i) pour 0i Question 18

Ecrire une fonctionnouveaucarrevqui prend en entree deux motsuetvet renvoietruesi le mot obtenu lors de la concatenation deuet devfait appara^tre un nouveau

carre centre surv, etfalsesinon. On garantira une complexite enO(juj+jvj).(* Caml *) nouveaucarrev:char vect -> char vect -> boolOn admettra l'existence d'une fonctionnouveaucarreu(similaire a celle de la question

precedente) de complexiteO(juj+jvj) qui renvoietruesi un nouveau carre centre suruappara^t lors de la concatenation des motsuetv(et renvoiefalsesinon).

Question 19

Ecrire une fonctionnouveaucarrequi prend en entree deux motsuetvet renvoietruesi un nouveau carre appara^t lors de la concatenation des motsuetv, et renvoie falsesinon. On veillera a bien prendre en compte d'eventuels nouveaux carres qui ne sont ni

centres suruni centres surv, et on garantira une complexite enO(juj+jvj).(* Caml *) nouveaucarre:char vect -> char vect -> boolQuestion 20En deduire une fonctioncarrequi renvoietruesi le motmdonne en entree

admet un carre, etfalsesinon. On garantira que le calcul se fait enO(jmj log(jmj)).(* Caml *) carre:char vect -> boolPartie IV. Implementation ecace des fonctionslmsetlmp

On souhaite maintenant implementer ecacement le calcul delms(u;v;i), etlmp(u;v;i). Comme annonce dans la partie precedente, on implemente la fonctioncalcullms(respecti- vementcalcullmp) qui, appliquee auetv, renvoie un tableau d'entiers de taillejvjtel que l'entier stocke dans la caseiest egal alms(u;v;i) (respectivementlmp(u;v;i)) pour 0i 8contrev1,v9contrev2, ...On obtient icipref7= 3. Pour faire ce raisonnement de facon systematique, on introduit, l'indicei2 etant xe, deux valeursgetfqui constituent les elements cles de la methode. Elles satisfont les relations : g=maxfj+prefjj0< j < igf2 fjj0< j < ietj+prefj=gg Question 21Completer la table 1 en indiquant la valeur deget les valeurs possibles defpour chaque indiceicompris entre 2 etjvj 1 = 9. Question 22Soient 1< i gi gi+`sinon ou`est la longueur du plus long prexe commun avgi:::vm1etvg:::vm1. Autrement dit, on a`=lmp(vgi:::vm1;vg:::vm1;0). On poserak=prefifetk0=gi, et on etudiera separement les cask < k0,k > k0, etk=k0. Ces trois cas correspondent aux trois situations illustrees au travers des exemples donnes en debut de cette partie. Question 24On considere le code donne en Figure 1. 8

1. let calcul_pref v =

2. let pref = make_vect (vect_length v) 0 in

3. pref.(0) <- vect_length v;

4. let g = ref 0 in

5. let f = ref 0 in

6. for i = 1 to vect_length v - 1 do

7. if i < !g && pref.(i - !f) < !g - i then

8. pref.(i) <- pref.(i - !f)

9. else

10. if i < !g && pref.(i - !f) > !g - i then

quotesdbs_dbs22.pdfusesText_28

[PDF] Alain-René Lesage - L 'Etudiant

[PDF] Cours de mathématiques Partie III

[PDF] équipement d alarme incendie type 3 - RS

[PDF] systèmes de détection incendie - Chubb securite

[PDF] NOTICE D UTILISATION Type 4 Planète - Cooper

[PDF] Alarme Type 4 sans fil V3 - BSOI 974

[PDF] URA - Alarme incendie Type 4

[PDF] La maintenance des équipements d alarme incendie Type 4 - Sicli

[PDF] réglementation incendie 2009 - Sifrrap

[PDF] KEBIJAKAN UPAH MINIMUM INDONESIA 1 SITUASI

[PDF] PP No 10 Tahun 1983 tentang Izin Perkawinan dan Perceraian

[PDF] détermination de l 'albédo des surfaces enneigées par télédétection

[PDF] Genetica Medica

[PDF] l étranger - Anthropomada

[PDF] antidiabétiques