X Informatique MP 2007

ÉCOLE POLYTECHNIQUE FILIÈRE MP
OPTION INFORMATIQUE
CONCOURS D'ADMISSION 2007

COMPOSITION D'INFORMATIQUE

(Durée : 4 heures)

L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.

On attachera une grande importance a la concision, a la clarté, et a la 
précision de la rédaction.

***

Codage Reed-Solomon

Ce problème s'intéresse aux codes de correction d'erreurs de Reed-Solomon. On 
souhaite trans--
mettre un message au travers d'un canal de communication bruite" : les données 
émises sont modi--
fiées par quelques erreurs lorsqu'elles sont reçues. Pour permettre néanmoins 
la transmission fiable
d'un message, la donnée émise est un codage du message, plus long que le 
message lui-même.
La redondance ainsi ajoutée permet de corriger ensuite des erreurs qui peuvent 
apparaître lors de la
transmission. Les codes appelés codes de Reed-Solomon ont de nombreuses 
applications : les CDs,
DVDs, les systèmes ADSL, ou encore de nombreuses sondes spatiales utilisent des 
codes bâtis autour
des codes de Reed--Solomon.

Le préambule donne les définitions communes a l'ensemble de l'énoncé, et 
introduit les codes
de Reed-Solomon. La partie I s'attache au calcul du codage d'un message. La 
partie Il définit
quelques fonctions de manipulation de polynômes. La partie III poursuit cette 
étude par la mise en
oeuvre d'algorithmes de meilleure complexité. Enfin, la partie IV permet 
d'améliorer la complexité
du codage. On notera que le problème du décodage {retrouver un message original 
a partir d'une
transmission bruitée) n'est pas traité dans ce problème.

Les parties 1 a Ill peuvent être traitées indépendamment. La partie IV repose 
sur les résultats
de la partie III.

Préambule : Définitions et notations

Dans l'ensemble de l'énoncé, on fixe un nombre premier }) inférieur a 215 (de 
telle sorte que le
produit de deux entiers modulo }) soit toujours représentable par un simple 
entier positif en Caml ou
en Pascal). Les calculs liés aux codes de Reed--Solomon seront réalisés dans le 
corps le : Z/pZ des
entiers modulo p. On rappelle que l'opération << modulo >> est réalisée par 
l'opérateur mod en Caml
et en Pascal, où on suppose également disposer de la fonction inv suivante pour 
calculer l'inverse
modulo }) de tout entier a vérifiant 0 < a < p : (* Caml *) { Pascal } (donné) inv : int --> int (donné) function inv(azinteger)

: integer

Toutes les questions ayant trait a la complexité des programmes écrits 
demandent comme réponse
une borne supérieure (raisonnable) du type O() sur le nombre d'opérations dans 
le : chacune des
opérations dans le (addition, multiplication, inversion) est considérée de 
complexité 1.

1

On manipulera des listes d'entiers modulo p en les identifiant avec des 
polynômes. Ainsi la

liste de (d + 1) entiers  correspond au polynôme A(X ) : ZÎ=0 
a.;Xi de degré inférieur

ou égal a d, a coefficients dans E,. On notera couramment degA le degré d'un 
polynôme A(X )
Les listes d'entiers modulo p sont des valeurs du type poly, défini comme suit :

(* Caml *) { Pascal }
type poly = int list;; type poly = "polycoeff;
polycoeff = record

coeff: integer;

suivant: poly;

end;

En Pascal la liste vide est nil, et l'on pourra utiliser la fonction suivante 
pour construire des
listes :

{ Pascal }
function nouveauPolynome(a : integer ; (Q : poly) : poly;
var r : poly;

begin new(r); r".coeff := a. ; r".suivant := Q; nouveauPolynome := r; end;

Pour définir le codage de Reed--Solomon, on fixe deux constantes entières k et 
77. qui vérifient
O de k entiers modulo p, tandis que le codage est une liste 
B :  de
n entiers modulo p. On peut aussi voir le message comme un polynôme A(X ) de 
degré inférieur ou
égal a le -- 1. Le codage utilise comme paramètre une liste oz : {cm, . . . 
,dn_1> de n entiers modulo

p, et est calculé comme suit :

k--1
|A :  | -->|B :  | , avec b; : A(oz;) : Zou--cd 
modp.
message codage j =O

Dans les programmes qu'on écrira, on considérera les entiers k, 77. et p comme 
des constantes
globales.

Partie I. Codage de Reed-Solomon, première version

Question 1 Écrire la fonction valeur qui prend comme arguments un polynôme U a 
coefficients
dans E, et un entier a:; et qui retourne la valeur U (513) dans E, de ce 
polynôme en cet entier a:.

(* Caml *) valeur : poly --> int --> int

{ Pascal } function valeur(U : poly ; a: : integer) : integer

Question 2 Écrire la fonction codage qui prend comme arguments la liste 04 : 
(cm, . . . ,an_1> et
le polynôme A(a:) ; et qui retourne le codage de Reed--Solomon du message A.

(* Caml *) codage : poly --> poly --> poly
{ Pascal } function codage(a : poly ; A : poly) : poly

Question 3 Quelles sont les complexités des fonctions valeur et codage en 
fonction de n et k ?

Partie II. Polynômes

Dans cette partie) toutes les opérations retournent des polynômes a 
coefficients dans le.

Question 4 Écrire la fonction addition qui prend comme arguments deux polynômes 
U (X ) et
V(X ) a coefficients dans le, représentés par des listes de ÆU et EURV 
coefficients; et qui retourne
la somme de ces deux polynômes. Les coefficients du résultat sont aussi dans 
le. Déterminer la
complexité de cette fonction en fonction de ÆU et (V-

(* Caml *) addition : poly --> poly --> poly
{ Pascal } function addition(U : poly ; V : poly) : poly

Question 5 Écrire de même la fonction soustraction qui prend comme arguments 
deux poly--
nômes U (X ) et V(X ) a coefficients dans le, représentés par des listes de ÆU 
et EURV coefficients;
et qui retourne la différence U (X ) -- V(X ) Déterminer la complexité de cette 
fonction en fonction
de ËU et Ëv.

(* Caml *) soustraction : poly --> poly --> poly
{ Pascal } function soustraction(U : poly ; V : poly) : poly

Question 6 Écrire la fonction produitParScalaire qui prend comme arguments un 
polynôme
U (X )) représenté par la liste de ÆU coefficients7 et un entier 5 dans &; et 
qui retourne s >< U (X ) Donner la complexité de cette fonction en fonction de EURU. (* Caml *) produitParScalaire : poly --> int --> poly
{ Pascal } function produitParScalaire(U : poly ; s : integer) : poly

Question 7 Écrire la fonction produit qui prend comme arguments deux polynômes 
U (X ) et
V(X), représentés par des listes de ÆU et EURV coefficients; et qui retourne le 
produit de ces deux
polynômes. Déterminer la complexité de cette fonction en fonction de ÆU et (V-

(* Caml *) produit : poly --> poly --> poly
{ Pascal } function produit(U : poly ; V : poly) : poly

3

Question 8 Soit un polynôme U (X ) de degré inférieur ou égal a dU représenté 
par une liste de
ÆU : (dU + 1) entiers, et un polynôme non nul V(X ) de degré exactement égal a 
dv, représenté par
une liste de EURV : (dv + 1) entiers. Écrire la fonction division qui calcule 
le quotient de la division
euclidienne de U (X ) par V(X), noté U div V. On rappelle que le résultat de la 
division euclidienne
d'un polynôme U (X ) par un polynôme non nul V(X ) est l'unique couple (Q(X ), 
R(X )) (quotient
et reste) vérifiant :

U(X) =Q(X)V(X)+R(X),
degR < dv. Déterminer la complexité de la fonction division en fonction de ÆU et ËV- (* Caml *) division : poly --> poly --> poly
{ Pascal } function division(U : poly ; V : poly) : poly

Question 9 Écrire la fonction modulo qui prend comme arguments deux polynômes U 
(X ) et
V(X ) ; et qui calcule le reste de la division euclidienne de U (X ) par V(X ) 
Quelle est la complexité
de cette fonction ?

(* Caml *) modulo : poly --> poly --> poly
{ Pascal } function modulo(U : poly ; V : poly) : poly

Dans la suite du problème) le reste de la division euclidienne de U (X ) par 
V(X ) est noté U mod V.

Partie III. Multiplication et division rapide

Cette partie s'attache a l'amélioration de la complexité des algorithmes de 
multiplication et de
division de polynômes. La notation La:l (respectivement loel) désigne la partie 
entière inférieure
(respectivement la partie entière supérieure) d'un nombre réel a:. On remarque 
qu'on a, pour tout

- w ° d d _
nombre ent1er d, lequat10n (fl + bl -- d.
Multiplication Soient deux polynômes U (X ) et V(X ) représentés par les listes 
(uO7 . . . ,ug_1> et
(co, . .. ,Ug_1> ayant EUR coefficients (le degré de U et V est donc au plus 
EUR -- 1). On pose 6 : (%
puis Ub : (u0, . .. ,u6_1> et Uh : (ue, . .. ,ug_1>, de sorte que U : Ub +X6Uh. 
On définit de même
Vb et Vh. Lorsqu'on écrit le produit U (X )V(X )) on fait apparaitre quatre 
produits impliquant les
polynômes Uh, Ub, Vh, % :

U(X)V(X) = (UbX6 + Ub) (VhX6 + Vb),
= Uhth2EUR + (Ubi/}) + Uth) X6 + Ubi/b.
Question 10 Donner une formule par laquelle le produit U (X )V(X ) s'exprime 
sous la forme

VVsz26 + VV...XEUR + W5, où les polynômes W... W... et Wb se calculent avec 
seulement trois produits
impliquant les polynômes U... V... Ub, V},, Uh + Ub et Vh + V5.

4

Question 11 Écrire la fonction produitRapide qui prend comme arguments deux 
polynômes
U (X ) et V(X ) représentés par des listes de EUR coefficients; et qui calcule 
leur produit, avec une
complexité O (EUR10g2 3) dans le cas où EUR est une puissance de 2. Justifier 
cette formule de complexité.

(* Caml *) produitRapide : poly --> poly --> poly
{ Pascal } function produitRapide(U : poly ; V : poly) : poly

Division Il est possible d'obtenir une amélioration similaire de la division de 
polynômes. Soit un
dividende U (X ) et un diviseur non nul V(X ), respectivement représentés par 
les listes 
et  d'entiers. On suppose que vg_1 est non nul, de telle sorte 
que deg V est exactement
égal a d = EUR -- 1. Le degré de U est au plus égal a 2d : 2EUR -- 2.

Comme pour la multiplication, on sépare les entrées en << partie haute >> et << partie basse >>.
On pose 6 : L%J : l%l, puis Uh : , U;, : , Vh 
: ,
Vb : . Le découpage est représenté par la figure 1. Attention, 
selon la parité de d, on
a2<9=dou2<æ=d+l. On recherche le quotient Q, écrit sous la forme Q : X6Qh+Qb avec deg Qh S d--e et deg Qb < 6. Les formules suivantes donnent la valeur de Q}, et Qb. -- Q,, est le quotient de la division de U ;, par V;,. -- R,, est le reste de cette même division. -- Qb est le quotient de la division de S : <80, . .. 782(d--e)> par Vh, où :

S = X6R.. + uge_1XEUR--l -- thb.

Ub = <%. - -- ,U2e_1> U}. = 

A A

U : Ub + X26Uh |...,| ................. r..26| ................. |...|

V=Vb+Xth IUÜI °°°°°° |%l °°°°°°° lUdl

% %.
degU;,£2(d--e), degUb<26, deth=d--e, degV}, poly --> poly
{ Pascal } function divisionRapide(U : poly ; V : poly) : poly

Question 13 Écrire la fonction moduloRapide qui prend comme arguments deux 
polynômes U (X )
et V(X ) (toujours soumis a la contrainte degU S 2deg V); et qui calcule le 
reste de la division
euclidienne de U (X ) par V(X), plus rapidement qu'avec la fonction modulo de 
la question 11.9.
Quelle est la complexité de la fonction moduloRapide ?

(* Caml *) moduloRapide : poly --> poly --> poly
{ Pascal } function moduloRapide(U : poly ; V : poly) : poly

Partie IV. Codage par évaluation multi--points

L'objectif de cette partie est de proposer un autre algorithme pour calculer le 
codage de Reed--
Solomon par une stratégie de type << diviser pour régner >>.

On commence par construire un arbre binaire dont les noeuds sont étiquetés par 
des polynômes.
Un arbre de sous-produits pour les polynômes X -- dg, X -- cn, . . . X -- dn_1 
est défini comme suit :
les X -- a; sont les étiquettes des feuilles de l'arbre (par ordre des indices 
i croissants dans l'ordre de
lecture des feuilles de la gauche vers la droite)) chaque noeud interne est 
étiqueté par le produit des
polynômes étiquetant ses noeuds fils. Un arbre de sous--produits est dit 
optimal s'il est de hauteur
h minimale (2h_1 < 77. S 2h), et si les degrés des polynômes étiquetant deux fils d'un même noeud diffèrent d'au plus un. La figure 2 représente un tel arbre de sous--produits de hauteur h = 3 pour une famille de 6 polynômes X -- dg, . . . ,X -- a5. m0mlm2m3m4m5 /\ m0m1m2 m3m4m5 /\ /\ m0m1 m2 m3m4 m5 ...! \... ...! \... FIG. 2: Un arbre de sous--produits optimal pour (mo, . . . ,m5), avec la notation m; = X -- cri. Un arbre de sous--produits est représenté par une valeur de type arbre, défini comme suit : (* Caml *) { Pascal } type arbre = Vide type arbre = "noeud; l Noeud of poly * arbre * arbre noeud = record etiquette: poly; filsG: arbre; filsD: arbre; end; L'arbre vide (sans aucun noeud) est représenté par Vide en Caml et par nil en Pascal. Question 14 Écrire la fonction arbreSousProduits qui prend comme argument la liste  arbre

{ Pascal } function arbreSousProduits(a: poly) : arbre

On souhaite maintenant calculer un second arbre, appelé arbre des restes de A(X 
) Il est similaire
a l'arbre de sous--produits calculé a la question précédente) mais les 
étiquettes des noeuds diffèrent : a
un noeud d'étiquette m dans l'arbre des sous--produits) correspond un noeud 
d'étiquette A(X ) mod m
dans l'arbre des restes. La figure 3 donne l'arbre des restes de A(X ) qui 
correspond a l'arbre de la
figure 2.

A(X) mod m0m1mgmgm4m5

A(X )mod mom1m2 A(X )mod m3m4m5
A(X) mod m0m1 A(X) mod m2 A(X) mod m3m4 A(X) mod 7715

/ \ / \

A(X) mod m0 A(X) mod m1 A(X) mod 7713 A(X) mod 7714

FIG. 3: Arbres des restes de A(X ) correspondant a la figure 2.

On fait l'observation suivante. Soient (Q(X ), R1 (X ), R2 (X )) trois 
polynômes a coefficients dans
le. Si on connait @ mod R1R2, on peut calculer @ mod R1 par l'opération :

@ mod R1 = (@ mod R1R2) mod R1.

Question 15 Écrire la fonction arbreRestes qui prend comme arguments l'arbre 
des sous--
produits et un polynôme A(X ) ; et qui retourne comme résultat l'arbre des 
restes de A(X ) Quelle
est la complexité de la fonction arbreRestes lorsqu'on utilise les fonctions de 
la partie III ? Quelle
est la complexité lorsqu'on ne les utilise pas ?

(* Caml *) arbreRestes : arbre --> poly --> arbre

{ Pascal } function arbreRestes(T : arbre ; A : poly) : arbre

À présent) on se sert de l'arbre des sous--produits pour factoriser les 
évaluations du même poly--
nôme A(X) aux nombreux points cm, cm, . . . an_1. On remarque qu'on a pour tout 
i (0 S i < 77.) : A(CQ) : A(X) mod (X -- ozi) Et on calcule ces valeurs a partir de A(X) mod (X -- dg)(X -- 041) - - - (X -- ozn_1) a l'aide de l'arbre des restes. Question 16 Écrire la fonction codageArbre qui prend comme arguments la liste 04 : (cm, . .. ,dn_1> et le polynôme A(a:) ; et qui retourne le codage de 
Reed-Solomon du message
A en utilisant l'arbre de sous--produits correspondant a la suite des polynômes 
X -- cri. Déterminer
sa complexité.

(* Caml *) codageArbre : poly --> poly --> poly
{ Pascal } function codageArbre(oz : poly ; A : poly) : poly