Maths-cours

Cours & exercices de mathématiques

  • Troisième
  • Seconde
  • Première
  • Terminale
  • Tle Complément.
  • Tle Expert
  • Quiz
  • 3ème
  • 2nde
  • 1ère
  • Tle
  • Tle Comp
  • Tle XP
  • Quiz

Tle Expert

moyenExercice corrigé

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
0 1 2 3 4 5 6 7 8 9 10 11 12 13
o p q r s t u v w x y z *
14 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 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.

  1. 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
  2. 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.
  3. Proposer une méthode de décodage.
  4. Décoder le mot « vfv ».

Corrigé

  1. 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, *.

  2. 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

  3. 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.
  4. 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 ».

  Signaler une erreur

Dans ce chapitre...

Cours

  • Divisibilité et congruences

Exercices

  • facileDivision euclidienne d'entiers négatifs
  • moyenArithmétique - Bac S Amérique du Nord 2013 (spé)
  • moyenDivision euclidienne : restes
  • moyenSolutions entières d'équations
  • difficileCongruences - Puissances de 2 et de 3
  • difficileDivisibilité et récurrence
  • difficileSomme de puissances et congruences

Méthodes

  • Calculer un reste à l'aide de congruences

VOIR AUSSI...

  • tableau de signe
  • loi de probabilité
  • fonction trigonométrique
  • suite géométrique
  • théorème de thalès
  • polynôme second degré
  • limites
  • fonction affine
  • théorème de pythagore
  • fonction exponentielle
  • division euclidienne
  • trigonométrie
  • python en seconde
  • fonction paire
  • loi normale
  • algorithme de dijkstra
  • tableau de variation
  • fonction dérivée

© 2021 - Maths-cours.fr - Nous contacter