WikiPrépaLivrets

Polytechnique Mathématiques 1 PC 2000Sujet et corrigé

Pas encore noté
Logo concours X

Explorer les annales

BanqueX-ENSAnnée2000FilièrePCMatièreMathématiques
Annales X-ENS PC MathématiquesX-ENS PC 2000PC MathématiquesMathématiques 2000

Téléchargements

Télécharger le sujet (PDF)
Corrigé
Lire en ligneLaTeXWord
  • Rapport du jury : non disponible

Présentation du sujet

Polynômes de Krawtchouk et matrices d'adjacence du schéma de Hamming
Afficher ou masquer la section

Le problème étudie une famille de polynômes, les polynômes de Krawtchouk, définis à partir de coefficients binomiaux généralisés, et une famille de matrices liées à la distance de Hamming entre parties d'un ensemble fini. La première partie établit les propriétés algébriques des polynômes de Krawtchouk : valeurs particulières, fonction génératrice, orthogonalité pour un produit scalaire discret et relation de récurrence à trois termes. La deuxième partie introduit la distance de Hamming entre parties d'un ensemble.

  1. 1Première partie : polynômes de KrawtchoukDéfinir les polynômes de Krawtchouk, calculer leur fonction génératrice, montrer qu'ils forment une base orthogonale pour un produit scalaire discret et établir leur relation de récurrence à trois termes.
  2. 2Deuxième partie : distance de Hamming entre parties d'un ensembleÉtudier la distance de Hamming entre parties d'un ensemble fini, définie par le cardinal de leur différence symétrique.
  3. 3Troisième partie : matrices d'adjacence du schéma de HammingExprimer les matrices d'adjacence associées à la distance de Hamming comme polynômes de Krawtchouk d'une matrice de base, construire des projecteurs spectraux associés, et déterminer les valeurs propres et sous-espaces propres de ces matrices.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.
Afficher ou masquer la section
Sujet en PDF

ÉCOLE POLYTECHNIQUE

ÉCOLE SUPÉRIEURE DE PHYSIQUE ET DE CHIMIE INDUSTRIELLES

CONCOURS D'ADMISSION 2000
filière PC

PREMIÈRE COMPOSITION DE MATHÉMATIQUES

(Durée : 4 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
On se propose d'étudier une famille de polynômes (polynômes de Krawtchouk) et une famille de matrices (matrices d'adjacence du schéma d'association de Hamming) dont les propriétés sont liées, et applicables à la théorie des codes détecteurs et correcteurs d'erreurs dans la transmission de l'information. (Ces applications ne sont pas abordées dans le problème.)
Les deux premières parties sont indépendantes.
Dans tout le problème, N désigne un entier naturel non nul.
On prend par convention 0! = 1. Si n et k sont des entiers naturels, on pose
(n/k) = {(n!)/(k!(n − k)!), si 0 ≤ k ≤ n; 0, sinon

Première partie

  1. Pour tout k ∈ Z, on définit le polynôme φ_k de la variable X par
φ_k(X) = {1/(k!)∏_(0 ≤ i ≤ k − 1)(X − i), si k > 0; 1, si k = 0; 0, si k < 0
Évaluer φ_k(j) pour chaque entier naturel j.
2. Pour tout entier n tel que 0 ≤ n ≤ N, on définit le polynôme P_n de la variable X par
P_n(X) = ∑_(k = 0)^N(− 1)^k φ_k(X)φ_(n − k)(N − X).
a) Calculer P_0, P_1 et P_2.
b) Calculer le degré et le coefficient dominant du polynôme P_n.
c) Montrer que, pour chaque entier j tel que 0 ≤ j ≤ N,
P_n(j) = ∑_(k = 0)^N(− 1)^k(j/k)((N − j)/(n − k)).
  1. Pour tout entier j tel que 0 ≤ j ≤ N, on considère la fonction f_j de la variable réelle u, définie par
f_j(u) = ∑_(n = 0)^N P_n(j)u^n.
Montrer que f_j(u) = (1 − u)^j(1 + u)^(N − j).
4. On considère la fonction F de deux variables réelles u et v, définie par
F(u, v) = ∑_(j = 0)^N(N/j)f_j(u)f_j(v).
a) Montrer que F(u, v) = α(1 + uv)^β, où α et β sont des constantes que l'on déterminera.
b) Soient a et b des entiers, 0 ≤ a ≤ N, 0 ≤ b ≤ N. Montrer que si a ≠ b :
(∂^(a + b)F)/(∂u^a∂v^b)(0, 0) = 0
Évaluer (∂^(2a)F)/(∂u^a∂v^a)(0, 0) en fonction de a et de N.
5. On note R_N[X] l'espace vectoriel des polynômes à coefficients réels de degré inférieur ou égal à N. Pour P, Q ∈ R_N[X], on pose
< P| Q>=∑_(j = 0)^N(N/j)P(j)Q(j).
a) Montrer que <|> est un produit scalaire sur R_N[X].
b) Montrer que (P_n)_(0 ≤ n ≤ N) est une base orthogonale de R_N[X] muni de ce produit scalaire.
6. Montrer que, pour tout entier m tel que 1 ≤ m ≤ N − 1,
(m + 1)P_(m + 1)(X) − (N − 2X)P_m(X) + (N − m + 1)P_(m − 1)(X) = 0.
[On calculera de deux manières différentes le coefficient de u^m dans (1 − u^2)(df_j(u))/(du).]

Deuxième partie

On pose E = {1, 2, …, N} et l'on désigne par P(E) l'ensemble des parties de E. Pour chaque partie I de E, on note Card I le cardinal de I. Si I et J sont des parties de E, on pose
d(I, J) = Card(IΔJ)
où IΔJ est l'ensemble des points de la réunion I ∪ J qui n'appartiennent pas à l'intersection I ∩ J.
7.a) À quelle condition a-t-on d(I, J) = 0 ? À quelle condition a-t-on d(I, J) = 1 ?
b) Montrer que d(IΔJ, I) = CardJ.
8. Soient I et J deux parties de E. On pose d(I, J) = k. Calculer le nombre γ_j^k de parties A de E telles que d(I, A) = 1 et d(J, A) = j.

Troisième partie

On utilise dans cette partie les notations et les résultats des deux premières parties.
On suppose P(E) muni d'un ordre total ⪯. On a donc P(E) = {I_1, I_2, …, I_(2^N)} où I_1⪯I_2⪯…⪯I_(2^N).
Pour tout entier naturel n, on définit une matrice carrée réelle à 2^N lignes
A_n, = ((A_n)_(pq))_(1 ≤ p ≤ 2^N; 1 ≤ q ≤ 2^N) par; (A_n)_(pq), = {1, si d(I_p, I_q) = n; 0, sinon
On note J la matrice identité à 2^N lignes.
9.a) Que vaut A_n pour n > N ? Expliciter A_0.
b) Montrer que pour tout entier m tel que 1 ≤ m ≤ N − 1,
A_1 A_m = (N − m + 1)A_(m − 1) + (m + 1)A_(m + 1).
  1. On pose A = 1/2(NJ − A_1). Montrer par récurrence sur n que, pour tout entier n tel que 0 ≤ n ≤ N,
A_n = P_n(A)
où les polynômes P_n sont ceux définis et étudiés dans la première partie.
11. Soit i un entier tel que 0 ≤ i ≤ N. Montrer que, si I ∈ P(E) est tel que CardI = i, alors pour tout entier j tel que 0 ≤ j ≤ N,
P_j(i) = ∑_(J ∈ P(E); CardJ = j)(− 1)^(Card(I ∩ J))
12.a) Soient I, J, K ∈ P(E). Montrer que
(− 1)^(Card((IΔJ) ∩ K)) = (− 1)^(Card(I ∩ K))(− 1)^(Card(J ∩ K))
b) Soient I, J ∈ P(E). Montrer que
∑_(K ∈ P(E))(− 1)^(Card(I ∩ K))(− 1)^(Card(J ∩ K)) = {2^N, si I = J; 0, sinon
  1. Pour tout entier k tel que 0 ≤ k ≤ N, on pose
B_k = 1/(2^N)∑_(n = 0)^N P_k(n)A_n
a) Montrer que
{(B_k)^2 = B_k; B_k B_ℓ = 0 si ℓ ≠ k
[On pourra utiliser les résultats des questions 11. et 12.].
b) Déterminer la trace et le rang de chaque matrice B_k.
14.a) Pour chaque entier n tel que 0 ≤ n ≤ N, trouver les valeurs propres de la matrice A_n.
b) Déterminer la dimension des sous-espaces propres de la matrice A_1.

Questions fréquentes

4 questions
Sur quels chapitres porte ce sujet de maths 1 X PC 2000 ?
Afficher ou masquer la section

Sur quels chapitres porte ce sujet de maths 1 X PC 2000 ?

Il porte sur les polynômes et fonctions génératrices, les produits scalaires et bases orthogonales sur un espace de polynômes, la combinatoire des ensembles finis, et la réduction des matrices.

Les parties de ce sujet sont-elles indépendantes ?

Les deux premières parties sont indépendantes l'une de l'autre ; la troisième réutilise les résultats des deux précédentes pour étudier les matrices du schéma de Hamming.

Ce sujet a-t-il un lien avec les codes correcteurs d'erreurs ?

L'énoncé précise que les polynômes de Krawtchouk et les matrices étudiées sont utiles à la théorie des codes détecteurs et correcteurs d'erreurs, mais ces applications ne sont pas abordées dans le problème lui-même.

Ce sujet demande-t-il de diagonaliser des matrices ?

Oui, la troisième partie détermine les valeurs propres et les sous-espaces propres des matrices d'adjacence étudiées, ainsi que des projecteurs spectraux associés.

Pas de description pour le moment