[PDF] corrigé sujet dinformatique de polytechnique MP/PC 2008

View - Download corrigé sujet dinformatique de polytechnique MP/PC 2008

Previous PDF

Next PDF

(PSI )Epreuve d'informatique de l'X - 2008 - MP/PC

Codage de Cesar

Question 1: le codage demaitrecorbeauavec un decalage de 5 donne le message code : hvdomzxjmwzvp. Question 2: ligne 4, on remplit le tableau representant le texte code avec les lettresdu texte initial (represente par un tableau d'entiers) decales dedvers la gauche, ce qui se fait modulo le nombre de lettres dans l'alphabet soit 26.

1defcodageCesar (t , n, d):

2tt = [ ]

3foriinrange (n) :

4tt . append (( t [ i ] + 26d)%26)

5returntt

Question 3: m^eme principe que dans la fonction precedente sauf que l'on eectue le decalage dans l'autre sens.

1defdecodageCesar (t ,n,d):

2tt = [ ]

3foriinrange (n):

4tt . append (( t [ i ] + d)%26)

5returntt

On aurait aussi pu utiliser la fonction precedente en eectuant un decalage dans l'autre sens de la maniere suivante :

1defdecodageCesar (t ,n,d):

2return( codageCesar (t ,n,(26d)))Question 4: On commence par creer et initialiser le tableau des frequences

(lignes 2-4) puis on parcourt le tableau representant le texte.

A la lecture

de lai-eme lettre du texte, on incremente la case correspondante dans le tableau des frequences (lignes 5-7).

1deffrequences ( tt ,n):

2freq = [ ]

3foriinrange (26):

4freq . append(0)

5foriinrange (n) :

6lettre = tt [ i ]

7freq [ lettre ] += 1

8returnfreq

Question 5: dansdecodageAuto, on commence par recuperer le tableau des frequences des apparitions des lettres dans le texte code (ligne 2). On parcourt le tableau des frequences pour reperer la frequence d'apparition maximale ainsi que l'indice du tableau correspondant (ligne 7-10). On cal- cule la cle (ligne 11) en prenant en compte le fait que `e` est la cinquieme lettre de l'alphabet et enn on decode le texte (ligne 12).

1defdecodageAuto( tt ,n):

2freq = frequences ( tt ,n)

3codee = 4

4cle = 0

5maxi = freq [0]

6imaxi = 0

7foriinrange (26):

8ifmaxi<= freq [ i ] :

9imaxi = i

10maxi = freq [ i ]

11cle = (30imaxi)%26

12returndecodageCesar ( tt ,n, cle )

Question 6: Le codage du texte "becunfromage" en utilisant la cle de codage "jean" est "kichwjrbvegr". 1/ 3 Question 7: M^eme principe que pour le codage de Cesar sauf que le decalage depend de la position de la lettre du texte a coder moduloket s'obtient a partir des lettres de la cle. Le decalage pour lai-eme lettre du texte a coder est egal ac[imodk] (le decalage se fait cette fois-ci vers la droite).

1defcodageVigenere (t ,n, c ,k ):

2res = [ ]

3foriinrange (n):

4res . append (( t [ i ]+c [ i%k])%26)

5returnres

Question 8: On programme un classique calcul de pgcd en utilisant les proprietes suivantes (les nombres sont supposes positifs) : pgcd(0;b) =b,pgcd(a;0) =a, etpgcd(a;b) =pgcd(a;ba) sia6b pgcd(ab;b) sia > b.

1defpgcd(a ,b):

2whilea != 0andb != 0:

3ifa<= b:

4b = ba

5else:

6a = ab

7returnmax(a ,b)

Question 9: On memorise la repetition des trois lettreshtt[i];tt[i+1];tt[i+

2]idu texte code dans les variablest0; t1; t2 (ligne 4-6), puis on fait une

boucle pour regarder si la sequencehtt[j];tt[j+1];tt[j+2]iconcide avec la sequence de depart pourjvariant dei+3 an4. Si c'est le cas, on modie la variablePGCDqui contiendra le resultat nal. On y metpgcd(PGCD; ji) (ligne 12). On utilise la proprietepgcd(a1;:::;ap) =pgcd(pgcd(a1;:::;ap1);ap) et la proprietepgcd(0;a) =a.1defpgcdDesDistancesEntreRepetitions ( tt ,n, i ):

2a = 0

3t0 = tt [ i ]

4t1 = tt [ i +1]

5t2 = tt [ i +2]

6forjinxrange ( i +3,n4):

7iftt [ j]==t0andtt [ j+1]==t1andtt [ j+2]==t2 :

8ecart = ji

9ifa == 0:

10a = ecart

11else:

12a = pgcd(a , ecart )

13returna

Question 10: Dans cette fonction, on essaye de trouver la longueur de la cle. Pour cela, on calcule les distances de repetition dehtt[i];tt[i+1];tt[i+2]i pourivariant de 0 an7. Comme on a suppose que toute repetition d'une sequence de 3 lettres dans le texte codet0provient exclusivement d'une sequence de 3 lettres repetee du texte originalt, ces distances seront toutes des multiples de la longueur de la cle. On retourne donc lepgcdde toutes les distances non nulles pour obtenir le plus petit multiple possible dek(on espere trouver ainsi la longueur exacte de la cle avec ce procede).

1deflongueurDeLaCle( tt ,n):

2res = 0

3i = 0

4whileres == 0andi

5res = pgcdDesDistancesEntreRepetitions ( tt ,n, i )

6i += 1

7returnres

2/ 3 Question 11: Dans la fonctionlongueurDeLaCle, on a au plusn6 appels a la fonctionpgcd. Mais il ne faut pas oublier que la fonction pgcdDesDistancesEntreRepetitionsfait aussi appel a la fonctionpgcd et que le nombre de ces appels est majore parni. On peut donc majorer le nombre total d'appels a la fonctionpgcdpar n+nX i=1ni=n+n(n+ 1)2 ce qui nous donne une complexite quadratique (enO(n2)). Question 12: Une fois que l'on akla longueur de la cle, on peut retrou- ver chacune des lettres de la cle en appliquant la methode d'analyse des frequences aux mots construits a partir du mot code en prenant une lettre surk. Pour le mot codeht00;:::;t0n1iet 06j < k, on fait une analyse en frequence sur le motht0j;t0j+k;:::;t0j+m:ki, oum=b((n1)j)k c. Cela nous permet de trouver laj-eme lettre de la cle de la m^eme facon que dans la fonctiondecodageAutode la question 5, a ceci pres que les decalages se font vers la droite pour le codage de Vigenere et vers la gauche pour le codage de Cesar. Question 13: En fait, on va creer la cle de decodage plut^ot que la cle de codage pour pouvoir reutiliser la fonctioncodageVigenere. On commence par recuperer la longueurkde la cle que l'on obtient gr^ace a la fonction longueurDeLaCle(ligne 2). Pour trouver laj-eme lettre de la cle, on fait une analyse en frequence du sous mot obtenu a partir du texte code en par- tant de laj-eme lettre et en ne gardant qu'une lettre surk(ligne 7-9). Une fois que l'on a le tableau des frequences du sous mot, on le parcourt pour trouver la frequence maximale qui correspondra normalement au codage de la lettre `e` (lignes 12-15). On peut ainsi reconstituer laj-eme lettre de la cle de decodage (ligne 16). Une fois que l'on dispose de la cle de decodage, il ne reste plus qu'a decoder le texte (ligne 17).1defdecodageVigenereAuto ( tt ,n):

2k = longueurDeLaCle( tt ,n)

3cle = [ ]

4forjinrange (k ):

5m = (n1j )/k

6sousMot = [ ]

7forlinrange (m+1):

8sousMot . append( tt [ j+lk ])

9freq = frequences (sousMot ,(m+1))

10maxi = 0

11imaxi = 0

12foriinrange (26):

13ifmaxi<= freq [ i ] :

14maxi = freq [ i ]

15imaxi = i

16cle . append((26(imaxi4))%26)

17returncodageVigenere ( tt ,n, cle ,k)

3/

3E. Le Nagard- XMPPC2008cor_p ython(comp osea vecL ATEX le 5/11/2012)

quotesdbs_dbs12.pdfusesText_18

[PDF] sujet pour bac 2019

[PDF] sujet pour crpe

[PDF] sujet probable bts 2019

[PDF] sujet pse cap 2019

[PDF] sujet qcm ira 2020

[PDF] sujet question

[PDF] sujet qui

[PDF] sujet qui change de couleur avec le temps

[PDF] sujet qui fache

[PDF] sujet qui font râler les français 94

[PDF] sujet qui fuite bac 2018

[PDF] sujet qui fuite bac 2019

[PDF] sujet qui revient régulièrement

[PDF] sujet qui revient souvent

[PDF] sujet qui risquent de tomber au bac 2019