Solutions des Exercices du cours de Theorie de l'Information et Codage cours du 1er mars
3
pages
Français
Documents scolaires
2011
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
3
pages
Français
Documents scolaires
2011
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Secondaire, Lycée, Première
Solutions des Exercices du cours de Theorie de l'Information et Codage cours 3 du 1er mars 2011. 1. Montrer le lemme enonce sans demonstration en cours: c(un1) = O(n/ logn). • En reprenant les notations du cours, soit c? = c/J3 et n? = n/J3. On a vu en cours que n? > c? logJ c?. Pour n suffisament grand tel que √ n? ≤ 2 n?logJ n? , on a – soit c? < √ n? et donc c? < 2n?/ logJ n?. – soit c? ≥ √ n? et alors c? < n?logJ c? ≤ n? logJ √ n? = 2n? logJ n? . 2. Montrer que pour toute v.a. X a valeurs entieres de moyenne E[X ], on a: H(X) ≤ (E[X ] + 1) log (E[X ] + 1)? E[X ] logE[X ], avec egalite quand X suit une loi geometrique: P(X = k) = qk(1? q) pour k ≥ 0. • pour Y de loi geometrique P(Y = k) = qk(1? q) pour k ≥ 0, on a E[Y ] = q1?q et : H(Y ) = ? ∑ k qk(1? q) log qk(1? q) = ? log(1? q)? E[Y ] log q,
Voir
Solutions des Exercices du cours de Theorie de l'Information et Codage cours 3 du 1er mars 2011. 1. Montrer le lemme enonce sans demonstration en cours: c(un1) = O(n/ logn). • En reprenant les notations du cours, soit c? = c/J3 et n? = n/J3. On a vu en cours que n? > c? logJ c?. Pour n suffisament grand tel que √ n? ≤ 2 n?logJ n? , on a – soit c? < √ n? et donc c? < 2n?/ logJ n?. – soit c? ≥ √ n? et alors c? < n?logJ c? ≤ n? logJ √ n? = 2n? logJ n? . 2. Montrer que pour toute v.a. X a valeurs entieres de moyenne E[X ], on a: H(X) ≤ (E[X ] + 1) log (E[X ] + 1)? E[X ] logE[X ], avec egalite quand X suit une loi geometrique: P(X = k) = qk(1? q) pour k ≥ 0. • pour Y de loi geometrique P(Y = k) = qk(1? q) pour k ≥ 0, on a E[Y ] = q1?q et : H(Y ) = ? ∑ k qk(1? q) log qk(1? q) = ? log(1? q)? E[Y ] log q,
- n?
- n?logj n?
- loi geometrique
- discrete de loi pk
- lim n?∞
- c? ≥
- n? logj
SolutionsdesExercicesducoursdeThe´oriedel’InformationetCodage cours 3 du 1er mars 2011. n 1.Montrerlelemme´enonc´esansd´emonstrationencours:c(u) =O(n/logn). 1 ′3′3 •En reprenant les notations du cours, soitc=c/Jetn=n/J. Ona vu en cours que ′ ′ ′′ ′n n >clogc. Pournsuffisament grand tel quen≤2′, on a J logn J ′ ′′ ′′ –soitc <net doncc <2n /logn. J ′ ′′ ′n n2n ′ ′ c <′≤ –soitc≥net alorslogJclo′=logJn′. gn J 2. Montrerque pour toute v.a.Xnnyeesereomedesru`itnavela`E[X], on a: H(X)≤(E[X] + 1) log (E[X] + 1)−E[X] logE[X], k avece´galite´quandXoielunitsu:eiruq´mte´goeP(X=k) =q(1−q) pourk≥0. k q •pourYloigdee´rte´moqieuP(Y=k) =q(1−q) pourk≥0, on aE[Yet :] = 1−q X k k H(Y) =−q(1−q) logq(1−q) k =−log(1−q)−E[Y] logq, onadoncbiene´galite´danscecas. •SoitXioledetcr`e.disev.aunpketYoleddeueiqtr´eom´eigneenˆmmemeyoqka. On alors X H(X) =−pklogpk X X pk =−pklog−pklogqk qk X k =D(p||q)−pklogq(1−q) X ≤ −log(1−q)−kpklogq=H(Y), o`ul’ine´galit´evientdeD(p||q)≥0. ∞ 3. Soitune suiteble finiUet d’entropieH(U). {Ui}i=1elrudsnausensnmedev.a.i.i.d.`ava (n) On noteC(nldemximaremanombeluae´ag.v.a)alelqustcnelnedstoitsiUutpetrˆee n de´coupe´.C’est`adireaveclesnotationsducours:C(n) =c(Uallons montrer qu’avec). Nous 1 probabilite´1,ona: C(n) logC(n) lim sup≤H(U). n→∞n Cer´esultatpermetdede´montrerl’optimalit´edel’algorithmedeLempelZivdanslecasparti culierd’unesourcesansme´moire.
1
