© Éditions H&K
X Informatique MP/PC 2008 -- Corrigé
Ce corrigé est proposé par Arnaud Borde (École Polytechnique) ; il a été relu
par
Céline Chevalier (ENS Cachan) et Vincent Puyhaubert (Professeur en CPGE).
Le sujet propose l'étude de deux méthodes de codage de texte basées sur le
décalage des lettres dans l'alphabet. On travaille cependant sur une
représentation
simpliste d'un texte par des tableaux d'entiers. Dans les deux méthodes, on
commence par écrire les fonctions simples qui permettent de coder un texte à
partir
d'une clé. Puis on étudie des techniques pour décoder le texte automatiquement,
c'est-à-dire sans connaître la clé. Il s'agit du travail qu'est amené à faire
tout pirate
qui se respecte.
La plupart des questions demandent d'écrire du code. Il est rédigé en Maple
dans ce corrigé car ce langage est le plus utilisé en classe préparatoire, même
s'il
est plus destiné au calcul formel qu'à la programmation. D'autres langages comme
C, C++, Caml, Pascal et Java étaient autorisés pour cette épreuve. Les fonctions
écrites n'utilisant que la syntaxe de base, vous pourrez sans difficulté les
réécrire
dans le langage de votre choix.
· La première partie a pour objectif l'étude du codage de César. Ce codage
basique paraîtra familier à tout le monde puisqu'il consiste simplement à
choisir un entier k (une lettre en fait, mais peu importe) et à remplacer chaque
lettre du texte par la k e qui la suit dans l'alphabet. Par exemple, pour k = 1,
on remplace « a » par « b », « b » par « c », et ainsi de suite jusqu'au « z »
remplacé par « a ».
Comme mentionné précédemment, l'objectif de cette partie est non seulement
de rédiger les programmes qui codent un texte, mais aussi de trouver une
méthode de décodage automatique, basée sur l'hypothèse (souvent vérifiée) que
la lettre « e » est la plus présente dans le texte original. Elle ne devrait
poser
aucun problème à tout candidat familier avec l'usage des boucles.
· La seconde partie étudie le codage de Vigenère, qui est une amélioration de la
méthode de César. Il s'agit cette fois d'utiliser non pas un unique entier,
mais p
entiers k1 , . . . , kp (en fait, un mot de p lettres). On code alors la ne
lettre du
texte grâce à un décalage de k(n mod p) caractères.
À nouveau, la difficulté de cette partie réside essentiellement dans l'écriture
de
la fonction de décodage automatique. Heureusement, le travail est en grande
partie facilité par l'énoncé, qui détaille de façon précise les hypothèses à
effectuer sur le texte et l'algorithme à employer.
Au final, le problème est assez long, mais en étant efficace il est possible
d'en
venir à bout dans les deux heures imparties. Il est bien écrit et très agréable
à suivre.
On peut passer pas mal de temps à s'amuser avec les fonctions de codage/décodage
une fois le problème résolu en totalité.
© Éditions H&K
Indications
2 Écrire dès maintenant une fonction reste(a,b) qui renvoie le reste de la
division
de a par b.
3 Penser à réutiliser le code de la question 2 sans tout refaire.
4 Initialiser le tableau contenant les fréquences avec des 0. Parcourir le
tableau de
sorte que pour chaque nouvelle lettre lue, on mette à jour la case
correspondante
dans le tableau des fréquences.
5 Pour trouver la lettre qui code « e », rechercher la lettre dont l'entrée
dans le
tableau frequences est maximale. C'est cette lettre qui servira à calculer la
clé
de décodage.
7 Utiliser la fonction reste afin d'associer le bon décalage à chaque lettre du
texte
original.
8 Utiliser une méthode récursive. A partir d'un couple d'entier donné en
argument,
retrancher le plus petit au plus grand jusqu'à ce que le résultat de la
soustraction
soit nul.
9 Passer en revue tous les triplets de lettres qui suivent t[i], t[i+1], t[i+2]
et les
comparer à ce dernier. Faire attention aux indices de début et de fin de la
boucle.
Utiliser la propriété d'associativité du pgcd pour mettre à jour le résultat au
fur
et à mesure du parcours.
10 Utiliser les fonctions des questions 8 et 9. Utiliser encore la propriété
d'associativité du pgcd et appliquer l'algorithme donné par l'énoncé.
11 Bien compter le nombre d'itérations dans les boucles.
12 Voir les différents tableaux t[j], t[j+k], t[j+2k],..., pour j {0, k - 1},
comme
des textes codés par la méthode de César.
13 Conserver la vision de t comme un ensemble de textes codés par la méthode
César
et les décoder successivement comme dans la première partie. Utiliser une
matrice
(un tableau de tableaux) pour faciliter la remise en ordre du texte.
© Éditions H&K
Codage de César
Ce corrigé introduit deux fonctions locales (reste et quotient) qui ne
sont pas indispensables pour cette épreuve mais qui permettent de gagner du
temps et évitent d'utiliser des fonctions de Maple qui ne sont peut-être pas
connues de tous.
Rappelons également que tout ce qui est précédé d'un # dans un programme en
Maple n'est pas interprété par le compilateur, ce qui permet
d'insérer des commentaires dans le code.
1 Représentons les phases du codage dans un tableau. Les différentes lignes
représentent : le texte d'origine, les entiers correspondants, les entiers
après décalage,
le texte codé.
m
12
7
h
a
0
21
v
i
8
3
d
t
19
14
o
r
17
12
m
e
4
25
z
c
2
23
x
o
14
9
j
r
17
12
m
b
1
22
w
e
4
25
z
a
0
21
v
u
20
15
p
Le codage de maitrecorbeau avec un décalage de 5 vers la gauche est donc :
hvdomzxjmwzvp
Il faut être attentif au fait que le décalage se fait vers la gauche.
2 Commençons par écrire une fonction reste(a,b) qui renvoie le reste de la
division
de a par b. On programme cette fonction de manière récursive, en partant de a
et en soustrayant b autant de fois qu'il le faut pour le résultat devienne égal
à b.
Notons qu'il faut aussi penser à prendre en compte le cas où a est négatif.
reste:=proc(a,b)
if 0<=a and a=b then RETURN(reste(a-b,b));
else RETURN(reste(a+26,b));
# correspond au cas où a est négatif
fi;
end;
Cette fonction peut être remplacée par la fonction Maple irem(a,b).
Cette fonction va principalement servir dans le cas particulier b = 26 pour se
ramener à un entier compris entre 0 et 25 dès qu'on effectue un décalage.
Pour coder un texte, chaque lettre doit être décalée vers la gauche du nombre d.
Pour cela, on construit au moyen d'une boucle for un tableau resultat de même
taille que le tableau t donné en entrée, dans lequel on stocke le texte chiffré.
Pour chaque indice, l'élément rajouté au tableau est le reste de la division
par 26
du chiffre t[i] auquel on a soustrait d.
© Éditions H&K
codageCesar:=proc(t,n,d)
local resultat,i;
resultat:=[seq(0,i=0..n-1)];
for i from 0 to n-1 do
resultat[i+1]:=reste(t[i+1]-d,26);
od;
RETURN(resultat);
end;
Dans Maple, contrairement aux autres langages de programmation, les
indices de tableaux commencent par défaut à 1 et non à 0. Si vous utilisez ce
langage, il est bien de préciser la convention que vous adoptez pour les indices
car le sujet suppose qu'ils débutent à 0. On respecte ici la convention utilisée
par l'énoncé pour les boucles tout en conservant un code exécutable en
réajustant les indices dans le corps de la boucle avec la syntaxe tableau[i+1].
La commande seq permet de fabriquer une séquence. Sa syntaxe générale est
seq(f(compteur),compteur=début..fin). Elle produit alors la
séquence f(début), f(début+1), ..., f(fin). Ici, cette séquence est placée
entre crochets afin de fabriquer une liste.
Il existe une fonction de Maple, nops(), qui permet de récupérer la longueur du
tableau ou de la liste placé en argument. On aurait donc pu se
passer du second argument de la fonction (et de même pour beaucoup de
fonctions demandées par l'énoncé). Mais il y a fort à parier que les
concepteurs du sujet n'ont pas voulu pénaliser les élèves qui ne connaîtraient
pas
cette fonction.
3 Il suffit d'utiliser la fonction précédente avec un décalage opposé.
decodageCesar:=proc(t,n,d)
codageCesar(t,n,-d);
end;
4 On remplit en premier lieu le tableau des fréquences appelé freq à l'aide de 0
avant de parcourir le texte et de le mettre à jour au fur et à mesure. À chaque
fois
que l'on rencontre une lettre, on augmente la case correspondante (à savoir
celle dont
l'indice est t'[i]) dans le tableau des fréquences de 1.
frequences:=proc(tprime,n)
local freq,i;
# on crée le tableau des fréquences avec des 0
freq:=[seq(0,i=0..26)];
# on met à jour le tableau des fréquences
for i from 0 to n-1 do
freq[tprime[i+1]+1]:=freq[tprime[i+1]+1]+1;
od;
RETURN(freq);
end;