Solutions des Exercices du cours de Theorie de l'Information et Codage cours du fevrier

Publié par

Solutions des Exercices du cours de Theorie de l'Information et Codage cours 1 du 8 fevrier 2011. 1. Dans le cas R = 1/2n, avec n ? N et pour un encodage du type: repetition de chaque bit 2n fois sur le canal binaire symmetrique: donner une strategie de decodage et calculer la probabilite d'erreur correspondante Pe. Comparer au cas R = 1/(2n? 1) etudie en cours quand p ? 0. • Decodage par majorite, en cas d'egalite, tirage a pile ou face. Pe = ∑ k≥n+1 ( 2n k ) pk(1? p)2n?k + 1 2 ( 2n n ) pn(1? p)n. • quand p? 0, on a Pe ? (2n?1 n ) pn qui correspond au cas etudie en cours. 2. On considere le cas R = 2n + 1 pour n ? N et l'encodage: j'envoie la majorite de chacun des blocs de 2n+1 bits successifs emis par la source (comme decrit en cours pour R = 3). Montrer que Pe = (1? p)Q+ p(1?Q) avec Q = 1 2 ? ( 2n n ) 2?(2n+1).

  • triplets de colonnes liees

  • meme probabilite d'erreur pe

  • bit

  • probabilite d'erreur correspondante

  • probabilite

  • strategie de decodage

  • colonnes complementaires du motif d'erreur

  • majorite

  • motif d'erreur


Publié le : mardi 1 février 2011
Lecture(s) : 84
Source : di.ens.fr
Nombre de pages : 4
Voir plus Voir moins
Correctiondesexercicesducours:StructuresetAlgorithmesAle´atoires cours 1 du 16 octobre 2009. 1.Vousavez3pi`ecesdontuneestbiaise´e:voussavezquelletombesurpileavecprobabilite´2/3. Vousnesavezpasquellepie`ceestbiaise´emaisvousfaitesuntirageavecchacunedespie`ceset lapremie`reetsecondepie`cestombentsurpiletandisquelatroisie`metombesurface.Quelle estlaprobabilite´quelapremi`erepie`cesoitcellequiestbiaise´e? SoitEine´entmelev´l:aiteee´siuiestbiastcelleqpe`iceee`meBgeratilet:enemne´ve´l destroispie`cesdonnedanslordre:pilepileface.Avantletirage,nousnavonsaucune informationsurlapie`cebiais´eedoncP(Ei) = 1/avons aussi3. Nous 2 1 11 1 P(B|E1) =P(B|E2=) =,et,P(B|E3) =. 3 2 26 12 On a donc P(B|E1)P(E1) 2 P(E1|B) =P=. 3 P(B|Ei)P(Ei) 5 i=1 Apre`slare´alisationdutirage,lavraisemblancepourquelapremie`repie`cesoitcellequi estbiais´eeestpass´eede1/3`a2/5. 2. Dansle cas vu en cours de la multiplication matricielle.Sans information surA, B, C, on fait lhypothe`seaprioriqueP(AB=C) = 1/fait tourner une fois l’algorithme vu en cours2. On quinousretourneler´esultat:AB=Clellelienefsotrlmttaetnioounvqeui.l´vtAceeecpaorabib aposterioriquelidentite´soitcorrecte?Etapr`eskit´ee?hmitglroleanodsarit uaacps´rcee´edtn.SoitnesoaierLerialimistsetnemEl´ev´enem:tnedilitneee´tcostecrr.te etFnemee´´vllane:tthmegoriurneretolAB=C. Oncommence avecP(E) =P(E) = 1/2. De plus,P(F|E) = 1 tandis queP(F|E)1/aOn).eucnuosrseluatvtr`esler´2(dap donc P(F|E)P(E) 2 P(E|F) =. P(F|E)P(E) +P(F|E)P(E) 3 Apre`slepremiertest,onsupposemaintenantqueP(E)2/3 etP(E)1/3, on a donc apres un second test: 2/3 4 P(E|F)=. ˙ 2/3 + 1/31/2 5 Ontrouveapr`eskeratit´ions 1 P(E|F)1. k 2 +1
1
3.Unecoupedansungrapheestunensembledarˆetesquiunefoisretire´rendlegraphed´econnecte´. Unecoupeminimaleestunecoupedecardinalit´eminimale.Lacontractionduneareˆte{u, v} consistea`rassembleruetvuttoleesmilintnatemme´neesnuosluesetrˆseanetrenuetv maisengardanttouteslesautresarˆetesdugraphe.Legrapheainsiobtenupeutcontenirdes arˆetesparall`elesmaispasdebouclesurunsommet.Ve´rierquunecoupedungrapheobtenu apr`esunecontractiondareˆteestencoreunecoupedugrapheoriginal.Onconsid`erealors l’algorithme qui consiste enn2e´atep`usonui`aeetqgudshparosedtemmnolerembste chaqueite´ration,choisituneareˆteuniforme´mentauhasardetlacontracte.Alandesn2 it´erations,legrapheobtenuestungraphe`adeuxsommetsetlalgorithmeretournelensemble desareˆtesconnectantcesdeuxsomments.Montrerquecetalgorithmeretourneunecoupe minimaleavecprobabilit´eaumoins2/n(n1). 3 1 1 3,4 1,3,45 1,2,3,4 5 5 5
4 2 2 2 Figure1:Unexempleou`lalgorithmeretourneunecoupeminimale(`achaque´etape,lareˆtecontracte´e estmarque´e).
Soitkla taille d’une coupe minimale deGet soitCune telle coupe minimale.Nous calculonslaprobabilite´quelalgorithmetrouveC. SilalgorithmenechoisitjamaisdareˆtesdeClors desnilrelorsnetour´trei2sna,taoi C. SoitEiarlt:enntcoteˆelmene´ve´artce´lerodsleai`emeit´erationntsedsapsnaCet i so =Edevons calculer. NousP(Fr:nspan¸coemmoccuoN.) itFi j=1j n2 2k P(E1) =P(F1)1, nk carchaquesommetaaumoinsdegre´ket donc le graphe a au moinsnk/teseE.na2ˆr conditionant parF1paere`lsertiime`tion´eraungravecehpaedeterns,opreauvron1 sommets et de coupe minimale de taillek. Ona donc 2k P(E2|F1)1. k(n1) Finalement,enit´erant: P(Fn2) =P(En2|Fn3)P(Fn3) n2  Y 2 2 1=. ni+ 1n(n1) i=1
2
4.Montrerquilexisteuneinnit´edenombrespremiersdutype6nsnade´silitutatlsu´e(r+5la dernie`repreuvedonn´eeencours). On suppose par l’absurde qu’ils sont en nombre fini:{p1, p2, . . . , pk}eeotcnnois`drep= 6p1p2. . . pk1. Commepe´turirc,]6[epno5ep= 6n+ 5et sipn’est pas premier alors p=uvet donc soit5 [6]usoitvitrappaat`en{p1, p2, . . . , pk}ce qui est contradictoire. 5.Voiciunepreuvenonprobabilisteduthe´or`emevuencourssurlesensemblesdominantsdun grapheG´rgededlaminimeδ >chaque sommet1. Pourv, on noteC(v)tu´eelocsnitlneesbm devOn dit queet de ses voisins.vcouvreC(vensemble dominant pour le graphe). Un G= (V, E) est un ensembleUtel queV=uUC(uirhtem´dtereiminconsid`erelalgonO.)est qui`achaque´etapechoisitlesommetquicouvreunmaximumdesommetsquinesontpas encore couverts.SoitUtujqsua`el´dbetull´etapemmossedelbmesneispudeisishoscett. Soit rt=|V\ ∪uUtC(u)|aMp.eal`et´tronquert, il existe un sommetvumaat`ennsoiuqraitaipp rt(δ+ 1)/nensemblesC(w) avecwV\ ∪uUtC(ue.)nE´ddeiueruqrt+1rt(1(δ+ 1)/n). Retrouverlere´sultatdonne´encours. P Soitn(v) le nombre deC(w) avecwV\ ∪uUtC(u) qui couvrev. Onan(v) = vV P |C(v)| ≥rt(δet donc il existe+ 1)vV\Uttel quen(v)rt(δ+ 1)/n. vV\∪uUC(u) t Enrajoutantcesommet`aUt, le nombre de sommets non couverts est au plus dert(1(δ+ 1)/n), on a doncrt+1rt(1(δ+ 1)/napres). Doncnln(δ+ 1)/(δ+1)it´erati,snoli restera au plusn/(δ+ 1)sommets non couverts que l’on peut alors rajouter pour former un ensemble dominant de taille au plus celle vue en cours. 6. Un hypergraphe est une paireH= (V, Eo)`uVest un ensemble fini de sommets etEest une famille de sousensembles deVhapeetslepp(se´epyhra)rteˆeUns.pehyrargnuniforme si chaquearˆetecontientexactementnsommets. Ondit qu’un hypergraphe est 2coloriable si il existe un 2coloriage deVenesoitmunearˆettaqieuS.nocorhmotoiuqlecuatm(n) le nombre minimalpossibledarˆetesdunhypergraphenMontrer queuniforme qui n’est pas 2coloriable. n1n1 tout hypergraphensest2coloriableiosned2raeˆetfoniucmveearmnod,euqcm(n)2 . Oncherchemaintenantunebornesupe´rieuresurm(nfixe). OnVavecvpoints,ve´simitpoares plus tard.Soitχun coloriage deVSoiten deux couleurs.SVun ensemble denpoints v/2 (n) 2 choisiuniform´ement.MontrerqueP(Sest monochromatique sousχ)pavecp=v. (n) SoitS1, . . . , Smdes ensembles dentieermfonieueri`uoP.etnadnepe´dnropintschoisisdeman chaque coloriageχ, soitAχndcuesenemaut:´vnele´SiMontrer quen’est monochromatique. v mvln 2 P(χAχ)2 (1p) etdonc quem(n)≤ ⌈doit donc trouver. Onvqui minimisev/p. p Pour ceci on utilisera l’approximation:   v/2n Y 22 v2i n1n1nn /2v p= = 22e . v vi n i=0 eln 22n End´eduirequem(n)<(1 +o(1))n2 . 4 n1 tartdnoie´eDnsmom(n)On colore2 .Veharcou.Petrˆeaquerlaine`ioere´tademaeE, 1n soitAe:veen´e´tlnemeest monochromatique.On aP(Aeet donc) = 2 X P(eEAe)P(Ae)<1. eE 3
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.