Baccalauréat S Antilles-Guyane 11 septembre 2013 - Correction Spécialité
Spécialité 5 points
Partie A
On considère l'algorithme suivant :
A et Xsont 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
- Qu'affiche cet algorithme quand on saisit le nombre 3 ? Si on saisit le nombre 3, l’algorithme affiche 3.
- Qu'affiche cet algorithme quand on saisit le nombre 55 ? Si on saisit le nombre 55 l’algorithme affiche 3.
- Pour un nombre entier saisi quelconque, que représente le résultat fourni par cet algorithme? Cet algorithme fournit le reste de la division euclidienne de A par 26.
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:
ABCDEFGHIJKLM0123456789101112NOPQRSTUVWXYZ13141516171819202122232425
On obtient une matrice colonne (x1x2) où x1 correspond à la première lettre du mot et x2 correspond à la deuxième lettre du mot.
Étape 2 : (x1x2) est transformé en (y1y2) tel que
(y1y2)=(3152)(x1x2)
La matrice C=(3152) est appelée la matrice de codage.
Étape 3 : (y1y2) est transformé en (z1z2) tel que {z1≡y1(26)avec0⩽z1⩽25z2≡y2(26)avec0⩽z2⩽25
Étape 4 : (z1z2) est transformé en un bloc de deux lettres en utilisant le tableau de correspondance donné dans l'étape 1.
Exemple : RE →(174)→(5593)→(315)→ DP Le bloc RE est donc codé en DP Justifier le passage de (174) à (5593) puis à (315).
- Étape 1 : RE →(174) en utilisant le tableau
- Étape 2 :(174) est transformé en (y1y2) tel que
(y1y2)=(3152)(174)=(3×17+1×45×17+2×4)=(5593) - Étape 3 : {55≡3(26)avec0⩽3⩽2593≡15(26)avec0⩽13⩽25
- Étape 4 :(315)→ DP en utilisant le tableau
On a donc bien : RE →(174)→(5593)→(315)→ DP Le bloc RE est donc codé en DP
- Soient x1,x2,x′1,x′2 quatre nombres entiers compris entre 0 et 25 tels que (x1x2) et (x′1x′2) sont transformés lors du procédé de codage en (z1z2).
- Montrer que {3x1+x2≡3x′1+x′2(26)5x1+2x2≡5x′1+2x′2(26). On a donc y1=3x1+x2 et y2=5x1+2x2 ainsi que y′1=3x′1+x′2 et y′2=5x′1+2x′2.
- En déduire que x1≡x′1(26) et x2≡x′2(26) puis que x1=x′1 et x2=x′2. On appelle L1 la ligne 3x1+x2≡3x′1+x′2 (26) et L2 la ligne 5x1+2x2≡5x′1+2x′2 (26).
Or z1≡y1 (26) et z1≡y′1 (26) par conséquent y1≡y′1 (26).
D’où 3x1+x2≡3x′1+x′2 (26).
De même z2≡y2 (26) et z2≡y′2 (26) par conséquent y2≡y′2 (26)
Et 5x1+2x2≡5x′1+2x′2 (26).
Alors 2l1−L2 donne x1≡x′1 (26) et 3L2–5L1 donne x2≡x′2 (26).
Les nombres x1, x2, x′1 et x′2 sont des entiers compris entre 0 et 25.
Par conséquent ils sont égaux à leur reste dans la division euclidienne par 26.
Cela signifie donc que x1=x′1 et x2=x′2. - On souhaite trouver une méthode de décodage pour le bloc DP :
- Vérifier que la matrice C′=(2−1−53) est la matrice inverse de C. C×C′=(1001). Par conséquent C′ est bien la matrice inverse de la matrice C.
- Calculer (y1y2) tels que (y1y2)=(2−1−53)(315). (y1y2)=(2×3–1×15−5×3+3×15)=(−930)
- Calculer (x1x2) tels que {x1≡y1(26)avec0⩽x1⩽25x2≡y2(26)avec0⩽x2⩽25 Alors −9=−26+17 donc x1=17 et 30=26+4 d’où x2=4.
- Quel procédé général de décodage peut-on conjecturer ? On peut donc conjecturer que {x1≡2y1–y2 (26)avec 0≤x1≤25x2≡−5y1+3y2 (26)avec 0≤x2≤25
- Dans cette question nous allons généraliser ce procédé de décodage. 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 colonne (z1z2) par les étapes 2 et 3 du procédé de codage. Soient y′1 et y′2 tels que (y′1y2)=C′(z1z2) où C′=(2−1−53).
Soient x1 et x2, les nombres entiers tels que {x1≡y′1(26)avec0⩽x1⩽25x2≡y′2(26)avec0⩽x2⩽25
Montrer que {3x1+x2≡z1(26)5x1+2x2≡z2(26).. Conclure. 3x1+x2≡6y1–3y2–5y1+3y2≡y1≡z1 (26) - Décoder QC. QC→(162)
5x1+2x2≡10y1–5y2–10y1+6y2≡y2≡z2 (26)
Par conséquent (x1x2) est bien le couple de nombres initial ayant permis d’obtenir (y1y2) à l’aide du procédé de codage.
Alors y′1=16×2–1×2=30 et y′2=−5×16+3×2=−74.
Par conséquent x′1=4 et x′2=4.
Le code QC provenait donc de EE.
- Vues: 38704