Université Paris Diderot
Résumé
Le cours s'articule autour de trois théorèmes de Claude Shannon.
Ce sont trois théorèmes mathématiques avec des problématiques différentes
autour de la numérisation optimale et la transmission de l'information.
Le premier théorème s'intéresse à la compression des données : si
on veut numériser un document, il est intuitivement clair qu'on
va gagner en espace de stockage
en codant de façon plus courte les caractères les plus fréquents
et de façon plus longue les moins fréquents. Cette fréquence des caractères nous
fera introduire le language des probabilités et d'entropie de
Shannon.
Le deuxième théorème s'intéresse à la transmission
(ou stockage) sans pertes des
données. On démontre qu'en introduisant un peu de redondance dans
un document numérisé, on peut le retrouver malgré la perte aléatoire
d'une partie de l'information.
C'est encore ici le language des probabilités qui est utilisé.
En plus de
l'entropie, apparaît ici la notion de capacité d'un canal de
transmission.
Le troisième est le théorème d'échantillonnage. Une information
peut être une fonction d'une variable réelle. Le théorème
d'échantillonnage nous explique comment, en prenant la valeur de
cette fonction en un nombre fini de points, on peut reconstruire
l'information. On tient compte pour cela des fréquences de notre
fonction. L'analyse faite ici est basée sur la théorie des séries
de Fourier.
Contenu
- Notions de probabilités discrètes et continues.
- Entropie, information mutuelle
- Premiers théorèmes de Shannon
- Séries de Fourier
- Théorème d'échantillonnage
Horaire des cours
Le cours aura lieu du 9 septembre au 12 décembre 2019 :
Bibliographie
- T. Cover, J. Thomas, Elements of Information Theory, Wiley & Sons, 2e édition, 2006
- H. Dym, H. P. McKean, Fourier series and integrals, Academic Press, 1972
- J.-P. Kahane, P.-G. Lemarié-Rieusset, Séries de Fourier et Ondelettes, coll. Nouvelle bibliothèque mathématique, Cassini, 2017
- C. Shannon, La théorie mathématique de la communication, coll. Le sel et le fer, Cassini, 2018. Traduction de « A mathematical theory of communication », The Bell System Technical Journal, vol. 27, p. 379–423, 623–656, 1948.
- C. Shannon, « Communication in the presence of noise », Proc. of the IRE, vol. 37, p. 10–21, 1949. Réimprimé dans Proc. of the IEEE, vol. 86, p. 447--458, 1998.
- Exposés du séminaire Bourbaphy
sur la théorie de l'information :
Kirone Mallick, Thermodynamique et information ;
Olivier Rioul, La théorie de l'information sans peine.
Documents disponibles
Résumé des séances
- 13 septembre
-
Introduction :
le modèle de Shannon de la communication.
Entropie.
Entropie d'une variable aléatoire discrète, exemples d'un tirage de dés,
d'une loi uniforme et d'une loi de Bernoulli. Entropie conditionnelle.
Divergence d'une loi par rapport à une autre et information mutuelle
de deux variables aléatoires ; positivité de l'information mutuelle,
lien avec l'entropie.
- 20 septembre
-
Information mutuelle conditionnelle, indépendance conditionnelle de deux variables aléatoires relative à une variable aléatoire.
Taux d'entropie d'un processus stochastique. Cas d'un processus iid, d'un processus stationnaire. Processus markoviens homogènes : matrice de transition
et expression des lois par calcul matriciel.
- 30 septembre
-
Processus markoviens homogènes : existence et calcul de l'entropie
dans le cas stationnaire, puis dans le cas primitif (= irréductible apériodique) — théorème de convergence vers la loi stationnaire (Perron).
- 4 octobre
- Codage.
Alphabet, mots, longueur, concaténation des mots (structure de monoïde). Code, code uniquement décodable, code préfixe.
Inégalité de Kraft–McMillan. Minoration de la longueur moyenne d'un mot de code par l'entropie de la source. Inversement, construction de codes permettant une compression assez efficace (Shannon).
- 11 octobre
-
Codage arithmétique de Shannon (démonstration du résultat admis la semaine précédente).
Codes optimaux : codage de Huffman.
- 18 octobre
-
Preuve de l'optimalité du codage de Huffman.
Inégalité de Markov, inégalité de Bienaymé–Tchebitcheff.
Interprétation statistique de l'entropie et de l'information mutuelle.
- 25 octobre
-
Modèle de communication avec bruit,
définition d'un canal sans mémoire. Capacité de transmission d'un tel canal, exemples.
- 9 et 16 novembre
- Cours fait par Guillaume Garrigos
- 23 novembre
-
Échantillonnage.
Discussion de la problématique du traitement numérique
de l'information, échantillonnage, quantification.
Séries de Fourier, théorème de Dirichlet, théorème de Parseval.
- 30 novembre
-
Transformation de Fourier, formule d'inversion de Fourier,
théorème de Plancherel.
Théorème d'échantillonnage. Lien avec la formule de Poisson.
Antoine Chambert-Loir—
Dernière mise à jour :