ENS Informatique Fondamentale (Maths Info) MP 2011Sujet

Pas encore noté

Explorer les annales

BanqueX-ENS Année2011 FilièreMP MatièreMathématiques-Informatique

Annales X-ENS MP Mathématiques-Informatique X-ENS MP 2011 MP Mathématiques-Informatique Mathématiques-Informatique 2011

Téléchargements

Télécharger le sujet (PDF)

Lire en ligne LaTeX Word

Corrigé : pas encore disponible
Rapport du jury : non disponible

Ces sujets peuvent vous intéresser

Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

ÉCOLES NORMALES SUPÉRIEURES

COMPOSITION D'INFORMATIQUE-MATHÉMATIQUES - (ULC)

(Durée : 4 heures)

Les calculatrices sont interdites.

La qualité de la rédaction sera prise en compte dans la note finale.

Autour des codes correcteurs

Nous allons traiter dans ce sujet quelques points relatifs aux codes correcteurs d'erreur. Ce domaine s'occupe de la transmission fiable d'informations via un canal possiblement bruité. Cette théorie trouve de nombreuses applications pratiques comme la transmission d'information par satellite ou les disques compacts par exemple.

Nous allons dans un premier temps examiner certains points fondamentaux de cette théorie.

Dans une deuxième partie, nous allons considérer une famille particulière de codes. Ils sont normalement définis sur des objets que l'on appelle corps finis mais pour des raisons de compatibilité avec le programme de l'épreuve, nous allons les définir sur

ℝ

ℂ

. Cela ne nous empêchera pas de mettre en évidence un certain nombre de leurs propriétés classiques. Nous allons notamment étudier un algorithme de décodage de ces codes.

La troisième partie sera consacrée au développement d'algorithmes qui nous permettront d'accélérer la procédure de décodage introduite dans la deuxième partie.

Pour finir, nous reviendrons dans le cadre plus réaliste de codes définis sur un ensemble fini et nous mettrons en place les propriétés qui nous permettront d'établir des bornes sur le nombre de mots que peut contenir un code, et d'avoir ainsi une idée un peu plus précise de l'efficacité de ce code.

Préambule

Dans la suite, si

x

est un nombre réel,

⌊x⌋

désignera la partie entière de

x

, i.e. le plus grand entier relatif inférieur ou égal à

x

. Si

E

désigne un ensemble fini, on notera

card(E)

son nombre d'éléments. Soit

m

n

deux entiers relatifs, on définit

(n/m) = {(n!)/((n - m)!m!) si 0 ⩽ m ⩽ n,; 0 sinon.

Une somme et un produit indexés sur un ensemble vide vaudront, comme d'habitude, respectivement 0 et 1 .

Partie 1 : Codes correcteurs

Soit

A

un ensemble non vide,

n

un entier naturel non nul. On désignera par

A^n

l'ensemble

{x = (x_1, x_2, …, x_n), x_i ∈ A}

. Les éléments de

A^n

seront appelés mots.

x = (x_1, x_2, \dots, x_n)

y = (y_1, y_2, \dots, y_n)

désignent deux mots de

A^n

, on note

δ_(H, n)(x, y) = card({i ∈ {1, 2, …, n}, x_i ≠ y_i}).

Question 1.1. Démontrer que

δ_(H, n)

définit une distance sur

A^n

Dans la suite,

δ_(H, n)

sera notée plus simplement

δ_H

Un code sur

A

de longueur

n

est un sous-ensemble

C

A^n

. Dans tout le problème, un code comportera toujours au moins deux éléments distincts. L'ensemble

A

sera appelé alphabet, l'entier

n

sera appelé la longueur du code

C

et les éléments de

C

seront appelés les mots du code.

Soit

e

un entier naturel. On dit qu'un code

C

de longueur

n

sur un alphabet

A

vérifie la condition de décodage d'ordre

e

si pour tout

y \in A^n

, il existe au plus un mot

x \in C

tel que

δ_H(x, y) ⩽ e

La distance minimale d'un code

C

est l'entier

d_C = min{δ_H(x, y); (x, y) ∈ C × C, x ≠ y}.

Question 1.2. Justifier que

d_C

est bien définie.

Question 1.3. Soit

C

un code et

e

un entier naturel. Montrer que si

d_C ⩾ 2e + 1

alors

C

vérifie la condition de décodage d'ordre

e

La capacité de correction d'un code

C

est l'entier

e = ⌊(d_C - 1)/2⌋

, où

d_C

désigne la distance minimale de

C

Dans la pratique, un mot

x

d'un code

C

de longueur

n

est envoyé via un canal de communication et l'on note

y

le mot de

A^n

reçu. Le but est, lorsque c'est possible, de retrouver

x

à partir de

y

: tout moyen permettant d'effectuer une telle opération est appelé décodage.

On suppose

A

fini pour toute la suite de la Partie 1.

Question 1.4. Soit

x \in A^n, r \in ℕ

, on désigne par

B(x, r)

la boule fermée de centre

x

et de rayon

r

pour la distance

δ_H

, i.e.

B(x, r) = {y ∈ A^n; δ_H(x, y) ⩽ r}

.
(a). Pour tout

i \in ℕ

, on désigne par

S(x, i)

la sphère centrée en

x

et de rayon

i

, i.e.

S(x, i) = {y ∈ A^n; δ_H(x, y) = i}

. Démontrer que

card(B(x, r)) = \sum_(i = 0)^r card(S(x, i))

(b). En déduire que

card(B(x, r)) = \sum_(i = 0)^r(card(A) - 1)^i(n/i)

Question 1.5. Soit

C

un code de longueur

n

sur un alphabet

A

. Démontrer qu'il existe un plus petit rayon

r

tel que l'ensemble des boules de rayon

r

centrées en chaque mot du code forme un recouvrement de

A^n

. On note

ρ(C)

ce rayon.

Question 1.6.

(a). Soit

C

un code de longueur

n

sur un alphabet

A

, de capacité de correction

e

. Démontrer que

card(C)\sum_(i = 0)^e(card(A) - 1)^i(n/i) ⩽ (card(A))^n

(b). Soit

C

un code de longueur

n

sur un alphabet

A

. Montrer de même que

card(C)\sum_(i = 0)^(ρ(C))(card(A) - 1)^i(n/i) ⩾ (card(A))^n

Intermède : notations et définitions

Dans les deux prochaines parties,

K

désignera le corps des nombres réels

ℝ

ou le corps des nombres complexes

ℂ, K[X]

désignera l'anneau des polynômes à coefficients dans

K

K(X)

le corps des fractions rationnelles à coefficients dans

K

. Ces deux ensembles sont aussi des

K

espaces vectoriels. Un élément

P

d'un de ces deux ensembles pourra aussi être noté

P(X)

. Un polynôme à coefficients dans

K

est dit unitaire si son coefficient dominant, i.e. le coefficient de son terme de plus haut degré, vaut 1 . On convient que deg

0 = - \infty

Soit

A, B

C \in K[X]

. On dit que

A

divise

B

s'il existe

D \in K[X]

tel que

B = AD

. On notera

A \equiv BmodC

C

divise

A - B

Il vous sera demandé d'estimer l'efficacité de certaines procédures de calculs. On le fera comme suit. Soit

K

désignant

ℝ

ℂ

, on supposera que le coût d'une opération arithmétique (addition, soustraction, multiplication, division) sur

K

est unitaire. On devra donc estimer, ou au moins majorer, le nombre d'opérations arithmétiques sur

K

qui seront effectuées au cours de l'exécution des algorithmes.

Soit

(f(n))

(g(n))

deux suites réelles définies à partir d'un certain rang

n_0

. On écrit que

f(n) = O(g(n)), n \to \infty

s'il existe

K > 0

N ⩾ n_0

tels que pour tout

n \in ℕ, n ⩾ N

, on a

|f(n)| ⩽ K|g(n)|

.
On généralise cette notation à des fonctions de deux arguments : soit

m_0

n_0

deux entiers fixés, si

f

g

sont deux fonctions à valeurs réelles définies en tout couple

(m, n) \in ℕ^2, m ⩾ m_0

n ⩾ n_0

. On écrit que

f(m, n) = O(g(m, n)), n \to \infty, m \to \infty

s'il existe

K > 0, N ⩾ max(m_0, n_0)

tels que pour tout

n

m \in ℕ, min(n, m) ⩾ N

, on a

|f(m, n)| ⩽ K|g(m, n)|

À titre d'exemple, on va effectuer une majoration du coût du produit de deux polynômes. On va au préalable admettre les résultats suivants : soit

A = \sum_(0 ⩽ i ⩽ n)a_i X^i

B = \sum_(0 ⩽ j ⩽ m)b_j X^j \in K[X]

avec

a_n b_m \neq 0, λ \in K

la multiplication de $A$ par un monôme $X^k, k \in ℕ$ , n'a pas de coût arithmétique (le polynôme obtenu est $\sum_(0 ⩽ i ⩽ n)a_i X^(i + k))$ ;
la multiplication de $A$ par $λ$ coûte au plus $degA + 1$ multiplications dans $K$ (le polynôme obtenu est $\sum_(0 ⩽ i ⩽ n)(λa_i)X^i)$ ;
l'addition de $A$ et $B$ coûte au plus $min(degA, degB) + 1$ additions dans $K$ (supposons $n ⩾ m$ , on a $A + B = \sum_(0 ⩽ k ⩽ n)c_k X^k$ avec $c_k = a_k + b_k$ pour $k ⩽ m$ et $c_k = a_k$ sinon).
Soit deux polynômes, $A$ et $B \in K[X]$ . On peut calculer le produit, noté $C$ , de $A$ et $B$ de la manière élémentaire suivante :

Algorithme 1
Entrée : $n$ et $m \in \mathbb{N}, A=\sum_{0 \leqslant i \leqslant n} a_{i} X^{i}$ et $B=\sum_{0 \leqslant j \leqslant m} b_{j} X^{j} \in \mathbf{K}[X]$.
Sortie : Un polynôme $C \in \mathbf{K}[X]$ égal au produit de $A$ et $B$.
1. $C_{0} \longleftarrow \sum_{0 \leqslant j \leqslant m} a_{0} b_{j} X^{j}$
2. Pour $i=1, \ldots, n$, faire
            $S_{i} \longleftarrow\left(a_{i} X^{i}\right) B$
            $C_{i} \longleftarrow C_{i-1}+S_{i}$
4. Renvoyer $C=C_{n}$

Le symbole

⟵

dans un algorithme signifie «prend la valeur de». L'expression <<renvoyer XXX» dans un algorithme signifie «sortir de l'algorithme et retourner XXX».

L'étape 1 coûte au plus

m + 1

produits (les

a_0 b_j

pour

j = 0, \dots, m

) dans

K

.
Soit

i \in {1, \dots, n}

, on constate que

S_i = \sum_(i ⩽ j ⩽ i + m)a_i b_(j - i)X^j

et on montre par récurrence que

degC_(i - 1) ⩽ m + i - 1

. On écrit donc

C_(i - 1) = \sum_(0 ⩽ j ⩽ m + i - 1)c_(i - 1, j)X^j

. Le polynôme

C_i = C_(i - 1) + S_i

est donc de la forme

\sum_(0 ⩽ j ⩽ m + i)c_(i, j)X^j

avec

c_(i, j) = {c_(i − 1, j) pour j = 0, …, i − 1,; c_(i − 1, j) + a_i b_(j − i) pour j = i, …, m + i − 1,; a_i b_m pour j = m + i

Donc, pour

j = 0, \dots, i - 1

, il n'y a pas de coût arithmétique. Pour

j = i, \dots, m + i - 1

, on calcule au plus un produit et une addition dans

K

et pour

j = m + i

, on effectue au plus une multiplication. L'étape 3 a donc un coût total d'au plus

m + 1

multiplications et

m

additions dans

K

L'étape 2 consistant à répéter

n

fois l'étape 3 , son exécution nécessite au plus

n(m + 1)

multiplications et

nm

additions dans

K

Il y a donc un coût total d'au plus

m + 1 + n(m + 1) + nm = (m + 1)(n + 1) + nm

opérations arithmétiques dans

K

. Comme

(m + 1)(n + 1) + nm ⩽ (2m)(2n) + nm = 5mn

dès que

min(n, m) ⩾ 1

, on en déduit que le nombre total d'opérations arithmétiques sur

K

est en

O(mn)

Partie 2 : Décodage d'une famille de codes

Dans cette partie, l'alphabet sera le corps

K

.
Pour

n \in ℕ, n ⩾ 1

, l'ensemble

A^n

est donc

K^n

, l'espace vectoriel sur

K

muni des opérations standard + et

\cdot

définies par :

pour $x = (x_1, \dots, x_n)$ et $y = (y_1, \dots, y_n)$ dans $A^n$ , on a $x + y = (x_1 + y_1, \dots, x_n + y_n)$ ;
pour $x = (x_1, \dots, x_n)$ dans $A^n$ et $λ \in K$ , on a $λ \cdot x = (λx_1, \dots, λx_n)$ .

x \in A^n

, on notera

w_H(x) = δ_H(x, 0)

.
Soit

k \in ℕ, k ⩾ 1

, un code linéaire de longueur

n

sur

K

et de dimension

k

(on dira un code

[n, k])

est un sous-espace vectoriel de

K^n

de dimension

k

Question 2.1. Soit un code linéaire

C, w_H

est-elle une norme sur le

K

-espace vectoriel

C

? Justifier votre réponse.

Question 2.2. Démontrer que la distance minimale d'un code linéaire

C

est égale au minimum de

w_H(x)

, où

x

décrit

C∖{0}

Question 2.3. Borne de Singleton. Démontrer que tout code

[n, k]

de distance minimale

d

vérifie l'inégalité

k + d ⩽ n + 1

. On pourra faire intervenir le sous-ensemble des points de

K^n

dont les

n - d + 1

premières composantes sont nulles.

Soit

n

un entier naturel non nul. Soit

α_1, \dots, α_n \in K

, deux à deux distincts. La fonction d'évaluation associée à

α = (α_1, \dots, α_n)

est

ev_α : K[X], \to K^n; f, \mapsto (f(α_1), \dots, f(α_n)).

Soit

k \in ℕ, 1 ⩽ k ⩽ n

, soit

L_k = {f ∈ K[X]; degf < k}.

Soit

RS_(α, k)

défini par

RS_(α, k) = ev_α(L_k) = {ev_α(f); f ∈ L_k}

Question 2.4. Démontrer que

RS_(α, k)

est un code

[n, k]

Question 2.5.

(a). Démontrer que, pour tout

f ∈ L_k∖{0}

, le vecteur

ev_α(f)

a au plus

k - 1

composantes nulles.
(b). Déterminer la distance minimale de

RS_(α, k)

. Que remarque-t-on ?

Nous allons maintenant étudier un procédé de décodage des codes

RS_(α, k)

. On se donne un entier

e

tel que

0 < e < (n - k + 1)/2

Algorithme 2
Entrée : Le mot reçu $y=\left(y_{1}, \ldots, y_{n}\right) \in \mathbf{K}^{n}$
Sortie : Un polynôme $f \in \mathbf{K}[X]$ tel que $\operatorname{deg} f<k$ et $\delta_{H}\left(\mathrm{ev}_{\alpha}(f), y\right) \leqslant e$ ou «échec»
1. Calculer $E, F \in \mathbf{K}[X]$ tels que
    a. $F\left(\alpha_{i}\right)-y_{i} E\left(\alpha_{i}\right)=0$ pour tout $i \in\{1, \ldots, n\}$
    b. $\operatorname{deg} F<e+k$
    c. $\operatorname{deg} E=e$ et $E$ est unitaire
    Si de tels polynômes n'existent pas, renvoyer <<échec>>
2. Si $E$ ne divise pas $F$, renvoyer «échec». Sinon, calculer $f=F / E$.
3. Si $\delta_{H}\left(\mathrm{ev}_{\alpha}(f), y\right)>e$, renvoyer <<échec>>. Sinon, renvoyer $f$.

Question 2.6. Soit

f \in K[X]

tel que

degf < k

δ_H(ev_α(f), y) ⩽ e

, exhiber un couple

(E, F) \in K[X]^2

vérifiant les conditions 1a, 1b et 1c de l'Algorithme 2, et tel que

f = F/E

Question 2.7. Soit (

E_1, F_1

) et (

E_2, F_2

) deux paires de polynômes satisfaisant les conditions 1a, 1b et 1c de l'Algorithme 2. Démontrer que

(F_1(X))/(E_1(X)) = (F_2(X))/(E_2(X))

Question 2.8. On suppose que l'on sait effectuer l'étape 1 de l'Algorithme 2. Démontrer que s'il existe

f \in K[X]

tel que

degf < k

δ_H(ev_α(f), y) ⩽ e

, l'Algorithme 2 le calcule et renvoie «échec» sinon.

Soit

n \in ℕ

. On dira qu'un système d'équations linéaires à coefficients dans

K

est de taille au plus

n

si son nombre d'inconnues et son nombre d'équations sont tous deux inférieurs ou égaux à

n

. On admet que la résolution d'un système d'équations linéaires à coefficients dans

K

de taille au plus

n

peut s'effectuer en un coût

O(n^3)

d'opérations arithmétiques sur

K

Question 2.9. Démontrer que le calcul effectif de polynômes

E

F

vérifiant les conditions 1a, 1b et 1c de l'Algorithme 2 peut se ramener à la résolution d'un système d'équations linéaires à coefficients dans

K

, que l'on explicitera, de taille au plus

n

P

est un polynôme, on notera

cd(P)

son coefficient dominant.

Algorithme 3
Entrée : $A=\sum_{0 \leqslant i \leqslant n} a_{i} X^{i}$ et $B=\sum_{0 \leqslant i \leqslant m} b_{i} X^{i} \in \mathbf{K}[X]$ avec $b_{m} \neq 0$
Sortie : Le couple $(Q, R) \in \mathbf{K}[X]$ tel que $A=B Q+R$ et $\operatorname{deg} R<m$
1. Si $n<m$, renvoyer $Q=0$ et $R=A$
2. $R \longleftarrow A, u \longleftarrow b_{m}^{-1}$
3. pour $i=n-m, n-m-1, \ldots, 0$, faire
        si $\operatorname{deg} R=m+i$ alors $q_{i} \longleftarrow \operatorname{cd}(R) u, R \longleftarrow R-q_{i} X^{i} B$
            sinon $q_{i} \longleftarrow 0$
5. Renvoyer $Q=\sum_{0 \leqslant i \leqslant n-m} q_{i} X^{i}$ et $R$

Question 2.10. Division euclidienne. Soit

n, m \in ℕ, A

B \in K[X]

avec

degA = n

degB = m

.
(a). Démontrer qu'un couple

(Q, R) \in K[X]^2

tel que

A = BQ + R

degR < m

est unique.
(b). Démontrer que l'Algorithme 3 retourne bien la sortie annoncée.
(c). Démontrer que, si

n ⩾ m

, cet algorithme nécessite au plus

(2m + 1)(n - m + 1) + 1

opérations arithmétiques dans

K

Les polynômes

Q

R

renvoyés par l'Algorithme 3 seront appelés respectivement quotient et reste de la division euclidienne de

A

par

B

Question 2.11. Démontrer que l'Algorithme 2 peut s'exécuter en un nombre

O(n^3)

d'opérations arithmétiques sur

K

Partie 3 : Décodage via l'interpolation et l'algorithme d'Euclide étendu

On rappelle que, pour tous

A

B \in K[X]

, non tous deux nuls, un polynôme

D \in K[X]

est un pgcd (plus grand commun diviseur) de

A

B

s'il satisfait aux deux conditions :

$D$ divise $A$ et $B$ ;
si $E \in K[X]$ divise $A$ et $B$ , alors $E$ divise $D$ .

Un pgcd de deux polynômes est donc défini à une constante multiplicative de

K

près. On notera

pgcd(A, B)

le pgcd unitaire de

A

B

Algorithme 4 Algorithme d'Euclide étendu.
Entrée : $A=\sum_{0 \leqslant i \leqslant n} a_{i} X^{i}$ et $B=\sum_{0 \leqslant i \leqslant m} b_{i} X^{i} \in \mathbf{K}[X]$ tels que $A B \neq 0$
Sortie : Un entier $\ell \in \mathbb{N}$, quatre suites finies $\left(Q_{i}\right)_{1 \leqslant i \leqslant \ell},\left(R_{i}\right)_{0 \leqslant i \leqslant \ell+1},\left(S_{i}\right)_{0 \leqslant i \leqslant \ell+1},\left(T_{i}\right)_{0 \leqslant i \leqslant \ell+1}$
d'éléments de $\mathbf{K}[X]$
1. $R_{0} \longleftarrow A, S_{0} \longleftarrow 1, T_{0} \longleftarrow 0$,
    $R_{1} \longleftarrow B, S_{1} \longleftarrow 0, T_{1} \longleftarrow 1$
2. $i \longleftarrow 1$,
    tant que $R_{i} \neq 0$, faire
3. $\quad\left(Q_{i}, R_{i+1}\right) \longleftarrow$ Algorithme 3 appliqué à $\left(R_{i-1}, R_{i}\right)$
        $S_{i+1} \longleftarrow S_{i-1}-Q_{i} S_{i}$
        $T_{i+1} \longleftarrow T_{i-1}-Q_{i} T_{i}$
        $i \longleftarrow i+1$
4. Renvoyer $\ell=i-1$ et les suites $\left(Q_{i}\right)_{1 \leqslant i \leqslant \ell},\left(R_{i}\right)_{0 \leqslant i \leqslant \ell+1},\left(S_{i}\right)_{0 \leqslant i \leqslant \ell+1},\left(T_{i}\right)_{0 \leqslant i \leqslant \ell+1} \in \mathbf{K}[X]$

L'algorithme d'Euclide étendu fournit notamment un pgcd des deux polynômes en entrée et les coefficients de Bézout correspondants, à savoir respectivement les polynômes

R_ℓ, S_ℓ

T_ℓ

, comme on va le voir.

On notera

M_(2, 1)(K(X))

K

-espace vectoriel des matrices à deux lignes et une colonne à coefficients dans

K(X)

M_(2, 2)(K(X))

K

-espace vectoriel et l'anneau des matrices à deux lignes et deux colonnes à coefficients dans

K(X)

On reprend les notations de l'Algorithme 4 et l'on introduit les matrices :

U_0 = (S_0, T_0; S_1, T_1) \in M_(2, 2)(K(X)), W_i = (0, 1; 1, - Q_i) \in M_(2, 2)(K(X)) pour tout 1 ⩽ i ⩽ ℓ

U_i = W_i\dotsW_1 U_0 \in M_(2, 2)(K(X)) pour tout 0 ⩽ i ⩽ ℓ.

Question 3.1. En reprenant les notations de l'Algorithme 4 , démontrer que, pour tout

0 ⩽ i ⩽ ℓ

, on a
(a).

U_i(A/B) = ((R_i)/(R_(i + 1)))

,
(b).

U_i = (S_i, T_i; S_(i + 1), T_(i + 1))

S_i A + T_i B = R_i

(l'égalité est vraie aussi pour

i = ℓ + 1

),
(c).

S_i T_(i + 1) - S_(i + 1)T_i = (- 1)^i

,
(d).

pgcd(A, B) = pgcd(R_i, R_(i + 1)) = R_ℓ/cd(R_ℓ)

, où

cd(R_ℓ)

désigne le coefficient dominant de

R_ℓ

Question 3.2. En reprenant les notations de l'Algorithme 4 et en supposant

degA ⩾ degB

, démontrer que

degS_i, = \sum_(2 ⩽ j < i)degQ_j = degR_1 - degR_(i - 1) pour tout 2 ⩽ i ⩽ ℓ + 1,; degT_i, = \sum_(1 ⩽ j < i)degQ_j = degR_0 - degR_(i - 1) pour tout 1 ⩽ i ⩽ ℓ + 1.

Question 3.3. Soit

n, m \in ℕ, A

B \in K[X]

avec

degA = n

degB = m

. Démontrer que l'exécution de l'Algorithme 4 nécessite au plus

O(nm)

opérations arithmétiques dans

K

Question 3.4. Soit

M \in K[X]

de degré

n > 0, P \in K[X]

tel que

degP < n

. Soit

k \in {0, \dots, n}

, déterminer un couple

(R, T) \in K[X]^2

tel que

T \neq 0 et R \equiv TP modM, degR < k, degT ⩽ n - k.

On admet dans la suite du problème que l'évaluation d'un polynôme de

K[X]

de degré au plus

t

peut se faire en

O(t)

opérations arithmétiques sur

K

Algorithme 5
Entrée : $n$ un entier naturel non nul, $u_{0}, u_{1}, \ldots, u_{n-1}$ distincts deux à deux, $v_{0}, v_{1}, \ldots, v_{n-1} \in \mathbf{K}$
Sortie : L'unique $P \in \mathbf{K}[X]$ tel que $\operatorname{deg} P \leqslant n-1$ et $P\left(u_{i}\right)=v_{i}$ pour $i=0, \ldots, n-1$
1. $A \longleftarrow 1, P \longleftarrow 0$
2. Pour $i=0, \ldots, n-1$, faire $A \longleftarrow\left(X-u_{i}\right) A$
3. Pour $i=0, \ldots, n-1$, faire
4. $\quad A_{i} \longleftarrow$ quotient de la division euclidienne de $A$ par $X-u_{i}$
    $\alpha_{i} \longleftarrow A_{i}\left(u_{i}\right)$
    $P \longleftarrow P+v_{i} A_{i} / \alpha_{i}$
5. Renvoyer $P$

Question 3.5. Soit

n

un entier naturel non nul,

u_0, u_1, \dots, u_(n - 1), v_0, v_1, \dots, v_(n - 1) \in K

. On suppose les

u_i

deux à deux distincts.
(a). Démontrer qu'un polynôme

P \in K[X]

tel que

degP ⩽ n - 1

P(u_i) = v_i

pour

i = 0, \dots, n - 1

, est unique.
(b). Démontrer que l'Algorithme 5 calcule bien la sortie annoncée.
(c). Démontrer que le nombre d'opérations arithmétiques effectuées dans

K

pour calculer le polynôme

P

, sortie de l'Algorithme 5, est en

O(n^2)

Question 3.6. Soit

n

un entier naturel non nul, soit

k \in {0, \dots, n}

. Soit

u_0, \dots, u_(n - 1) \in K

distincts deux à deux,

v_0, \dots, v_(n - 1) \in K

. On veut déterminer un couple

(R, T) \in K[X]^2

tel que

{R(u_i) = T(u_i)v_i pour tout 0 ⩽ i < n; degR < k; T ≠ 0 et degT ⩽ n − k

(a). Démontrer que résoudre (2) revient à résoudre (1) pour un couple (

M, P

) que l'on explicitera.
(b). En déduire une solution de (2).

Question 3.7. Démontrer que l'Algorithme 2 peut s'exécuter en un nombre

O(n^2)

d'opérations arithmétiques sur

K

Partie 4 : Borne de la programmation linéaire

On travaille dans toute cette partie avec des codes définis sur un alphabet

A

de cardinal

q \in ℕ, q ⩾ 2

. On se donne aussi un entier naturel non nul

n

On définit la taille d'un code comme le nombre de mots de ce code (précisons que le terme <taille> employé dans cette partie n'a pas de rapport avec celui employé dans la Partie 2). Soit

C

un code de longueur

n

et de taille

M

, on écrira que

C

est un (

n, M

)-code. Si de plus,

C

est de distance minimale

d

, on écrira que

C

est un

(n, M, d)

-code.

On notera

A_q(n, d)

la plus grande taille possible d'un code sur

A

de longueur

n

et de distance minimale

d

, i.e.

A_q(n, d) = max{M; il existe un (n, M, d)-code sur A}.

Le but de cette partie est d'établir une borne sur

A_q(n, d)

appelée borne de la programmation linéaire. Nous déduirons de cette borne une autre borne classique en théorie des codes.

Nous allons nous servir d'une certaine famille de polynômes (dans cette partie, on confondra polynôme et fonction polynomiale). Avant de la définir, nous allons généraliser la notion de coefficient binomial comme suit : si

y

m

sont deux nombres réels quelconques, on pose

(y/m) = {(y(y - 1)\dots(y - m + 1))/(m!) si m \in ℕ, m \neq 0; 1 si m = 0; 0 sinon.

On vérifie aisément que cette définition prolonge bien celle rappelée dans le préambule.
Pour tout entier naturel

k

, le polynôme

K_k(x)

, où

x

est une variable de

ℝ

, est donné par

K_k(x) = \sum_(j = 0)^k(- 1)^j(x/j)((n - x)/(k - j))(q - 1)^(k - j)

On rappelle que pour tous

u, v \in ℝ

, avec

|u| < 1

, on a

(1 + u)^v = \sum_(i = 0)^(+ \infty)(v/i)u^i

Question 4.1. Établir les propriétés suivantes.
(a). Soit

z \in ℝ, |z| < 1/(q - 1)

, on a

\sum_(k = 0)^(+ \infty)K_k(x)z^k = (1 + (q - 1)z)^(n - x)(1 - z)^x.

(b). On a, pour tout

k \in ℕ

K_k(x) = \sum_(j = 0)^k(- 1)^j q^(k - j)((n - k + j)/j)((n - x)/(k - j)).

(c). Pour tout

k \in ℕ, K_k(x)

est un polynôme de degré

k

, avec un coefficient dominant égal à

(- q)^k/k!

et un terme constant

K_k(0) = (n/k)(q - 1)^k

.
(d). Pour tous

k, ℓ \in ℕ

, on a

\sum_(i = 0)^n(n/i)(q - 1)^i K_k(i)K_ℓ(i) = δ_(kℓ)(n/k)(q - 1)^k q^n

où

δ_(kℓ)

est le symbole de Kronecker défini par

δ_(kℓ) = 1

k = ℓ

et 0 sinon. Indication : on pourra multiplier les deux membres de l'égalité par

y^k z^ℓ

, avec

y, z \in ] - 1, 1[

, et sommer sur tous les

k, ℓ ⩾ 0

, en expliquant pourquoi cette opération est licite.
(e). On a, pour tous

k, i \in ℕ

(q - 1)^i(n/i)K_k(i) = (q - 1)^k(n/k)K_i(k).

(f). On a, pour tous

k, ℓ \in ℕ

\sum_(i = 0)^n K_ℓ(i)K_i(k) = δ_(kℓ)q^n.

(g). On a, pour tout

m \in ℕ

\sum_(k = 0)^m((n - k)/(n - m))K_k(x) = q^m((n - x)/m).

Indication : utiliser (b).
(h). Soit

r \in ℕ

, tout polynôme

f(x)

de degré

r

peut s'exprimer sous la forme

f(x) = \sum_(k = 0)^r f_k K_k(x)

où

f_k = q^(- n)\sum_(i = 0)^n f(i)K_i(k)

Soit

C

(n, M)

-code sur

A

. On définit pour tout

i \in ℕ, 0 ⩽ i ⩽ n

A_i(C) = 1/Mcard{(u, v) ∈ C × C : d(u, v) = i}.

La suite finie

(A_i(C))_(i = 0)^n

est appelée la distribution des distances de

C

Remarque. La distribution des distances de

C

ne dépend pas de l'alphabet mais seulement du cardinal de l'alphabet. Nous supposerons donc à présent que l'alphabet

A

est l'anneau

ℤ/qℤ

Comme dans la Partie 2, on note

w_H(x) = δ_H(x, 0)

pour tout

x \in (ℤ/qℤ)^n

Question 4.2. Soit

ζ

une racine primitive

q

-ième de l'unité dans

ℂ

, i.e.

ζ^q = 1

mais

ζ^j \neq 1

pour tout

j \in ℕ, 1 ⩽ j ⩽ q - 1

. On suppose que

u \in (ℤ/qℤ)^n

est un mot tel que

w_H(u) = i

. Démontrer que

\sum_(v \in (ℤ/qℤ)^n; w_H(v) = k)ζ^(u \cdot v) = K_k(i)

où, si

u = (u_1, \dots, u_n)

v = (v_1, \dots, v_n)

, on a

u \cdot v = \sum_(j = 1)^n u_j v_j

(on confond

u_j

v_j

avec leurs représentants dans

{0, \dots, q - 1}

: c'est bien défini puisque

ζ^q = 1

Question 4.3. Soit

C

un code de longueur

n

sur l'alphabet

ℤ/qℤ

. Démontrer que

\sum_(i = 0)^n A_i(C)K_k(i) ⩾ 0

pour tout

k \in ℕ, 0 ⩽ k ⩽ n

Question 4.4. Borne de la programmation linéaire (première version). Pour tous entiers

n

d

tels que

1 ⩽ d ⩽ n

, démontrer que

A_q(n, d) ⩽ max{∑_(i = 0)^n A_i; A_0 = 1, A_i = 0 pour 1 ⩽ i < d, A_i ⩾ 0 pour 0 ⩽ i ⩽ n; ∑_(i = 0)^n A_i K_k(i) ⩾ 0 pour 0 ⩽ k ⩽ n}

Question 4.5. Borne de la programmation linéaire (seconde version). Pour tous entiers

n

d

tels que

1 ⩽ d ⩽ n

, soit

f(x) = 1 + \sum_(k = 1)^n f_k K_k(x)

un polynôme tel que

f_k ⩾ 0

pour tout

1 ⩽ k ⩽ n

f(i) ⩽ 0

pour

d ⩽ i ⩽ n

. Démontrer que

A_q(n, d) ⩽ f(0)

Question 4.6. Borne de Singleton. Déduire de la question précédente que pour tous entiers

n

d

tels que

1 ⩽ d ⩽ n

, on a

A_q(n, d) ⩽ q^(n - d + 1)

Remarque. Il s'agit bien de la même borne que dans la Partie 2 : dans la pratique, les codes

RS_(α, k)

sont considérés sur des corps de cardinal

q

, où

q

est une puissance d'un nombre premier

p

Pas de description pour le moment

Commentaires• ENS Informatique Fondamentale (Maths Info) MP 2011

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...