Théorie de l'Information - L.Moisan
Aperçu :
La théorie de l'information, inventée par Shannon en 1948, est non seulement
à la base de toutes les communications numériques actuelles, mais séduit aussi
par sa portée mathématique, physique, et philosophique qui va bien au-delà.
L'objectif de ce cours est de comprendre les concepts fondamentaux de la
théorie de l'information (à commencer par la notion d'entropie), ainsi que
ses applications à la construction d'arbres de décision, à la compression
de données, et à la communication en présence de bruit.
Prérequis: très peu de prérequis, seulement la notion de probabilité
conditionnelle (dans le cas discret) et des notions de programmation
en Scilab ou dans un autre langage.
Plan du cours (*** = avancement actuel) :
- Arbres de décision et entropie algébrique.
- Entropie probabiliste. Propriétés.
- Entropie conditionnelle. Information mutuelle. Distance de Kullback.
- Propriété d'équirépartition asymptotique. Suites typiques.
- Codage: codes réguliers, déchiffrables, complets, codes de préfixe.
- Inégalité de Kraft. Premier théorème de Shannon.
- Codage de Huffman, optimalité. Lien entre codage et détermination de stratégies optimales.
- Taux d'entropie de sources avec mémoire. Codage Lempel-Ziv.
- Communication à travers un canal bruité. Deuxième théorème de Shannon. Example du code de Hamming 7,4. ***
Dates et horaires des prochains cours :
Les cours ont lieu le vendredi de 9h à 11h45 ou de 8h à
11h45 certaines semaines
en salle CUNÉO F
(cours, TD) ou en salle 529 (TD/TP).
- vendredi 30 janvier : cours en salle Cunéo F
- vendredi 6 février : TD/TP en salle 529
- vendredi 13 février 8h-11h45 : cours en salle Cunéo F
séance annulée en raison du mouvement de grève général
de l'UFR de Mathématiques et Informatique.
- vendredi 20 février 8h-11h45 : cours en salle Cunéo F
- vendredi 6 mars 9h-11h45 : TD/TP en salle 529
- vendredi 20 mars 8h-11h45 : cours/TD en salle Cunéo F
- vendredi 27 mars 8h-11h45 : cours/TD en salle Cunéo F
- vendredi 3 avril 9h-11h45 : TD/TP en salle 529
- vendredi 10 avril 9h-11h45 : cours en salle Cunéo F (et distribution des projets)
- vendredi 24 avril 8h-11h45 : TD/TP en salle 529
- du 4 au 7 mai : suivi individuel des projets
- vendredi 29 mai à partir de 9h : soutenance des projets
Documents en ligne
Le document "Démarrer en Scilab" (PostScript, PDF)
L'article fondateur de Claude Shannon de 1948,
"A Mathematical Theory of Communication" (PDF)
Exercices 1 à 5 : arbres de décision et information (PDF)
Exercice 6 (TP) : construction d'un arbre de décision binaire (TXT) et fichier de données associé (animaux.dat)
Exercices 7 à 22 : entropie, codage, décision (PDF)
Exercice 23 : codage de Huffman (PDF)
Validation
La validation se fait par mini-projet. Chaque projet comprend une part
de programmation (variable selon les projets) qui peut être
réalisée dans le langage de votre choix.
Vous devrez me rendre, au moment de votre soutenance,
un rapport de quelques pages décrivant le travail réalisé, ainsi
qu'un listing de vos programmes et des résultats obtenus.
Pendant la "soutenance", vous devrez faire une petite présentation
(10-15 minutes) de votre travail au tableau ou avec un rétroprojecteur,
puis une démonstration sur ordinateur de vos programmes. Suivront
ensuite des questions portant sur le projet que vous avez réalisé
et plus généralement sur le contenu du cours, en lien avec votre projet.
Sujets des projets et fichiers de données associés:
- projet nº1: synthèse de textes (PDF)
- le fichier goriot.txt (531 ko)
- le site Gutenberg
- projet nº2: jeu du pendu (PDF)
- le fichier mots.txt (1,3 Mo)
- le fichier frequence_mots.txt (1,9 Mo)
Attention, pour le fichier frequence_mots.txt la fréquence de chaque mot
est obtenue en renormalisant le nombre associé par la somme de tous
les nombres. Le fichier mots.txt correspond simplement au premier
champ du fichier frequence_mots.txt. Ces deux fichiers contiennent
quelques mots erronés.
- projet nº3: codage arithmétique (PDF)
- voir complément scilab ci-dessous
- le fichier goriot.txt (531 ko)
- projet nº4: codes de Hamming concaténés (PDF)
- voir complément scilab ci-dessous
- projet nº5: communication à
travers des canaux inconnus (PDF NOUVELLE VERSION DU 27/04/2009)
- fichier canal1 et mode d'emploi (fichiers canal2, canal3 et canal4 communiqués individuellement par mail)
- voir complément scilab ci-dessous
Des fonctions utiles (lecture de fichier, calcul binaire, codage de Hamming)
sont données dans le fichier
complement_scilab.txt.
La consultation
de ce fichier peut vous être utile même si vous ne choisissez pas Scilab
comme langage de programmation.
Calendrier des projets:
- vendredi 10 avril : distribution des sujets
de projets
- mardi 28 avril : date limite pour le choix des projets (me communiquer votre choix par mail)
- du 4 au 7 mai : suivi individuel des projets
- vendredi 29 mai à partir de 9h : soutenance des projets
Choix de projets:
Jérôme Demantke: projet nº3
Madiké Diouf: projet nº4
Louis Eymard: projet nº5
Zarinah Jeeawoody: projet nº4
Li Jia: projet nº3
Amine Joulal: projet nº5
Damir Mohamed: projet nº5
Rokhy Sarr: projet nº4
Christian Theriault: projet nº5
Nghia-Khang Tran: projet nº2
Samuel Vaiter: autre
Melki Young: projet nº2
Suivi des projets:
Ce rendez-vous individuel de 20 à 30 minutes environ est destiné
à vous aider dans la réalisation de votre projet. Vous devez
avoir commencé significativement à travailler sur votre projet
pour qu'il soit efficace (plus votre travail sera avancé, plus
ce rendez-vous vous aidera à améliorer votre projet).
mardi 5 mai 15h: Samuel Vaiter
mercredi 6 mai 10h: Damir Mohamed
mercredi 6 mai 10h30: Jérôme Demantke
mercredi 6 mai 11h45: Melki Young
jeudi 7 mai 9h30: Rokhy Sarr
jeudi 7 mai 10h30: Zarinah Jeeawoody
jeudi 7 mai 11h: Li Jia
jeudi 7 mai 11h45: Christian Theriault
jeudi 7 mai 12h10: Louis Eymard
jeudi 7 mai 15h30: Madiké Diouf
Soutenance des projets
vendredi 29 mai, salle 508
9h15: Louis Eymard
9h45: Damir Mohamed
10h15: Christian Theriault
10h45: Amine Joulal
11h15: Nghia-Khang Tran
11h45: Melki Young
13h: Jérôme Demantke
13h30: Li Jia
14h: Samuel Vaiter
14h30: Madiké Diouf
15h: Zarinah Jeeawoody
15h30: Rokhy Sarr
Rappel: vous devrez me rendre, au début de votre soutenance,
un rapport de quelques pages décrivant le travail réalisé, ainsi
qu'un listing de vos programmes et des résultats obtenus.
Pendant la soutenance, vous devrez faire une petite présentation
(10-15 minutes) de votre travail au tableau ou avec un rétroprojecteur,
puis une démonstration sur ordinateur de vos programmes. Suivront
ensuite des questions portant sur le projet que vous avez réalisé
et plus généralement sur le contenu du cours, en lien avec votre projet.
Quelques références bibliographiques :
O. Rioul, Théorie de l'Information et du Codage,
Hermès Science - Lavoisier, 2007.
C. Shannon, "A Mathematical Theory of
Communication", The Bell System Technical Journal, 1948.
T. Cover, J. Thomas, Elements of Information Theory, Wiley, 1991.
D. MacKay, Information Theory, Inference, and Learning Algorithms,
Cambridge University Press, 2003.
Dernière mise à jour : 7 mai 2009