mat309 2019

Forum destiné aux étudiants de l'UGA (Université Grenoble-Alpes)

Modérateur : xcasadmin

parisse
Messages : 5084
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » mar. déc. 10, 2019 4:05 pm

10/12:
Preuve des 2 propositions.
Def code t-correcteur parfait.
Nombre d'elements dans une boule de rayon t.
2^n=2^k*(1+n+...+comb(n,t))
Cas t=1, codes de Hamming binaires
n=2^m-1, k=n-m
m=1 donne k=0 ne sert a rien
m=2 n=3, k=1 code de repetition
m=3, n=7, k=4 construction d'un code de Hamming systematique de distance 3, la matrice de controle contient l'ecriture en base 2 de tous les entiers de 1 a 7 en colonne. Le syndrome correspond a un entier, dont la colonne correspondante dans la matrice de controle donne le bit a corriger.
Le meme principe fonctionne pour m quelconque, exemple pour m=4, n=15, k=11.

Codes polynomiaux: poly de degre<k -> poly de degre<n, phi(P)=P*g pour g de degre m=n-k. Ce code n'est pas systematique, exemple g=x^3+x+1, k=4, n=7.
Code systematique phi(P)=P*x^m - reste(P*x^m,g), exemple ci-dessus, on retrouve un code de Hamming binaire.

J'ai evoque pour finir 2 prolongements hors programme
* corps fini faciles a manipuler sur ordinateur en base 2: reste de polynomes a coeff dans Z/2Z modulo un polynome irreductible (equivalent des restes d'entiers modulo un nombre premier)
* algorithme de Strassen pour mulitplier 2 matrices viewtopic.php?f=35&t=2432

parisse
Messages : 5084
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » ven. juil. 17, 2020 6:50 am


parisse
Messages : 5084
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: mat309 2019

Message par parisse » ven. juil. 17, 2020 7:12 am

Sujet juin 2020: https://www-fourier.univ-grenoble-alpes ... juin20.pdf
Elements de correction:
Exercice 1: restes chinois modulo 137 et 2020 (qui sont premiers entre eux)

Exercice 2: 1/ tester la divisibilite par 2 et par les nombres impairs <= racine carree de 2027
2/ Bezout sur E et 2027
3/ le nombre de division s'obtient a partir du nombre de bits et du nombre de 1 de l'ecriture en base 2 de l'exposant 2020=0b11111100100 (7 bits a 1 et 11 bits)
4/ 2027 est premier donc son indicatrice d'Euler vaut 2026, donc E^2026=1 mod 2027 donc E^2020*E^6=1 mod 2027 et E^2020=i^6 mod 2027. Si on connait i, il est donc plus rapide de calculer i^6 mod 2027, mais si on ne le connait pas, il vaut mieux calculer E^2020 directement.

Exercice 3.1:
2/ 10=1 mod 9, donc 10^k mod 9=(1 mod 9)^k=1 mod 9
3/ donc les classes modulo 9 de sum(a_i*10^i) et de sum(a_i) sont identiques. En recommancant autant de fois que necessaire, on en deduit que les classes modulo 9 de a et f(a) sont identiques.
4/ ab mod 9 =(a mod 9)*(b mod 9) donc f(ab)=f(f(a)*f(b)) car ils sont egaux mod 9 et compris entre 1 et 9 qui contient exactement 1 representant par classe modulo 9.
5/ donc si f(c)!=f(f(a)*f(b)) alors c!=a*b. Si f(c)=f(f(a)*f(b)), c n'est pas forcement egal a a*b, par exemple f(3*5)=f(6)
6/ E=q*10^5+r donc E mod 9 =(q+r) mod 9 donc f(E)=f(q+r) mod 9 donc ils sont egaux car compris entre 1 et 9 qui contient exactement 1 representant par classe modulo 9.
7/ En langage naturel, sans utiliser l'analyse mathematique precedente:

Code : Tout sélectionner

fonction f(x)
repeter 
  s := 0 // somme des chiffres de x
  tantque x!=0 faire
    s += reste(x,10) // dernier chiffre de l'ecriture de x en base 10
    x := quotient(x,10)
  fin tantque
  x := s
jusqua x<10
renvoyer x
fin de fonction
En C

Code : Tout sélectionner

int f(int x){
  for (;;){
    int s=0;
    while (x){
      s += x%10;
      x /= 10;
    }
    if (s<10) return s;
    x=s;
  }
}
En Python

Code : Tout sélectionner

def f(x):
  while True:
    s=0
    while x!=0:
      s += x%10
      x = x//10
    if s<10: return s
    x=s
On peut evidemment optimiser en utilisant l'analyse mathematique de f et renvoyer x mod 9 en remplacant 0 par 9, en Python:

Code : Tout sélectionner

def f(x):
  r = x % 9
  if r==0:
    return 9
  return r
en C

Code : Tout sélectionner

int f(int x){
  int r=x%9;
  return r?r:9;
}


Exercice 3.2:
L'analyse mathematique est en tout point similaire puisque 0x10=1 mod 0xF
4/ E=10^5*q+r, donc E=r modulo 16, donc g(E)=g(r) mais on n'a pas en general g(E)=g(q+r) (sauf si q=0 modulo 16).
5 et 6/ dans l'algorithme en langage naturel, remplacer 10 par 16=0x10, en base b remplacer 10 par b. L'analyse mathematique est identique en remplacant 9 ou 0xF par b-1 (puisque b=1 mod b-1)

Répondre