[PDF] CCP 2018 - Option informatique Un corrigé I. Logique et calcul des

View - Download CCP 2018 - Option informatique Un corrigé I. Logique et calcul des

Previous PDF

Next PDF

CCP 2018 - Option informatique

Un corrige

I. Logique et calcul des propositions

I.1 Premiere epreuve

Q.1B1=P1_P2.

Q.2B2=P

1. Q.3On noteFla proposition resultant de la regle du jeu (et qui est donc vraie).

F= (B1^B2)_(B

1^B 2) ((P1_P2)^P 1)_(P 1^P 2^P1) (P1^P

1)_(P2^P

1) P2^P 1

Q.4Il faut donc choisir la bo^te 2.

I.2 Deuxieme epreuve

Q.5B1=P

1_P2etB2=P1.

Q.6On a cette fois

F((P

1_P2)^P1)_(P1^P

2^P1) (P

1^P1)_(P2^P1)_(P1^P

2)

P1^(P2_P

2) P1 Il y a une cle dans la bo^te 1 et les deux armations sont donc vraies. Avec la premiere on en deduit qu'il y a aussi une cle verte dans la bote 2.

On peut ainsi choisir n'importe quelle bo^te.

I.3 Troisieme epreuve

La facon dont cette partie est traitee est etrange. J'essaye ici de repondre aux question posees dans

l'esprit (?) du sujet mais on peut faire plus simple. Q.7Pour traduire les inscription, on ne peut a priori se contenter des variablesPides parties precedentes (ou alors il faudrait travailler avec une logique prenant trois valeurs de verite).

Je propose de noter

|Pila variable valant vrai ssi la cle verte est dans la bo^tei |Rila variable valant vrai ssi la cle rouge est dans la bo^tei On a alors, en notantBil'inscription de la bo^tei, B 1=P 3^R

3; B2=R1; B3=P

3^R 3 (on traduit la vacuite par l'absence de cle verte et de cle rouge). Q.8On sait deja qu'il y a exactement une bo^te avec cle verte et une bo^te avec cle rouge (et donc une boite vide). Ce renseignement peut se traduire par (P1^P 2^P 3)_(P

1^P2^P

3)_(P 1^P

2^P3) (F1)

1 en conjonction avec (R1^R 2^R 3)_(R

1^R2^R

3)_(R 1^R

2^R3) (F2)

On sait aussi qu'il ne peut y avoir deux cles dans la m^eme bo^te, ce qui se traduit parP

1^R1^P

2^R2^P

3^R3(F3)

Par ailleurs, l'inscription de la bo^teiest vraie ssiRiest faux. On a donc aussi les trois formules (Ri^B i)_(R i^Bi).

On peut noter que

|R

3^B3=R

3^P 3^R 3R 3^P

3etR3^B

3R3^(P3_R3)R3et donc

(R

3^B3)_(P

3^R 3)(R 3^P

3)_R3P

3_R3 | de maniere similaire, on a (R

2^B2)_(P

2^R

2)(R1_R2)^(R

2_R 1)

On ajoute donc les trois formules

(R 1^P 3_R

3)_(R1^(P3_R3)) (F4)

(R1_R2)^(R 2_R

1) (F5)P

3_R3(F6)

Les indications de l'animateur se traduisent par la veracite deF1^F2^F3^F4^F5^F6. Q.9Supposons, par l'absurde, que la cle verte soit dans la bo^te 2. Ainsi,P2= 1 etR2= 0. (F5) indique queR1= 1 et la cle rouge est dans la bo^te 1. La bo^te 3 est alors vide (car une bo^te de chaque nature) et l'inscription de la bo^te 1 est vraie ce qui contredit la regle (la bo^te contenant la cle rouge a une inscription fausse).

Q.10La cle verte ne peut ^etre dans la bo^te 3 (sinon l'inscription est juste et la bo^te est vide). On

vient de voir qu'elle n'est pas dans la bo^te 2 et donc

La cle verte est dans la bo^te 1

L'inscription de la bo^te 1 est donc vraie et

La bo^te 3 est vide

On en deduit que

La cle rouge est dans la bo^te 2

II. Automates

II.1 Denitions

Q.11On a

a

1L=fb;abg

Q.12On a trois proprietes a prouver.

- Re exivite: siu2, on au1L=u1Let doncuLu. - Symetrie: siu;v2verientuLv, on au1L=v1Let doncv1L=u1Li.e. vLu. - Transitivite: soientu;v;w2tels queuLvetvLw. Alorsu1L=v1L=w1Let doncuLw. 2

Lest une relation d'equivalence sur

SupposonsuLv, c'est a direu1L=v1L.

- Soitx2(uw)1L. On auwx2Let doncwx2u1L=v1Let doncvwx2Lce qui donne x2(vw)1L. - De maniere symetrique, six2(vw)1Lalorsx2(uw)1L.

Ainsi, (uw)1L= (vw)1LetuwLvw.

Lest compatible avec la concatenation a droite

Q.13(i) 2b1L(carb2L) mais =2(ab)1L(carab =2L). Ainsi b6Lab (ii)a2(aba)1L(carabaa2L) maisa =2(bab)1L(carbaba =2L). Ainsi aba6Lbab (iii) Siu2(abbaba)1Lalorsjabbabauja= 0[3] et doncjuja= 0[3] et doncjaaauja= 0[3] et doncu2(aaa)1L. La reciproque est identique et abbabaLaaa Q.14Letant regulier, il est reconnu par un automateA= (Q;;q0;F;).

Considerons l'application'denie deQdansQLpar

'(q) =q1L Soitu2etq=(q0;u). D'apres la propriete admise par l'enonce,'(q) =q1L=u1L. L'application'est donc surjective. Comme l'ensemble de depart est ni, il en est de m^eme de l'ensemble d'arrivee (qui a m^eme un cardinal inferieur ou egal). Ainsi,QLest ni.

II.2 Construction de l'automate minimal

Q.15Sip2Fetq2QnFalors distinguepetq. Il faut donc distinguer (p;q). Notons qu'u vu de l'avant derniere ligne de l'algorithme, il semblerait coherent d'ajouter aussi (q;p) a l'ensemble N 0. Q.16Soitj1. SupposonsNj6=;. Il existe alorsp;q2Qetu2de longueurjtels que (p;u)2Fet(q;u)=2F. Commej1,us'ecritavavecv2de longueurj1 et a2. Posonsp0=(p;a) etq0=(q;a). On a alors(p0;v) =(q0;v) etvdistinguep0etq0. Par ailleurs, siw2est de longueurj2 alorsawne distingue paspetq(car (p;q)2Nj). Or,(p0;w) =(p;aw) et(q0;w) =(q;aw) et doncwne distigue pasp0etq0.

Ainsi, (p0;q0)2Nj1etNj16=;. En contraposant, on a

N j1=; )Nj=; ce qui donne le resultat demande (par recurrence immediate, siNi=;alors8k0; Ni+k=;). Q.17 4 1 2 3 5 6 a- b? a- b- aZZZZZZZ} a? bs bk bI a b a 3

Q.18- Fin de l'initialisation123456

100
20000
300
400
50000
600
- Fin de l'etape 1

123456

10101
20000
31010
40101
50000
61010
- Fin de l'etape 2

123456

10101
20000
31010
40101
50000
61010
Il n'y a pas eu d'evolution a l'etape 2 et il n'y en aura plus. Les classes d'equivalences regroupent les sommets qui ne pourront ^etre distingues. Il y en a trois qui sont f1;4g;f2;5g;f3;6g Q.19On obtient un automate a trois etats (l'etat initial et les etats naux ne sont pas demandes). 1;4- 2;5 3;6 R a} aI b~ b b a

III. Algorithmique et programmation

III.1 Transformation de Burrows-Wheeler (BWT)

Q.20turlututuj

jturlututu ujturlutut tujturlutu utujturlut tutujturlu ututujturl lututujtur rlututujtu urlututujt 4 Q.21On nous demande une fonction recursive. Il faut donc se demander comment permuter a droite un motx::qsachant permuter a droiteq. Supposons queq= [q1;:::;qn]. La permutation a droite deqest [qn;q1;:::;qn1]. Celle dex::qest alors [qn;x;q1;:::;qn1]. On cherche donc le permute a droite deqa partir duquel on construit celui dex::qen intercalantxjuste apres la t^ete du permute deq. Ceci n'est possible que siqest au moins de taille 2 et donc si le mot initial est de taille au moins 3. Notons que le cas d'un mot argument de taille1 est un peu douteux (on ne peut rien decaler). let rec circulaire mu = match mu with |[a] -> [a] |[a;b] -> [b;a] |x::q -> let mot = circulaire q in (List.hd mot)::x::(List.tl mot);; Ceci etant, il m'aurait semble plus naturel d'ecrire une fonction auxilaire recursivedernier : 'a list!'a*'a listtelle que dans l'appeldernier l, on supposelnon vide et on renvoie le couple forme de la derniere lettre du mot et du mot ampute de cette derniere lettre. let rec dernier l = match l with |[x] -> (x,[]) |x::q -> let (y,u)=dernier q in (y,x::u);; La fonction demande s'en deduit (en supposant le mot argument non vide). let circulaire mu= let (y,u)=dernier mu in y::u;; Q.22Ici, on ne demande plus une fonction recursive et on pourrait iterer en utilisant des references de listes. Par ailleurs, on n'impose a priori pas d'ordre pour la liste resultat mais il semble plus naturel d'obtenir celle qui etait demandee plus haut (decalages successifs a droite). Je choisit d'ecrire une fonction recursive auxilaireconstruit : int!'a list!'a list list. Dans l'appelconstruit k mot, on renvoie la liste de taillekcontenantmotet lesk-1 decalages suivants de ce ce mot. let matrice_mot mu = let rec construit k mot = if k=0 then [] else mot::(construit (k-1) (circulaire mot)) in construit (List.length mu) mu;;

Q.23La matriceM0est la suivantejturlututu

lututujtur rlututujtu tujturlutu turlututuj tutujturlu ujturlutut urlututujt utujturlut ututujturl 5 et on a P=0 B

BBBBBBBBBBBBB@0 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0

0 0 0 0 0 1 0 0 0 0

0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 1

0 0 0 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0 0 01

C

CCCCCCCCCCCCCA

Q.24Une fonctioninsere : 'a!'a listprend en argument un element, une liste triee par ordre croissant et renvoie la liste triee obtenue en ajoutant l'element a la liste.

La fonction principale s'en deduit.

let rec insere x l = match l with |[] -> [x] |y::q -> if x<=y then x::l else y::(insere x q);; let rec tri l = match l with |x::q -> insere x (tri q);;

Q.25Il sut de trier la matriceMdes mots permutes.

let matrice_mot_triee mu = tri (matrice_mot mu) ;; Notons qu'il peut y avoir un doute : Ocaml sait-il comparer deux listes de caracteres et si oui, est-ce pour l'ordre lexicographique? La reponse est OUI. On peut cependant ecrire une fonction compare : 'a list!'a list!booltel quecompare mot1 mot2indique si le premier argument est inferieur au second. Il sut alors, dansinsere, de remplacerx<=yparcompare x y. let rec compare mot1 mot2 = match (mot1,mot2) with |[],_ -> true |_,[] -> false |x1::q1,x2::q2 -> (x1 failwith "erreur" |[x] -> x |x::q -> last q ;; Il sut alors de creer la matriceM0et de recuperer les dernieres lettres. On ecrit pour cela une fonctionparcours : 'a list list!'a listrenvoyant le mot correspondant a la derniere colonne de l'argument. On suppose ici que l'argument donne acodageBWTest le mot ^(c'est a dire que le symboleja deja ete ajoute). let codageBWT mu = let rec parcours mat = match mat with |mot::q ->(last mot)::(parcours q) in parcours (matrice_mot_triee mu);; D'apres la question 23, dans le cadre de l'exemple, le codage est uruujutttl Q.29`=BWT() contient exactement les m^emes lettres que ^(par construction deM0ou chaque lettre de ^se retrouve une fois en derniere position d'une ligne). Notonsmla version triee de`. CommeM0est triee par ordre lexicographique,mcorrespond alors exactement a la premiere colonne deM0(puisque dans cet ordre, on prend d'abord en compte la premiere lettre). Dans le cadre de l'exemple, la premiere colonne sera jadeegnnv Q.30Comme indique par l'enonce, les sous-mots de taille 2 de ^sont alors ej;da;nd;ge;ve;ng;en;an;jv Pour obtenir la colonne suivante, on ordonne cette liste de mots de taille 2 jv;an;da;ej;en;ge;nd;ng;ve A nouveau, par denition deM0, on obtient la les deux premieres colonnes deM0. En particulier, la seconde colonne est vnajnedge Q.31De facon generale, on suppose connues lesn1 premiere colonnes. En ajoutant DEVANT la derniere colonne, on obtient tous les facteurs de taillen. On ordonne ces facteurs de taillenet on obtient alors lesnpremieres colonnes deM0(et donc lan-ieme). Q.32L'algorithme est donc le suivant. On prend en argument le mot`=BWT() que l'on suppose de taillek. On initialise une listemde taillekcomposee de mots tous vides.

1. Ajouter devant chaque mot demla lettre correspondante de`(ceci modiemen ajoutant

une lettre a chaque mot).

2. Trierm(i.e. remplacermpar sa version triee)

3. retourner au point 1 si les elements demsont de taillek

4. Renvoyer la ligne demse terminant parj.

Q.33En appliquant l'algorithme, on obtient la liste de listes suivante 7 [['|'; 'v'; 'e'; 'n'; 'd'; 'a'; 'n'; 'g'; 'e']; ['a'; 'n'; 'g'; 'e'; '|'; 'v'; 'e'; 'n'; 'd']; ['d'; 'a'; 'n'; 'g'; 'e'; '|'; 'v'; 'e'; 'n']; ['e'; '|'; 'v'; 'e'; 'n'; 'd'; 'a'; 'n'; 'g']; ['e'; 'n'; 'd'; 'a'; 'n'; 'g'; 'e'; '|'; 'v']; ['g'; 'e'; '|'; 'v'; 'e'; 'n'; 'd'; 'a'; 'n']; ['n'; 'd'; 'a'; 'n'; 'g'; 'e'; '|'; 'v'; 'e']; ['n'; 'g'; 'e'; '|'; 'v'; 'e'; 'n'; 'd'; 'a']; ['v'; 'e'; 'n'; 'd'; 'a'; 'n'; 'g'; 'e'; '|']]

Le mot decode est donc

vendange III.2 Codage par plages RLE (Informatique pour tous) Q.34Le resultat d'un codage RLE est naturellement une liste de tuples de taille 2 (des couples).

Q.35On gere trois variables.

resest la liste code en construction a laquelle on ajoute des couples au fur et a mesure. carest le caractere composant le bloc en cours de lecture. tailleest la taille du bloc en cours de lecture. Initialement, on detecte un debut de bloc de taille 1 compose du caractere numero 0 du mot. On parcourt le mot en incrementanttaillesi le caractere rencontre complete le bloc ou en ajoutant un bloc aressinon (en redemarrant un nouveau bloc). En n de parcours, il reste a ajouter le couple correspondant au dernier bloc detecte. def RLE(mot): res=[] car=mot[0] taille=1 for i in range(1,len(mot)): if mot[i]==car: taille=taille+1 else: res.append((taille,car)) car=mot[i] taille=1 res.append((taille,car)) return res Q.36On gere une variablemotcorrespondant au mot decode que l'on construit. Pour chaque couple (taille,car)du mot code, on ajoute a la variablemotun nombretaillede carcaterescar. def decodeRLE(codeRLE): mot=[] for i in range(len(codeRLE)): (taille,car)=codeRLE[i] for j in range(taille): mot.append(car) return mot 8

III.3 Codage de Human (Informatique pour tous)

Q.37Initialement, on a (on identie une feuille et son etiquette qui est un couple)

L= [(l;1);(r;1);(t;3);(u;4)] etA= []

A la premiere etape, on utilise les deux premiers arbres dansLque l'on fusionne pour obtenir un arbre place dansA. Ainsi, en notantN(n,g,d) un noeud interne de poidsnet de lsgetd,

L= [(t;3);(u;4)] etA= [N(2;(l;1);(r;1))]

A l'etape suivante, on selectionne les premiers elements des deux listes. On les fusionne et on ajoute le resultat dansA. On obtient

L= [(u;4)] etA= [t]

outest l'arbre binaire suivant 5 t,3 2 l,1 r,1 AA A l'etape suivante, on selectionne les premiers elements des deux listes. On les fusionne et on ajoute le resultat dansA. Ce sera le resultat nal 9 u,4 5 t,3 2 l,1 r,1 AA Q QQQQ Q.38Siest un mot ou tous les symboles ont m^eme nombre d'occurrencesp, l'algorithme commence par \vider"Len ajoutant aAdes arbres de hauteur 1 et de poids 2p.Aest alors une le dans laquelle on enleve a chaque etape 2 elements pour en ajouter un. Le processus va donner un arbre equilibre en hauteur et donc touu. 9quotesdbs_dbs28.pdfusesText_34

[PDF] centrale éolienne edf

[PDF] centrale eolienne definition

[PDF] centrale hydrolienne

[PDF] centrale éolienne avantages et inconvénients

[PDF] centrales solaires

[PDF] soultz sous foret géothermie svt

[PDF] géothermie bouillante svt

[PDF] flux géothermique

[PDF] la plante domestiquée

[PDF] centrale hydraulique définition

[PDF] fonctionnement d'un barrage hydroélectrique pdf

[PDF] exposé sur lénergie hydraulique

[PDF] centrale hydraulique avantages et inconvénients

[PDF] symbole schéma hydraulique

[PDF] cours hydraulique industriel pdf