HEC 2004 mathematiques i classe prepa hec (s)

Description

hec 2004, math 1, option scientifiqueSUR LA TRANSMISSION DE MESSAGESLe but de ce probl`eme est de construire un syst`eme permettant de d´etecter et de corrigerautomatiquement des erreurs apparues lors de la transmission de messages binaires. Dans tout leprobl`eme, m, n, p d´esignent des entiers naturels non nuls.Partie I : L’op´eration Δ sur les parties d’un ensembleDans cette partie on consid`ere un ensemble E ={e ,...,e } ayant n ´el´ements.1 nLa diff´erence sym´etrique de deux parties quelconques A et B de E, not´ee AΔB, est l’ensembledes ´el´ements de E qui appartiennent `a l’une et pas a` l’autre. On admet que l’op´eration Δ estcommutative et associative. On sait que pour toute partie A de E :(G) AΔ∅ =A, AΔA =∅Pour toutes parties A et B de E, on pose d(A,B) = Card(AΔB).1)a)Pour une partie A de E, d´eterminer d(A,∅) et d(A,E).b)Montrer que pour toutes parties A et B de E : d(A,B) =d(AΔB,∅).2) On sait qu’on peut repr´esenter une partie A de E par le n-uplet (x ,...,x ) en posant :1 n∀i∈{1,...,n}, x = 1 si e appartient a` A et 0 sinon.i ia) Les parties A, B, AΔB ´etant repr´esent´ees respectivement par (x ,...,x ), (y ,...,y ) et1 n 1 n(z ,...,z ),construirepourunentierifix´eappartenanta`{1,...,n},unetablea`deuxlignes1 net deux colonnes donnant les valeurs de z en fonction des valeurs de x et y . Comparer zi i i iet |x −y |.i ib)Montrer que pour toutes parties A, B et C de E, d(A,C)6d(A,B)+d(B,C).Partie II : Une autre alg`ebre lin´eaireOn consid`ere ...

Informations

• Publié par: aiolos
• Nombre de lectures: 291
• Langue: Français

Extrait

hec 2004, math 1, option scientifique

SUR LA TRANSMISSION DE MESSAGES Lebutdeceprobl`emeestdeconstruireunsyst`emepermettantdede´tecteretdecorriger automatiquement des erreurs apparues lors de la transmission de messages binaires. Dans tout le probl`eme,m,n,plsrennnos.ulengise´dtunarsientsedent

PartieI:L’ope´rationΔsurlespartiesd’unensemble Danscettepartieonconside`reunensembleE={e 1 , . . . , e n }ayantn´lmee´.nest Ladiffe´rencesyme´triquededeuxpartiesquelconquesAetBdeEee,not´AΔB, est l’ensemble dese´le´mentsdeEdmet.Ona’op´queloiΔnretasetapuiqutreal’apas`neetlau’ne`teinnaptr commutative et associative. On sait que pour toute partieAdeE: (G)AΔ∅=A, AΔA=∅ Pour toutes partiesAetBdeE, on posed(A, B) = Card(AΔB). 1)a)Pour une partieAdeErenimrete´d,d(A,∅) etd(A, E). b)Montrer que pour toutes partiesAetBdeE:d(A, B) =d(AΔB,∅). 2)trapenureieipttsrae’uoqnupteeneOsnr´AdeEpar le n-uplet(x 1 , . . . , x n )en posant : ∀i∈ {1, . . . , n}, x i = 1sie i arappneita`tAet0sinon. a)Les partiesA,B,AΔBe´at(rpantmevetiecspresee´tnese´rpertnx 1 , . . . , x n ),(y 1 , . . . , y n ) et (z 1 , . . . , z n ) , construire pour un entierix´fiantna`aeppraet{1, . . . , n}gunneestable`adeuxli, et deux colonnes donnant les valeurs dez i en fonction des valeurs dex i ety i . Comparerz i et|x i −y i |. b)Montrer que pour toutes partiesA,BetCdeE,d(A, C)6d(A, B) +d(B, C).

PartieII:Uneautrealg`ebrelin´eaire Onconside`rel’ensembleK={0,1}etM p,n (Kas`se´d)ne’lengidelembseceriatsmplignes etn colonnesdontlescoefficientsappartiennent`aK. ˙ Onde´finitsurKl’addition + et la multiplication.snaetusvilbseestaidedal’a`

˙ + 0 1.0 1 0 01 00 0 1 10 10 1 On remarque que la multiplication surK´eopesecssontirarsednoituq,slee´estlamultiplicanot associatives, commutatives et que la multiplication surK`artpoaprrpavetinoitidda’lirubidtsets surKr.rec;´et´esneespropridae´omtnostnap`s Onde´finite´galement ˙ 16i6p16i6p 1) la sommeA+Bde deux matricesA= (a i,j ) etB= (b i,j `a) appartenantM p,n (K) 16j6n16j6n ˙ 16i6p ˙ par :A+B= (c i,j u`o)c i,j =a i,j +b i,j 16j6n 2) le produitε.Ad’une matriceA= (a i,j ´emen´el)td’utneεtneretanppraantme`aecspveti 16i6p 16j6n   M p,n (K) etKpar :ε.A=ε.a i,j 16i6p 16j6n ˙ 16i6p16i6n 3) le produitA×Bde deux matricesA= (a i,j ) etB= (b i,j respective-) appartenant 16j6n16j6m ˙ 16i6p ˙ ˙ menta`M p,n (K) etM n,m (K) par :A×B= (c i,j o`u)c i,j =a i,1 .b 1,j +∙ ∙ ∙+a i,n .b n,j 16j6m Pour toute matriceAnetr`tnaapaapM p,n (K) et toute colonneXetanppraatna`M n,1 (K), le ˙ produitA×Xsniatsee´dneibinfi.i ˙ Onadmetquelaloi+ainsid´efiniesurM p,n (Kve,aiitsscoeva,atitnciomuomp´eoatere)nuts qu’elleadmetune´le´mentneutre`asavoirlamatricenulleayantplignes etncolonnes et dont