MPSI831 Lycée Masséna DS 1 : Corrigé
Exercices
Exercice 1
Pour les bases 2 et 3, on procède comme dans le cours, par divisions euclidiennes, jusqu’à obtenir un quotient nul.
541 = 2 × 270 + 1
270 = 2 × 135 + 0
135 = 2 × 67 + 1
67 = 2 × 33 + 1
33 = 2 × 16 + 1
16 = 2 × 8 + 0
8 = 2 × 4 + 0
4 = 2 × 2 + 0
2 = 2 × 1 + 0
1 = 2 × 0 + 1
541 = 3 × 180 + 1
180 = 3 × 60 + 0
60 = 3 × 20 + 0
20 = 3 × 6 + 2
6 = 3 × 2 + 0
2 = 3 × 0 + 2
Il suffit ensuite de lire les restes dans l’ordre inverse. Ainsi, 541 = 1000011101 2 = 202001 3.
Puisque les bases 4, 9 et 16 sont des puissances de 2, il suffit ensuite de grouper les paquets de chiffres correspondants en commençant par la droite, suivant la transcription suivante :
hexadécimal
0
1
2
3
4
5
6
7
base 4
0
1
2
3
10
11
12
13
binaire
0000
0001
0010
0011
0100
0101
0110
0111
hexadécimal
8
9
A
B
C
D
E
F
base 4
20
21
22
23
30
31
32
33
binaire
1000
1001
1010
1011
1100
1101
1110
1111
Ainsi, 541 = 20131 4 = 21D16 = 661 9.
base 3
0
1
2
base 9
0
1
2
base 3
10
11
12
base 9
3
4
5
base 3
20
21
22
base 9
6
7
8
Exercice 2
L’algorithme de Hörner revient à évaluer l’expression 1 + 3 × (0 + 3 × (1 + 3 × (2 + 3 × 1))). Allons-y joyeusement :
N = 1 + 3 × (0 + 3 × (1 + 3 × (2 + 3 × 1)))
= 1 + 3 × (0 + 3 × (1 + 3 × 5))
= 1 + 3 × (0 + 3 × 16)
= 1 + 3 × 48
N = 145
Exercice 3
1. Comme les puissances de 2 nous sont données ici, il suffit de les sommer. Sur entiers naturels, N = 128 + 32 + 16 + 4 = 180 et M = 64 + 32 + 8 + 1 = 105.
2. L’interprétation en représentation en complément à 2 de M est identique à celle sur entiers naturels car son premier chiffre est 0. En revanche pour N, le premier chiffre correspond à −128 au lieu de 128. Il faut donc soustraire 256 à son interprétation sur entiers naturels pour obtenir celle sur entiers relatifs :
Sur entiers relatifs, N = 180 − 256 = −76 et M = 105.
3. Effectuons l’addition comme dans le cours :
11 01 1 1 0 1 0 0
+ 0 1 1 0 1 0 0 1
1
0 0 0 1 1 1 0 1
Il y a dépassement de capacité sur entiers naturels, mais pas sur entiers relatifs : en effet le résultat de l’addition sur entiers naturels est 285 > 28 − 1 = 255, mais sur entiers relatifs on reste bien dans l’intervalle [[−128, 127]] (ce qui est toujours le cas lorsque l’on additionne deux nombres représentables de signes opposés).
Exercice 4
Le problème se trouve dans le while : dû aux erreurs d’arrondis, la condition x!=3.1 est toujours vérifiée et la boucle ne termine jamais. On pourrait la remplacer par x < 3.1, au risque d’avoir un point en plus si x est légèrement en dessous de 3.1 à l’avant dernière itération (même si ici, ce n’est pas le cas). Ainsi, une condition comme x < 3.05 est préférable. On peut aussi travailler avec des entiers plutôt qu’avec des flottants :
while x!=31:
abscisses.append(x/10)
ordonnees.append(x*x/100)
x+=1
Enfin, comme on sait que l’on a besoin de 31 points exactement, la boucle while peut avantageusement être remplacée par une boucle for : on ne risque pas d’écrire une boucle infinie !
Problème : Ave Cesar (Zud Bdrzq)
Question 1
Pour coder le texte informatique, on le transforme d’abord en tableau de chiffres, on retranche 5 à tous les chiffres (modulo 26), et on transforme le résultat en lettres :
Texte de départ
i
n
f
o
r
m
a
t
i
q
u
e
Chiffres
8
13
5
14
17
12
0
19
8
16
20
4
Chiffres décalés de 5 (modulo 26)
3
8
0
9
12
7
21
14
3
11
15
25
Texte chiffré
d
i
a
j
m
h
v
o
d
l
p
z
On obtient donc le texte : diajmhvodlpz.
Question 2
Plusieurs solutions sont possibles ici. On en donne trois.
def chiffrementCesar(t,d): return([(x-d)%26 for x in t])
def chiffrementCesar(t,d): u=[0]*len(t)
for i in range(len(t)): u[i]=(t[i]-d)%26
return(u)
def chiffrementCesar(t,d): u=[]
for i in range(len(t)): u.append((t[i]-d)%26)
return(u)
Question 3
On pourrait donner une réponse similaire à celle de la question précédente, mais le plus simple reste certainement d’utiliser la fonction chiffrementCesar !
def dechiffrementCesar(t,d):
return(chiffrementCesar(t,-d))
Question 4
Il suffit de créer un tableau de taille 26, et de parcourir le tableau t en incrémentant le tableau des fréquences en fonction des éléments de t. On montre ici deux solutions. Dans la première, on parcourt les indices du tableau t, et dans la seconde on parcourt directement les éléments de t.
def frequences(t):
F=[0]*26
for i in range(len(t)): F[t[i]]+=1
return(F)
def frequences(t): F=[0]*26
for x in t:
F[x]+=1
return(F)
Question 5
Pas de difficulté ici : on stocke dans une variable l’indice du maximum temporaire, et on parcourt le tableau en comparant chaque élément avec l’élément correspondant au maximum temporaire. Pour l’initialisation, on considère que l’indice est 0.
def indice_max(T):
imax,vmax=0,T[0] #indice du maximum et maximum (temporaires)
for i in range(1,len(T)): #pas besoin de considérer l'indice 0.
if T[i]>vmax:
imax,vmax=i,T[i] #dans ce cas on remplace imax et vmax par i et T[i].
return(imax)
Question 6
On utilise la fonction frequences pour calculer le tableau des fréquences, on repère l’indice imax de l’élément maximal du tableau des fréquences à l’aide de la fonction précédente, qu’on associe à la lettre e. Comme e est associé au chiffre 4, cela signifie que le décalage vaut (4-imax)%26. Il suffit ensuite d’utiliser la fonction dechiffrementCesar.
def dechiffrementAuto(t):
F=frequences(t)
imax=indice_max(F)
return(dechiffrementCesar(t,(4-imax)%26))
Question 7
On procède comme en question 1, en utilisant cette fois ci le décalage variable fournit par le texte nice.
Texte de départ
p
r
o
m
e
n
a
d
e
Chiffres
15
17
14
12
4
13
0
3
4
Clé
n
i
c
e
n
i
c
e
n
Chiffres de la clé
13
8
2
4
13
8
2
4
13
Addition modulo 26
2
25
16
16
17
21
2
7
17
Texte chiffré
c
z
q
q
r
v
c
h
r
On obtient donc : czqqrvchr.
Question 8
Pour trouver le décalage associé au chiffre d’indice i de t, il suffit de considérer l’élément d’indice i%c de la clé.
def chiffrementVigenere(t,c):
taille_cle=len(c)
u=[0]*len(t)
for i in range(len(t)):
u[i]=(t[i]+c[i%taille_cle])%26
return(u)
Question 9
Pour cette question, on parcourt les indices du tableau t depuis l’indice i+5, jusqu’à l’indice n-5, où n est la taille du tableau t. Si on trouve un indice j tel que les séquences t[i:i+5] et [j:j+5] coïncident, cela signifie que j-i est une distance de répétition. On maintient un PGCD p des distances entre répétitions (initialisé à 0), que l’on recalcule à chaque nouvelle répétition trouvée. Si on ne trouve pas de répétition, ce PGCD reste à zéro, ce qui est bien le comportement voulu. Notez aussi que si n − 5 ≤ i + 5, on ne rentre pas dans la boucle for.
def pgcdDesDistancesEntreRepetitions(t,i):
p=0
n=len(t)
for j in range(i+5,n-5):
if t[i:i+5]==t[j:j+5]:
p=PGCD(p,j-i)
return(p)
Question 10
Il suffit ici d’utiliser la question précédente, en faisant varier i sur tous les indices du tableau et en prenant le PGCD à chaque étape. Notez que calculer PGCD(a,b) avec l’un des deux entiers (ou les deux) égal à 0 ne pose pas de problème : on peut donc appeler pgcdDesDistancesEntreRepetitions(t,i) avec i prenant toutes les valeurs entre 0 et len(t)-1 sans se poser de questions.
def longueurDeLaClef(t):
p=0
for i in range(len(t)):
p=PGCD(p,pgcdDesDistancesEntreRepetitions(t,i))
return(p)
Question 11
On procède de la même manière qu’avec le déchiffrement de César, mis à part que l’on rajoute une boucle externe variant entre 0 et k-1, et que l’on fait en quelque sorte k déchiffrements de César.
def dechiffrementVigenere(t,k): #k=longueur de la clef
n=len(t)
u=[0]*n
for i in range(k):
F=[0]*26
for j in range(i,n,k):
F[t[j]]+=1
imax=indice_max(F)
for j in range(i,n,k):
u[j]=(t[j]+4-imax)%26
return(u)
Question 12
Cette question n’est qu’une formalité : on calcule la longueur de la clé, puis on déchiffre.
def dechiffrementAutoVigenere(t):
k=longueurDeLaClef(t)
return(dechiffrementVigenere(t,k))
En pratique, le déchiffrement fonctionne plutôt bien, vous pouvez essayer chez vous : récupérez sur le site web le fichier Python associé au corrigé, il y a quelques exemples dedans. N’hésitez pas à faire varier la taille de la clé. Il se peut cependant que dans certaines sous-séquences, le « e » ne soit plus majoritaire. En fait, la méthode de chercher la lettre majoritaire pour lui faire correspondre le « e » (dans le déchiffrement des chiffrements de César ou de Vigenère) n’est pas la méthode la plus fiable. Il vaut mieux procéder par analyse fréquentielle : chercher le décalage qui rapproche le plus de la fréquence usuelle des lettres en français. On cherche pour cela à minimiser P25
i=0(ffrançais
i − ftexte
ffrançais
iet ftexte
i+d)2, où
isont les fréquences d’apparition de la lettre i en français et dans le texte crypté (le i + d étant pris modulo 26). Tout cela s’étend bien sûr aux textes comprenant également majuscules et ponctuation.
FAQ
Qu'est-ce que l'algorithme de Hörner ?
L'algorithme de Hörner est une méthode efficace pour évaluer les polynômes. Il consiste à évaluer l'expression en utilisant des multiplications et des additions successives.
Comment fonctionne le chiffrement de César ?
Le chiffrement de César consiste à décaler chaque lettre d'un texte d'un certain nombre de positions dans l'alphabet. Par exemple, si le décalage est de 3, la lettre 'A' devient 'D'.
Qu'est-ce que le déchiffrement automatique de Vigenère ?
Le déchiffrement automatique de Vigenère consiste à déterminer la longueur de la clé utilisée pour chiffrer un texte, puis à appliquer un déchiffrement de Vigenère en utilisant cette clé.
