IFT6080: Théorie de l'information
(Sujets en exploitation des ordinateurs)
Hiver 2020
Information générale
Ce cours traitera de la théorie de l'information fondée par Claude Shannon en 1948. Cette théorie fournit des méthodes permettant de mesurer la quantité d'information contenue dans une variable aléatoire, ainsi que les corrélations entre différentes variables. Ces concepts peuvent ensuite s'appliquer à une foule de domaines, comme la compression de données, les télécommunications (comment gérer le bruit?), la cryptographie (comment quantifier l'information détenue par un espion?), l'inférence statistique, la thermodynamique, etc.Les cours auront lieu:
- Les mercredis de 15h30 à 17h30 (
AA-1207changement de salle: AA-3195!) - Les jeudis de 16h30 à 18h30 (Z-260)
- NOTE: Le cours du jeudi 27 février est annulé!
Évaluation
Il n'y aura finalement que 4 devoirs, qui compteront pour 50% de la note, ainsi que l'examen final à faire à la maison, qui comptera également pour 50% de la note finale. Vous aurez 24h pour faire l'examen, et il sera à remettre sur Studium. L'examen aura lieu le 22 avril; l'examen sera disponible dès 9h, et sera à remettre sur Studium avant 9h le 23 avril.
Ressources
- Notes de cours (dernière mise à jour: 16 avril 2020)
- [CT] Thomas Cover et Joy Thomas, Elements of information theory (livre)
- [CK] Imre Csiszár et János Körner, Information theory: Coding theorems for discrete memoryless systems (livre)
- [C] Imre Csiszár, The method of types (article)
- [S] Nicolas Sendrier, Introduction à la théorie de l'information (notes de cours)
- [GRS] Venkatesan Guruswami, Atri Rudra et Madhu Sudan, Essential Coding Theory (livre sur les codes correcteurs)
- [KFL] Frank Kschischang, Brendan J. Frey et Hans-Andrea Loeliger, Factor Graphs and the Sum-Product Algorithm (article sur l'algorithme somme-produit)
Devoirs
- Devoir 1, à remettre le jeudi 6 février.
- Devoir 2, à remettre le mercredi 26 février.
- Devoir 3, à remettre le
jeudi 19 marslundi 30 mars sur Studium. - Devoir 4, à remettre le
jeudi 16 avrildimanche 19 avril.
Matière vue en cours
| Date | Matière | Références |
|---|---|---|
| 8, 9 jan | Introduction, admin, révision des probabilités et variables aléatoires. Définitions de base. | Notes de cours, [CT Ch 2]. |
| 15, 16 jan | Entropie relative et propriétés. Compression de données: inégalité de Kraft, codage de Shannon, codage de Huffman. | Notes de cours, [CT Ch 2 et 5]. |
| 22, 23 jan | Compression de données: preuve d'optimalité du codage de Huffman, Lempel-Ziv. Courses de chevaux (!). Début des types et séquences typiques. | Notes de cours, [CT Ch 5] (compression) et [CT Ch 6] (courses de chevaux). |
| 29, 30 jan | Types et séquences typiques. Introduction aux codage sur canaux bruités. | Notes de cours, [C], [CT, Ch 8]. |
| 5, 6 fév | Codage sur canaux bruités. Théorème de Shannon, canal binaire symétrique, canal binaire à effacement. | Notes de cours, [C], [CT, Ch 8] |
| 12, 13 fév | Codes linéaires: introduction, définitions. Codes linéaires aléatoires. | Notes de cours, [GRS]. |
| 19, 20 fév | Polynômes sur corps finis, codes de Reed-Solomon. | Notes de cours, [GRS]. |
| 26, 27 fév | Codes de Reed-Solomon: correction d'erreur et d'effacements. Partage de secret à la Shamir. | Notes de cours, [GRS]. |
| 11, 12 mars | Codes polaires: construction, preuve de polarisation. | Notes de cours, [GRS]. |
| 25, 26 mars | Codes polaires: décodage. Algorithme somme-produit. | Notes de cours, [GRS], [KFL]. |
| 1er, 2 avril | Algorithme somme-produit, variables continues. | Notes de cours, [KFL], [CT, Ch 9]. |
| 8, 9 avril | Canaux gaussiens. Théorie de l'information one-shot: intro, compression de données | Notes de cours, [CT, Ch 9-10]. |
| 15, 16 avril | Théorie de l'information one-shot: Extraction d'aléa, transmission sur canaux bruités, lissage | Notes de cours. |
Cours en direct
- 25 mars: [1][2]
- 26 mars: [Cours][Exercices]
- 1er avril: [Cours]
- 2 avril: [Jitsi], [Cours]
- 8 avril: [1][2]
- 9 avril: [Cours]
- 15 avril: [Cours]
- 16 avril: [Cours]