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

Description

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?


• n?logj n?


• loi geometrique


• discrete de loi pk


• lim n?∞


• c? ≥


• n? logj

Sujets

• Première
• Mathématiques
• Loi géométrique

Informations

• Publié par: davaj
• Date de parution: 01 mars 2011
• Nombre de lectures: 32
• Langue: Français

Extrait

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 alors log J c lo ′ = log J n ′ . 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.aunp k etYoleddeueiqtr´eom´eigneenˆmmemeyoq k a. On alors X H(X) =−p k logp k X X p k =−p k log−p k logq k q k X k =D(p||q)−p k logq(1−q) X ≤ −log(1−q)−kp k logq=H(Y), o`ul’ine´galit´evientdeD(p||q)≥0. ∞ 3. Soitune suiteble finiUet d’entropieH(U). {U i } i=1 elrudsnausensnmedev.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.

1