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.
La matrice est appelée la matrice de codage.
- É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.
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 :
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
Partie B
> 1. Étapes d'un processus de codage dans un cas particulier
Pour justifier le passage de à
, il faut chercher le reste de la division de 55 par 26 et celui de 93 par 26 .
> 2. a) Un système de congruences
La transformation de en
par le procédé de codage donne successivement :
De même, la transformation de en
par le procédé de codage donne successivement :
et , (étape 3 de la procédure).
On obtient au final :
b) Résolution d'un système de congruences
Attention
À développer et simplifier pour obtenir la deuxième ligne du système suivant.
Cela équivaut finalement à :
Cela équivaut à dire que est un multiple de 26.
> 3.a) Identifier l'inverse d'une matrice
b) Effectuer un produit matriciel
c) Décodage dans un cas particulier
d) Conjecture sur le procédé général de décodage
> 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
.