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é «[i]» 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 «[/i]» 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 |
On dit que a a pour rang 0, b a pour rang 1, ... , z a pour rang 25 et le séparateur «» a pour rang 26.
Deuxièmement : à chaque élément [i]x de E, l'application g associe le reste de la division euclidienne de 4_x_+3 par 27.
On remarquera que pour tout x de E, g_([i]x) appartient à E.
Troisièmement : Le caractère initial est alors remplacé par le caractère de rang g_([i]x). Exemple : s → 18, g_(18)=21 et 21 → [i]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_([i]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 ≡ 4_x_+3 modulo 27 alors x ≡ 7_y_+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_([i]x)=x si et seulement si 0 ≤ x ≤ 26 et :
4_x_+3 ≡ x (mod. 27)
Cette congruence est vérifiée si et seulement si il existe un entier relatif k tel que :
4_x_+3 = x_+27_k 3_x[/i] = 27_k_−3
3_x[/i] = 27_k_−3 x = 9_k_−1Pour k_≤0, les valeurs de [i]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 :
- [i]x_=8 (pour [i]k_=1)
- [i]x_=17 (pour [i]k_=2)
- [i]x_=26 (pour [i]k_31)
Par conséquent, les caractères invariants dans ce codage sont : i, r, [/i].
Si y ≡ 4_x_+3 (mod. 27) alors :
7_y[/i] ≡ 7(4_x_+3) (mod. 27)
7_y[/i] ≡ 28_x_+21 (mod. 27)
Comme 28 ≡ 1 (mod. 27) et 21≡−6 (mod. 27) on a alors :
7_y[/i] ≡ x_−6 (mod. 27) [i]x ≡ 7_y_+6 (mod. 27)
Soient deux entiers naturels x et x_′, compris entre 0 et 26, ayant la même image [i]y par g. Alors g_([i]x)=y et g_([i]x_′)=[i]y.
Par conséquent, x ≡ 7_y_+6 (mod. 27) et [i]x_′ ≡ 7_y_+6 (mod. 27).
Donc, comme x est compris entre 0 et 26, x est le reste de la division euclidienne de 7_y_+6 par 27 ainsi que [i]x_′. L'unicité du reste entraîne que [i]x_=[i]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 ≡ 7_y_+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 7_y_+6 par 27.
- 3ème étape : Le caractère initial est alors remplacé par le caractère de rang h_([i]y) trouvé à la seconde étape.
On utilise la méthode décrite précédemment :
v → [i]y_=21; [i]h_(21) est le reste de la division de 7×21+6=153 par 27 donc [i]h_(21)=18;
18 → s
f → [i]y_=5; [i]h_(5) est le reste de la division de 7×5+6=41 par 27 donc [i]h_(21)=14;
14 → o
Le mot « vfv » se décode : « sos ».