Description
Sont exposés les fondamentaux de la théorie de l’information, mesures d’incertitude,
entropie de Shannon, applications à la compression de données et à la protection contre
des erreurs. Le cours s’articule autour des notions suivantes:
- Entropie, entropie conditionnelle, information mutuelle
- Compression, algorithme de Huffman
- Canaux discrets sans mémoire, capacité, théorème de Shannon
- Initiation à la théorie des codes correcteurs. Application cryptographique aux canaux wiretap.
La théorie de l’information est née avec la publication en 1948 de l’article fondateur de Claude Shannon « A Mathematical Theory of Communication ». Peu de temps après, Shannon publie l’article
« Communication Theory of Secrecy Systems » qui met en avant la première approche mathématique de
la cryptographie et qui s’appuie fortement sur la notion d’information. Aujourd’hui, la notion de
sécurité inconditionnelle en cryptographie, où l’on n’impose aucune contrainte sur la
puissance de calcul de l’adversaire, relève directement de la théorie de Shannon.
Références
- G. Zémor, Notes de cours.
- T. M. Cover et J. A. Thomas, Elements of Information Theory, 2006 Wiley.
- M. Sudan, Course Notes on Coding Theory.
- V. Guruswami, Information Theory and its applications in theory of computation, Spring 2013 (avancé).