Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-1-7 [2011/07/12 14:28] (current)
baptiste created
Line 1: Line 1:
 +<html>
 +<h2>Théorie de l'information</h2>
 +
 +<p>Resp.: S. Boucheron</p>
 +
 +<h3>Objectifs</h3>
 +
 +<p>Les questions abordées dans ce cours sont motivées par des applications : le
 +stockage, la numérisation et la transmission des données. Motivé par des
 +questions d'ingénieur, le cours s'adresse à des étudiants en Informatique et
 +en Mathématiques. Il vise à présenter les bases mathématiques de la théorie
 +de Shannon et les solutions algorithmiques à ces problèmes. Il prépare les
 +étudiants à utiliser les résultats et les méthodes de la théorie de
 +l'information en Informatique (Compression/Télécommunications) et/ou en
 +Mathématiques (Probabilités/Statistiques).</p>
 +
 +<h3>Plan du cours</h3>
 +
 +<dl>
 +<dt>Codage source </dt>
 +<dd><ol>
 +<li> Entropie d'une source, théorème de codage sans
 +bruit de Shannon. Codage arithmétique.</li>
 +<li> Codage universel I : modèles paramétriques.  </li>
 +<li> Codage universel II : techniques de dictionnaires (LZ).  </li>
 +<li> Codage universel III : transformée de Burrows-Wheeler.  </li>
 +<li> Codage universel IV : codage par transformation grammaticale.  </li>
 +<li> Codage avec pertes d'information, théorème de débit-distorsion.  </li>
 +<li> Codages des sources Gaussiennes. Application aux codage linéaire prédictif.  </li>
 +<li> Débit-distorsion. Algorithmes de calcul de la fonction de débit-distorsion.
 +Codage progressif.</li>
 +</ol>
 +</dd>
 +<dt>Codage canal</dt>
 +<dd><ol>
 +<li> Codage canal. Capacité, <em>random coding exponents</em>,
 +<em>sphere packing bounds</em> </li>
 +<li> Méthodes effectives, codage algébrique, codes de Reed-Solomon.  </li>
 +<li> Constructions de bonnes familles de codes codables et décodables en
 +temps linéaire, LDPPC </li>
 +<li> Le principe de séparation.  </li>
 +<li> Questions de théorie de l'information multi-utilisateurs
 +I : diffusion </li>
 +<li> Questions de théorie de l'information multi-utilisateurs
 +II : accès multiple</li>
 +</ol>
 +</dd>
 +</dl>
 +
 +<h3>Pré-requis</h3>
 +
 +<p>Algorithmique et probabilités discrètes.</p>
 +
 +<h3>Bibliographie</h3>
 +
 +<ul>
 +<li>Cover, T. and Thomas, J. (1991) <em>Elements of Information Theory.</em>
 +J. Wiley and sons. New-York</li> 
 +<li>Csiszar, I. and Körner, J. (1981) <em>Information Theory: Coding
 +Theorems for Discrete Memoryless Channels.</em> Academic Press. New-York.</li> 
 +<li>Csiszar, I. (1990). <em>Information theoretical methods in statistics.</em>
 +Lecture notes at Maryland University. </li> 
 +<li>Gallager, R. G. (1968) <em>Information Theory and Reliable Communication.</em>
 +J. Wiley and sons. New-York. </li> 
 +<li>Kieffer, J. (2000) <em>Lecture notes on data compression.</em> Graduate
 +course ECE5585. University of Minesota.
 +[[http://www.ece.umn.edu/users/kieffer/ece5585.html|http://www.ece.umn.edu/users/kieffer/ece5585.html]]</li> 
 +<li>Shannon, C.E. (1948) A Mathematical Theory of Communication. <em>Bell
 +Syst. Tech. J.</em> **<em>27,</em>** 379-423, 623-656. available on
 +[[http://opera.ieee.org|http://opera.ieee.org]]. </li> 
 +<li>Verdu, S. and Poor, V. (eds) (1998) <em>Fifty years of Shannon Theory.</em>
 +IEEE Press. also published in <em>IEEE Trans. Inform. Theory.,</em>
 +**44**<em>, 6,</em> october 1998. </li>
 +</ul>
 +
 +<h3>Équipe pédagogique</h3>
 +<table border="2">
 +<tr><td>S. Boucheron</td>
 +<td>CR</td>
 +<td>CNRS</td>
 +<td>LRI</td>
 +</tr></table>
 +</html>
  
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA