Master MIC, 1re année

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

  1. Notions de probabilités discrètes et continues.
  2. Entropie, information mutuelle
  3. Premiers théorèmes de Shannon
  4. Séries de Fourier
  5. Théorème d'échantillonnage

Horaire des cours

Le cours aura lieu du 9 septembre au 12 décembre 2019 :

Bibliographie

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.
Powered by MathJax Valid CSS! Valid XHTML 1.1! Antoine Chambert-LoirDernière mise à jour :