Solutions des Exercices du cours de Theorie de l'Information et Codage cours du 1er mars

pages

Français

Documents scolaires

2011

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

2011

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

davaj

Date de parution

01 mars 2011

Nombre de lectures

Langue

Français

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,

n?logj n?

loi geometrique

discrete de loi pk

lim n?∞

c? ≥

n? logj

Voir

Publié par

davaj

Date de parution

01 mars 2011

Nombre de lectures

Langue

Français

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. Pournsuﬃsament 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 ﬁniUet 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’algorithmedeLempelZivdanslecasparti culierd’unesourcesansme´moire.

Voir