Arithmétique
matT_1309_04_05C
ENS. DE SPÉCIALITÉ
39
CORRIGE
Antilles, Guyane • Septembre 2013
Exercice 4 • 5 points
Partie A
On considère l'algorithme suivant :
| A et X sont des nombres entiers Saisir un entier positif A Affecter à X la valeur de A Tant que X supérieur ou égal à 26 Affecter à X la valeur X– 26 Fin du tant que Afficher X |
Partie B
On veut coder un bloc de deux lettres selon la procédure suivante (détaillée en quatre étapes) :
- Étape 1 : chaque lettre du bloc est remplacée par un entier en utilisant le tableau ci-dessous :
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
On obtient une matrice colonne 
où x1 correspond à la première lettre du mot et x2 correspond à la deuxième lettre du mot.
- Étape 2 :
est transformé en 
tel que
.
La matrice 
est appelée la matrice de codage.
- Étape 3 :
est transformé en 
tel que
- Étape 4 :
est transformé en bloc de deux lettres en utilisant le tableau de correspondance donné dans l'étape 1.
Exemple :
Le bloc RE est donc codé en DP
à 
puis 
.
, 
, quatre nombres entiers compris entre 0 et 25 tels que 
et 
sont transformés lors du procédé de codage en 
.
.
et 
puis que 
et 
.
est la matrice inverse de C.
tels que 
.
tels que 
.
On considère un bloc de deux lettres et on appelle z1 et z2 les deux entiers compris entre 0 et 25 associés à ces lettres à l'étape 3. On cherche à trouver deux entiers x1 et x2 compris entre 0 et 25 qui donnent la matrice 
par les étapes 2 et 3 du procédé de codage.
Soient 
et 
tels que 
où 
.
Soient x1 et x2, les nombres entiers tels que :
Montrer que 
.
Conclure.
Durée conseillée : 60 min
Les thèmes clés
Algorithme • Produit matriciel • Congruences.
Nos coups de pouce
Partie B
et à la matrice colonne
. Concluez en utilisant le fait que ces deux matrices sont transformées toutes les deux en la matrice colonne 
.
. Concluez.
Partie A
> 1. Analyse d'un algorithme et affichage en sortie au vu de l'entrée proposée
Si on saisit la valeur 3, X reçoit 3. Comme X n'est pas supérieur ou égal à 26, la condition de la boucle Tant que n'est pas vérifiée, cette dernière ne s'exécute donc pas et X s'affiche. Ainsi,
> 2. Analyse d'un algorithme et affichage en sortie au vu de l'entrée proposée
Si on saisit la valeur 55, X reçoit 55. Comme X est supérieur ou égal à 26, la boucle Tant que s'exécute. X prend alors successivement les valeurs 
et 
. Dans ce dernier cas, X n'est pas supérieur ou égal à 26, la condition de la boucle Tant que n'est plus vérifiée, cette dernière s'arrête et X s'affiche.
> 3. Analyse générale d'un algorithme
Pour un nombre entier naturel 
saisi, cet algorithme affiche le reste de la division de 
par 26.
Partie B
> 1. Étapes d'un processus de codage dans un cas particulier
Attention
dans l'étape 2 de la procédure.
Pour justifier le passage de 
à 
, il faut effectuer le produit par la matrice 
.
.
Attention
dans l'étape 3 de la procédure.
Pour justifier le passage de 
à 
, il faut chercher le reste de la division de 55 par 26 et celui de 93 par 26 .
Or 
donc 
Ensuite 
donc 
.
Attention
dans l'étape 3 de la procédure.
Par conséquent, 
et 
.
Le passage de 
à 
est ainsi justifié.
> 2. a) Un système de congruences
La transformation de 
en 
par le procédé de codage donne successivement :
(étape 2 de la procédure),
et 
(étape 3 de la procédure).
De même, la transformation de 
en 
par le procédé de codage donne successivement :
(étape 2 de la procédure),
et 
, (étape 3 de la procédure).
On obtient au final :
b) Résolution d'un système de congruences
Le système obtenu à la question précédente est équivalent à :
lui-même équivalent à
Attention
À développer et simplifier pour obtenir la deuxième ligne du système suivant.
Cela équivaut finalement à :
Ainsi, 
et 
.
Cela équivaut à dire que 
est un multiple de 26.
Or 
et 
sont des entiers compris entre 0 et 25.
Cela signifie donc que 
est égal à 0, soit 
. De même, 
.
> 3.a) Identifier l'inverse d'une matrice
b) Effectuer un produit matriciel
.
c) Décodage dans un cas particulier
donc 
.
donc 
.
d) Conjecture sur le procédé général de décodage
On transforme 
en 
en calculant :
puis 
est transformée en 
telle que :
> 4. Le problème du décodage dans le cas général
On a tout d'abord :
.
Si
alors
La matrice 
se code bien en la matrice 
. Donc la matrice 
se décode bien en 
.
> 5. Décodage d'une séquence donnée
Les lettres QC se codent en 
.
On multiplie cette matrice par 
:
.
On remarque ensuite que 
donc 
avec 
.
Puis 
donc 
avec 
.
Comme le nombre 4 code la lettre E,