Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Théorie de l’information 2011 - 2012 EISTI Guy Almouzni THEORIE DE L’INFORMATIO

Théorie de l’information 2011 - 2012 EISTI Guy Almouzni THEORIE DE L’INFORMATION CORRIGES Théorie de l’information TD 1 Corrigé. Modélisation mathématique d’une source d’information TD 1 Corrigé. 1 TD 1 Corrigé. Modélisation mathématique d’une source d’information Partie I. Entropie d’une source. Définitions et propriétés. Exercice 1. Entropie d’une source. On utilise la définition : ( ) ( ) ∑ = ⋅ − = n i i i p p X H 1 2 log en le bits/symbo (n est la taille de l’alphabet). Ici n = 5. 1. ( ) ( ) ( ) ( ) ( ) ( ) le bits/symbo 23 . 2 25 . 0 log 25 . 0 15 . 0 log 15 . 0 3 . 0 log 3 . 0 2 . 0 log 2 . 0 1 . 0 log 1 . 0 2 2 2 2 2 ≈ ⋅ − ⋅ − ⋅ − ⋅ − ⋅ − = X H 2. ( ) ( ) ( ) le bits/symbo 12 . 1 8 . 0 log 8 . 0 05 . 0 log 05 . 0 4 2 2 ≈ ⋅ − ⋅ ⋅ − = X H 3. Par la définition : ( ) ( ) le bits/symbo 5 1 log 2 . 0 log 2 . 0 5 2 2       − = ⋅ ⋅ − = X H , ou plus directement par la relation : ( ) ( ) ( ) le bits/symbo 32 . 2 5 log log 2 2 ≈ = = n X H . L’entropie représente l’incertitude sur l’issue de l’expérience; c’est l’information moyenne apportée par l’expérience. On remarquera que l’entropie est la plus élevée dans le cas 3. : c’est une propriété générale de l’entropie : L’entropie atteint son maximum lorsque tous les symboles d’un alphabet donné de taille n sont équiprobables (l’incertitude sur la prédiction de détermination d’un symbole est maximale). Elle vaut alors ( ) n 2 log . Exercice 2. Information moyenne. 1. L’alphabet ici ne contient que le symbole « pile ». On remarque que « pile » est un évènement certain (probabilité 1). Il n’y a aucune incertitude sur l’issue de l’expérience. On a donc ( ) 0 = X H (rappel : ( ) 0 1 log2 = ) 2. Soit    = impair est 6) à (1 dé le sur chiffre le si pair est 6) à (1 dé le sur chiffre le si 0 1 Y . L’alphabet est de taille 2. ( ) ( ) 5 . 0 0 1 = = = = Y P Y P . D’après la propriété de l’entropie dans le cas d’une distribution uniforme, on a immédiatement : ( ) ( ) e bit/symbol 1 2 log2 = = Y H 3. Soit { } ♠ ♥ ♦ ♣ ∈ , , , Y . L’alphabet est de taille 4. On calcule la distribution de probabilités associée : Y ♠ ♣ ♥ ♦ ( ) Y P 3/10 4/10 2/10 1/10 On en déduit l’entropie : ( ) le bits/symbo 85 . 1 10 1 log 10 1 10 2 log 10 2 10 4 log 10 4 10 3 log 10 3 2 2 2 2 ≈       ⋅ −       ⋅ −       ⋅ −       ⋅ − = Y H Théorie de l’information TD 1 Corrigé. Modélisation mathématique d’une source d’information TD 1 Corrigé. 2 Exercice 3. Propriété de groupe. 1. ( ) ( ) ( ) ( ) ( ) ( ) le bits/symbo 23 . 2 25 . 0 log 25 . 0 15 . 0 log 15 . 0 3 . 0 log 3 . 0 2 . 0 log 2 . 0 1 . 0 log 1 . 0 2 2 2 2 2 ≈ ⋅ − ⋅ − ⋅ − ⋅ − ⋅ − = X H 2. ( ) 65 . 0 25 . 0 3 . 0 1 . 0 = + + = = A P p ( ) 35 . 0 15 . 0 2 . 0 1 = + = − = = p B P q ( ) ( ) ( ) e bit/symbol 93 . 0 log log , 2 2 ≈ − − = q q p p q p H 3. Les distributions de probabilité de A et B sont : (on normalise pour que la somme des probabilités soit égale à 1) x 1 3 5 x 2 4 ( ) x PA 0.1/0.65 = 10/65 0.3/0.65 = 30/65 0.25/0.65 = 25/65 ( ) x P B 0.2/0.35 = 20/35 0.15/0.35 = 15/35 le bits/symbo 46 . 1 65 25 log 65 25 65 30 log 65 30 65 10 log 65 10 2 2 2 ≈       −       −       − = A H e bit/symbol 98 . 0 35 15 log 35 15 35 20 log 35 20 2 2 ≈       −       − = B H Vérification de la propriété de groupe : ( ) ( ) B A qH pH q p H X H + + = , : ( ) ( ) ( ) ( ) le bits/symbo 23 . 2 34 . 0 95 . 0 93 . 0 98 . 0 35 . 0 46 . 1 65 . 0 93 . 0 , ≈ + + = ⋅ + ⋅ + = + + = B A qH pH q p H X H Exercice 4. Vers le codage de Shannon. 1. ( ) ( ) ( ) ( ) ( ) ( ) le bits/symbo 23 . 2 25 . 0 log 25 . 0 15 . 0 log 15 . 0 3 . 0 log 3 . 0 2 . 0 log 2 . 0 1 . 0 log 1 . 0 2 2 2 2 2 ≈ ⋅ − ⋅ − ⋅ − ⋅ − ⋅ − = X H 2. Propriété de groupe : ( ) ( ) B A qH pH q p H X H + + = , avec p q − = 1 Interprétation : ( ) X H est composée de : 1. l’incertitude sur le choix de l’une des 2 parties A et B : c’est ( ) q p H , 2. la moyenne des incertitudes associées à chacune des 2 parties séparément : c’est B A qH pH + Ici : ( ) q p H , représente la quantité moyenne d’information apportée par l’observation d’une source binaire. La source est la réponse à une question et p, la probabilité de la réponse « oui ». → ( ) ( ) ( ) q q p p q p H 2 2 log log , − − = 3. D’après les propriétés de l’entropie : dans le cas d’un alphabet de taille n, l’entropie atteint son maximum (égal à ( ) n 2 log ) uniquement dans le cas de distribution de probabilités uniforme. Dans le cas d’un canal binaire ( 2 = n ) et une distribution de probabilités uniforme ( 5 . 0 = = q p ), on a donc : [ ] ( ) e bit/symbol 1 ) 2 ( log , max 2 1 , 0 = = ∈ q p H p . 4. Propriété de groupe : La réponse à une question binaire partage l’ensemble des valeurs possibles de X en 2 parties disjointes : celle du « oui » et celle du « non ». On peut alors appliquer la propriété de groupe : Propriété de groupe : ( ) ( ) ( ) non oui B A qH pH q p H qH pH q p H X H + + = + + = , ,      − = = = p q H H H H non B oui A 1 Interprétation : ( ) X H est composée de : 1. l’incertitude sur le choix de l’une des 2 parties A et B : c’est ( ) q p H , 2. la moyenne des incertitudes associées à chacune des 2 parties séparément : c’est B A qH pH + Théorie de l’information TD 1 Corrigé. Modélisation mathématique d’une source d’information TD 1 Corrigé. 3 Si ( ) X H est l’incertitude moyenne que l’on a sur le résultat du tirage de X en début de jeu, la quantité ( ) q p H , représente l’information moyenne apportée par la réponse à la 1ère question, et la quantité non oui qH pH + est l’incertitude moyenne restant sur la valeur de X une fois la réponse obtenue. uploads/S4/ th-info-polyc 1 .pdf