J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

ENS Informatique Fondamentale (Maths Info) MP 2011

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Logo ens
🔗 Explorer
Banque
X-ENS
Année
2011
Filière
MP
Matière
Maths Info
X-ENS MPX-ENS 2011MP Maths InfoMaths Info 2011
2025_08_29_846f14ef1c48b19605d0g

É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 ou . 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 est un nombre réel, désignera la partie entière de , i.e. le plus grand entier relatif inférieur ou égal à . Si désigne un ensemble fini, on notera son nombre d'éléments. Soit et deux entiers relatifs, on définit
Une somme et un produit indexés sur un ensemble vide vaudront, comme d'habitude, respectivement 0 et 1 .

Partie 1 : Codes correcteurs

Soit un ensemble non vide, un entier naturel non nul. On désignera par l'ensemble . Les éléments de seront appelés mots.
Si et désignent deux mots de , on note
Question 1.1. Démontrer que définit une distance sur .
Dans la suite, sera notée plus simplement .
Un code sur de longueur est un sous-ensemble de . Dans tout le problème, un code comportera toujours au moins deux éléments distincts. L'ensemble sera appelé alphabet, l'entier sera appelé la longueur du code et les éléments de seront appelés les mots du code.
Soit un entier naturel. On dit qu'un code de longueur sur un alphabet vérifie la condition de décodage d'ordre si pour tout , il existe au plus un mot tel que .
La distance minimale d'un code est l'entier
Question 1.2. Justifier que est bien définie.
Question 1.3. Soit un code et un entier naturel. Montrer que si alors vérifie la condition de décodage d'ordre .
La capacité de correction d'un code est l'entier , où désigne la distance minimale de .
Dans la pratique, un mot d'un code de longueur est envoyé via un canal de communication et l'on note le mot de reçu. Le but est, lorsque c'est possible, de retrouver à partir de : tout moyen permettant d'effectuer une telle opération est appelé décodage.
On suppose fini pour toute la suite de la Partie 1.
Question 1.4. Soit , on désigne par la boule fermée de centre et de rayon pour la distance , i.e. .
(a). Pour tout , on désigne par la sphère centrée en et de rayon , i.e. . Démontrer que
(b). En déduire que
Question 1.5. Soit un code de longueur sur un alphabet . Démontrer qu'il existe un plus petit rayon tel que l'ensemble des boules de rayon centrées en chaque mot du code forme un recouvrement de . On note ce rayon.

Question 1.6.

(a). Soit un code de longueur sur un alphabet , de capacité de correction . Démontrer que
(b). Soit un code de longueur sur un alphabet . Montrer de même que

Intermède : notations et définitions

Dans les deux prochaines parties, désignera le corps des nombres réels ou le corps des nombres complexes désignera l'anneau des polynômes à coefficients dans et
le corps des fractions rationnelles à coefficients dans . Ces deux ensembles sont aussi des espaces vectoriels. Un élément d'un de ces deux ensembles pourra aussi être noté . Un polynôme à coefficients dans est dit unitaire si son coefficient dominant, i.e. le coefficient de son terme de plus haut degré, vaut 1 . On convient que deg .
Soit et . On dit que divise s'il existe tel que . On notera si divise .
Il vous sera demandé d'estimer l'efficacité de certaines procédures de calculs. On le fera comme suit. Soit désignant ou , on supposera que le coût d'une opération arithmétique (addition, soustraction, multiplication, division) sur est unitaire. On devra donc estimer, ou au moins majorer, le nombre d'opérations arithmétiques sur qui seront effectuées au cours de l'exécution des algorithmes.
Soit et deux suites réelles définies à partir d'un certain rang . On écrit que
s'il existe et tels que pour tout , on a .
On généralise cette notation à des fonctions de deux arguments : soit et deux entiers fixés, si et sont deux fonctions à valeurs réelles définies en tout couple , . On écrit que
s'il existe tels que pour tout et , on a .
À 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 et avec ,
  • la multiplication de par un monôme , n'a pas de coût arithmétique (le polynôme obtenu est ;
  • la multiplication de par coûte au plus multiplications dans (le polynôme obtenu est ;
  • l'addition de et coûte au plus additions dans (supposons , on a avec pour et sinon).
    Soit deux polynômes, et . On peut calculer le produit, noté , de et 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 produits (les pour ) dans .
Soit , on constate que et on montre par récurrence que . On écrit donc . Le polynôme est donc de la forme avec
Donc, pour , il n'y a pas de coût arithmétique. Pour , on calcule au plus un produit et une addition dans et pour , on effectue au plus une multiplication. L'étape 3 a donc un coût total d'au plus multiplications et additions dans .
L'étape 2 consistant à répéter fois l'étape 3 , son exécution nécessite au plus multiplications et additions dans .
Il y a donc un coût total d'au plus opérations arithmétiques dans . Comme dès que , on en déduit que le nombre total d'opérations arithmétiques sur est en .

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

Dans cette partie, l'alphabet sera le corps .
Pour , l'ensemble est donc , l'espace vectoriel sur muni des opérations standard + et définies par :
  • pour et dans , on a ;
  • pour dans et , on a .
Si , on notera .
Soit , un code linéaire de longueur sur et de dimension (on dira un code est un sous-espace vectoriel de de dimension .
Question 2.1. Soit un code linéaire est-elle une norme sur le -espace vectoriel ? Justifier votre réponse.
Question 2.2. Démontrer que la distance minimale d'un code linéaire est égale au minimum de , où décrit .
Question 2.3. Borne de Singleton. Démontrer que tout code de distance minimale vérifie l'inégalité . On pourra faire intervenir le sous-ensemble des points de dont les premières composantes sont nulles.
Soit un entier naturel non nul. Soit , deux à deux distincts. La fonction d'évaluation associée à est
Soit , soit
Soit défini par
Question 2.4. Démontrer que est un code .

Question 2.5.

(a). Démontrer que, pour tout , le vecteur a au plus composantes nulles.
(b). Déterminer la distance minimale de . Que remarque-t-on ?
Nous allons maintenant étudier un procédé de décodage des codes . On se donne un entier tel que .
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 tel que et , exhiber un couple vérifiant les conditions 1a, 1b et 1c de l'Algorithme 2, et tel que .
Question 2.7. Soit ( ) et ( ) deux paires de polynômes satisfaisant les conditions 1a, 1b et 1c de l'Algorithme 2. Démontrer que
Question 2.8. On suppose que l'on sait effectuer l'étape 1 de l'Algorithme 2. Démontrer que s'il existe tel que et , l'Algorithme 2 le calcule et renvoie «échec» sinon.
Soit . On dira qu'un système d'équations linéaires à coefficients dans est de taille au plus si son nombre d'inconnues et son nombre d'équations sont tous deux inférieurs ou égaux à . On admet que la résolution d'un système d'équations linéaires à coefficients dans de taille au plus peut s'effectuer en un coût d'opérations arithmétiques sur .
Question 2.9. Démontrer que le calcul effectif de polynômes et 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 , que l'on explicitera, de taille au plus .
Si est un polynôme, on notera 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 et avec et .
(a). Démontrer qu'un couple tel que et est unique.
(b). Démontrer que l'Algorithme 3 retourne bien la sortie annoncée.
(c). Démontrer que, si , cet algorithme nécessite au plus opérations arithmétiques dans .
Les polynômes et renvoyés par l'Algorithme 3 seront appelés respectivement quotient et reste de la division euclidienne de par .
Question 2.11. Démontrer que l'Algorithme 2 peut s'exécuter en un nombre d'opérations arithmétiques sur .

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

On rappelle que, pour tous et , non tous deux nuls, un polynôme est un pgcd (plus grand commun diviseur) de et s'il satisfait aux deux conditions :
  • divise et ;
  • si divise et , alors divise .
Un pgcd de deux polynômes est donc défini à une constante multiplicative de près. On notera le pgcd unitaire de et .
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 et , comme on va le voir.
On notera le -espace vectoriel des matrices à deux lignes et une colonne à coefficients dans et le -espace vectoriel et l'anneau des matrices à deux lignes et deux colonnes à coefficients dans .
On reprend les notations de l'Algorithme 4 et l'on introduit les matrices :
et
Question 3.1. En reprenant les notations de l'Algorithme 4 , démontrer que, pour tout , on a
(a). ,
(b). et (l'égalité est vraie aussi pour ),
(c). ,
(d). , où désigne le coefficient dominant de .
Question 3.2. En reprenant les notations de l'Algorithme 4 et en supposant , démontrer que
Question 3.3. Soit et avec et . Démontrer que l'exécution de l'Algorithme 4 nécessite au plus opérations arithmétiques dans .
Question 3.4. Soit de degré tel que . Soit , déterminer un couple tel que
On admet dans la suite du problème que l'évaluation d'un polynôme de de degré au plus peut se faire en opérations arithmétiques sur .
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 un entier naturel non nul, . On suppose les deux à deux distincts.
(a). Démontrer qu'un polynôme tel que et pour , 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 pour calculer le polynôme , sortie de l'Algorithme 5, est en .
Question 3.6. Soit un entier naturel non nul, soit . Soit distincts deux à deux, . On veut déterminer un couple tel que
(a). Démontrer que résoudre (2) revient à résoudre (1) pour un couple ( ) 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 d'opérations arithmétiques sur .

Partie 4 : Borne de la programmation linéaire

On travaille dans toute cette partie avec des codes définis sur un alphabet de cardinal . On se donne aussi un entier naturel non nul .
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 un code de longueur et de taille , on écrira que est un ( )-code. Si de plus, est de distance minimale , on écrira que est un -code.
On notera la plus grande taille possible d'un code sur de longueur et de distance minimale , i.e.
Le but de cette partie est d'établir une borne sur 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 et sont deux nombres réels quelconques, on pose
On vérifie aisément que cette définition prolonge bien celle rappelée dans le préambule.
Pour tout entier naturel , le polynôme , où est une variable de , est donné par
On rappelle que pour tous , avec , on a .
Question 4.1. Établir les propriétés suivantes.
(a). Soit , on a
(b). On a, pour tout ,
(c). Pour tout est un polynôme de degré , avec un coefficient dominant égal à et un terme constant .
(d). Pour tous , on a
où est le symbole de Kronecker défini par si et 0 sinon. Indication : on pourra multiplier les deux membres de l'égalité par , avec , et sommer sur tous les , en expliquant pourquoi cette opération est licite.
(e). On a, pour tous ,
(f). On a, pour tous ,
(g). On a, pour tout ,
Indication : utiliser (b).
(h). Soit , tout polynôme de degré peut s'exprimer sous la forme où .
Soit un -code sur . On définit pour tout ,
La suite finie est appelée la distribution des distances de .
Remarque. La distribution des distances de ne dépend pas de l'alphabet mais seulement du cardinal de l'alphabet. Nous supposerons donc à présent que l'alphabet est l'anneau .
Comme dans la Partie 2, on note pour tout .
Question 4.2. Soit une racine primitive -ième de l'unité dans , i.e. mais pour tout . On suppose que est un mot tel que . Démontrer que
où, si et , on a (on confond et avec leurs représentants dans : c'est bien défini puisque ).
Question 4.3. Soit un code de longueur sur l'alphabet . Démontrer que
pour tout .
Question 4.4. Borne de la programmation linéaire (première version). Pour tous entiers et tels que , démontrer que
Question 4.5. Borne de la programmation linéaire (seconde version). Pour tous entiers et tels que , soit un polynôme tel que pour tout et pour . Démontrer que .
Question 4.6. Borne de Singleton. Déduire de la question précédente que pour tous entiers et tels que , on a .
Remarque. Il s'agit bien de la même borne que dans la Partie 2 : dans la pratique, les codes sont considérés sur des corps de cardinal , où est une puissance d'un nombre premier .
ENS Informatique Fondamentale (Maths Info) MP 2011 - Version Web LaTeX | WikiPrépa | WikiPrépa