Codage - Bac Nle Calédonie 2013
Bac S Nouvelle Calédonie 2013
On note E l'ensemble des vingt-sept nombres entiers compris entre 0 et 26.
On note A l'ensemble dont les éléments sont les vingt-six lettres de l'alphabet et un séparateur entre deux mots, noté «*» considéré comme un caractère.
Pour coder les éléments de A, on procède de la façon suivante :
Premièrement : On associe à chacune des lettres de l'alphabet, rangées par ordre alphabétique, un nombre entier naturel compris entre 0 et 25, rangés par ordre croissant. On a donc a → 0, b → 1, ... z → 25.
On associe au séparateur «*» le nombre 26.
| a | b | c | d | e | f | g | h | i | j | k | l | m | n | o |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| p | q | r | s | t | u | v | w | x | y | z | * |
| 15 | 13 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
Deuxièmement : à chaque élément x de E, l'application g associe le reste de la division euclidienne de 4x+3 par 27.
On remarquera que pour tout x de E, g(x) appartient à E.
Troisièmement : Le caractère initial est alors remplacé par le caractère de rang g(x). Exemple : s → 18, g(18)=21 et 21 → v. Donc la lettre s est remplacée lors du codage par la lettre v.
Trouver tous les entiers x de E tels que g(x)=x c'est-à-dire invariants par g.
En déduire les caractères invariants dans ce codage
Démontrer que, pour tout entier naturel x appartenant à E et tout entier naturel y appartenant à E, si y ≡ 4x+3 modulo 27 alors x ≡ 7y+6 modulo 27.
En déduire que deux caractères distincts sont codés par deux caractères distincts.
Proposer une méthode de décodage.
Décoder le mot « vfv »
Corrigé
g(x)=x si et seulement si 0 ≤ x ≤ 26 et :
4x+3 ≡ x (mod. 27)
Cette congruence est vérifiée si et seulement si il existe un entier relatif k tel que :
4x+3 = x+27k 3x = 27k−3
3x = 27k−3 x = 9k−1Pour k≤0, les valeurs de x obtenues sont strictement négatives et pour k > 3 elles sont strictement supérieures à 26.
On obtient donc trois solutions comprises entre 0 et 26 :
x=8 (pour k=1)
x=17 (pour k=2)
x=26 (pour k31)
Par conséquent, les caractères invariants dans ce codage sont : i, r, *.
Si y ≡ 4x+3 (mod. 27) alors :
7y ≡ 7(4x+3) (mod. 27)
7y ≡ 28x+21 (mod. 27)
Comme 28 ≡ 1 (mod. 27) et 21≡−6 (mod. 27) on a alors :
7y ≡ x−6 (mod. 27) x ≡ 7y+6 (mod. 27)
Soient deux entiers naturels x et x′, compris entre 0 et 26, ayant la même image y par g. Alors g(x)=y et g(x′)=y.
Par conséquent, x ≡ 7y+6 (mod. 27) et x′ ≡ 7y+6 (mod. 27).
Donc, comme x est compris entre 0 et 26, x est le reste de la division euclidienne de 7y+6 par 27 ainsi que x′. L'unicité du reste entraîne que x=x′.
Par conséquent, si deux caractères sont codés de façon identique, c'est qu'ils sont identiques. Autrement dit, deux caractères distincts sont codés par deux caractères distincts
La formule x ≡ 7y+6 permet de décoder un caractère. Il suffit de procéder de la façon suivante :
1ère étape: A chaque lettre on associe son rang y
2ème étape : à chaque valeur de y , l'application h associe le reste de la division euclidienne de 7y+6 par 27.
3ème étape : Le caractère initial est alors remplacé par le caractère de rang h(y) trouvé à la seconde étape.
On utilise la méthode décrite précédemment :
v → y=21; h(21) est le reste de la division de 7×21+6=153 par 27 donc h(21)=18;
18 → s
f → y=5; h(5) est le reste de la division de 7×5+6=41 par 27 donc h(21)=14;
14 → o
Le mot « vfv » se décode : « sos ».