HEC 2004 concours MAths 1

Publié par

HEC 2004 concours MAths 1

Publié le : jeudi 21 juillet 2011
Lecture(s) : 294
Nombre de pages : 4
Voir plus Voir moins
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:Lope´rationΔsurlespartiesdunensemble Danscettepartieonconside`reunensembleE={e1, . . . , en}ayantn´lmee´.nest Ladie´rencesyme´triquededeuxpartiesquelconquesAetBdeEee,not´AΔB, est l’ensemble dese´le´mentsdeEdmet.Onaop´queloiΔnretasetapuiqutrealapas`neetlaune`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)trapenureieipttsraeuoqnupteeneOsnr´AdeEpar le n-uplet(x1, . . . , xn)en posant : i∈ {1, . . . , n}, xi= 1sieiarappneita`tAet0sinon. a)Les partiesA,B,AΔBe´at(rpantmevetiecspresee´tnese´rpertnx1, . . . , xn),(y1, . . . , yn) et (z1, . . . , zn) , construire pour un entierix´antna`aeppraet{1, . . . , n}gunneestable`adeuxli, et deux colonnes donnant les valeurs dezien fonction des valeurs dexietyi. Comparerzi et|xiyi|. b)Montrer que pour toutes partiesA,BetCdeE,d(A, C)6d(A, B) +d(B, C).
PartieII:Uneautrealg`ebrelin´eaire Onconside`relensembleK={0,1}etMp,n(Kas`se´d)nelengidelembseceriatsmplignes etn colonnesdontlescoecientsappartiennent`aK. ˙ Onde´nitsurKl’addition + et la multiplication.snaetusvilbseestaidedala`
˙ + 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`artpoaprrpavetinoitiddalirubidtsets surKr.rec;´et´esneespropridae´omtnostnap`s Onde´nite´galement ˙16i6p16i6p 1) la sommeA+Bde deux matricesA= (ai,j) etB= (bi,j`a) appartenantMp,n(K) 16j6n16j6n ˙16i6p˙ par :A+B= (ci,ju`o)ci,j=ai,j+bi,j 16j6n 2) le produitε.Ad’une matriceA= (ai,j´emen´el)tdutneεtneretanppraantme`aecspveti 16i6p 16j6n   Mp,n(K) etKpar :ε.A=ε.ai,j 16i6p 16j6n ˙16i6p16i6n 3) le produitA×Bde deux matricesA= (ai,j) etB= (bi,jrespective-) appartenant 16j6n16j6m ˙16i6p˙ ˙ menta`Mp,n(K) etMn,m(K) par :A×B= (ci,jo`u)ci,j=ai,1.b1,j+∙ ∙ ∙+ai,n.bn,j 16j6m Pour toute matriceAnetr`tnaapaapMp,n(K) et toute colonneXetanppraatna`Mn,1(K), le ˙ produitA×Xsniatsee´dneibin.i ˙ Onadmetquelaloi+ainsid´eniesurMp,n(Kve,aiitsscoeva,atitnciomuomp´eoatere)nuts quelleadmetune´le´mentneutre`asavoirlamatricenulleayantplignes etncolonnes et dont
tousles´el´ementssontnuls;onnoteOcette matrice et cela quelles que soient les valeurs denet ˙ ˙ pOnadmet´.qteugelamene×ivutarepistdibtr.+aseppar`tro ˙ ˙ Dans leur copie les candidats pourront omettre les points sur les signes + et×. On remarque que pour toute matriceAaptrnena`taapMp,n(K) : 0 ˙ ˙ (G)A+O=A, A+A=O On appellecodetoute partie non videCdeMn,1(K) telle que : 2 ˙ (x, y)∈ C, x+y∈ C      1 1 0 1 1 1 0 0 1)rtauloceere`qselcoOnidnsonnesx1=0, x2=1, x3=1, x4=0ap-     1 0 1 0 0 0 0 0   4 ˙ ˙ ˙ partenanta`M5,1(K) puis l’ensembleC=ε1.x1+ε2.x2+ε3.x3+ε4.x4,(ε1, ε2, ε3, ε4)K a)Montrer queCest un code. D´eterminertousles´ele´mentsdeCl`addeeaix1, x2, x4.   2 ˙ b)Existe-t-il une famille (u1, u2´eel´)dedstnemCtelle queε1.u1+ε2.u2,(ε1, ε2)Ksoit ´egal`aC? ˙ ˙ c)Montrer que :ε1.x1+ε2.x2+ε4.x4=Oε1=ε2=ε4= 0. On dit qu’une famille(u1, . . . , uq)el´ed´sdementMp,n(K)estK-libre lorsque : q ˙ ˙ (ε,. . . , εq)K, ε1.u1+∙ ∙ ∙+εq.xq=Oε1=. . .=εq= 0 Dans le cas contraire, on dit que la famille(u1, . . . , uq)estKe´.e-il On dit qu’une famille(u1, . . . , up)nodne`tuacndaoptereinnementsaptles´el´Cest uneK-base deClorsqu’elle est une familleKbil-epqurtouetrersloemtnlee´uo´txdeCil existe p ˙ ˙ ε1, . . . , εp)a`tnanetrappaKtel quex=ε1.u1+∙ ∙ ∙+εp.up (Dans leur copie, les candidats pourront omettre la lettreKnadexprslesonsmessilue´napise K-libre,K- base, sans en oublier le sens particulier.) Dans la suite de cette partienrelsup´etiernatuenarnune´dsegia`lage´uorueir2.     x1y1     2)Pour toutx= ety= rtenappat`anaMn,1(K),d(x, y) est le nombre d’entiers .. xnyn ina`taapparten{1, . . . , n}tels quexi6=yi.  2 ˙ a)Montrer que :(x, y)∈ Mn,1(K), d(x, y) =d(x+y, O).  3 b)Montrer que :(x, y, z)∈ Mn,1(K), d(x, z)6d(x, y) +d(y, z). 3)SoitC`tano´rdeiuenodncu{O}. a)Montrer queCadmet uneKsavopr`estiirjuenixe´osec,tsneO.esuopnab-erd´,aeracrrsion le cardinal maximum d’une familleKbreform´eed´el´menestedil-C. b)Montrer que si (u1, . . . , up) est uneK-base d’un codeCdentme´eelt´outsrola,Cseirdt´ce ˙ ˙ mani`ereuniquesouslaformeε1.u1+∙ ∙ ∙+εp.up. du´eelirndEdleceraidanCen fonction du cardinal d’une de sesK-bases. c)Montrer que toutes lesK-bases deCelˆmotnraidmecel.na d)On suppose quepest le cardinal d’uneK-base deCet que (v1, . . . , vp) est une familleK-libre deC, montrer que (v1, . . . , vp) est uneK-base deC. 4)On suppose dans cette question que 16p6net on noteIp`aceirtamalplignes etpcolonnes donttousles´ele´mentssontnulsexcepte´les´ele´mentsdiagonauxquisont´egaux`a1. Onsupposee´galementqueQnanetrappaecirtaemunstea`tMp,n(K) telle quepcolonnes deQtne´agelasxusopcolonnes distinctes deIp.   ˙ Ond´enitlensembleCQ=x∈ Mn,1(K), Q×x=O. 2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.