IFT6080: Théorie de l'information

(Sujets en exploitation des ordinateurs)

Hiver 2021

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. Vous pouvez consulter le site web du cours de l'an dernier pour plus d'information sur la matière qui sera couverte.

This course is about information theory, a discipline founded by Claude Shannon in 1948. This theory provides methods that allow us to quantify the amount of information contained in a random variable as well as correlations between random variables. These concepts can then be applied in a wide variety of settings, such as data compression, telecommunications (how can we transmit digital data over noisy channels?), cryptography (how can we quantify how much information an eavesdropper has acquired about some private data?), statistical inference, thermodynamics, etc. You can have a look at the website for last year's course to have a better idea of the topics covered.

• Les mercredis de 15h30 à 17h30 (Sur Zoom: contactez-moi si vous voulez le lien, j'hésite à les rendre trop publics -- Contact me directly if you want the Zoom links, I'd rather not post them publicly.)
• Les jeudis de 16h30 à 18h30

Les cours seront enregistrés et mis à votre disposition au fur et à mesure sur la page Studium du cours. -- Lectures will be recorded and made available on the course's Studium page as the course progresses.

Le premier cours aura lieu le jeudi 14 janvier -- The first lecture will take place on Thursday Jan 14.

Évaluation

• Au moins 4 devoirs (et possiblement un 5ième) (60%) At least 4 problem sets, possibly 5 (60%).
• Présentation d'environ 30 minutes sur un article choisi parmi une liste qui sera fournie ultérieurement (ou un article de votre choix que j'aurai approuvé) (40%). ~30 min oral presentation on a paper chosen from a list that I will supply later (or a paper of your choice, subject to my approval) (40%).

Plan de cours

• Révision des probabilités et des variables aléatoires. Review of probability theory and random variables.
• Mesures d'incertitude et d'information: entropie, entropie relative, entropie conditionnelle, information mutuelle. Measures of uncertainty and information: entropy, relative entropy, conditional entropy, mutual information.
• Compression de données: inégalité de Kraft, codage de Shannon, codage de Huffman. Data compression: Kraft inequality, Shannon coding, Huffman coding.
• Types et séquences typiques. Équipartition asymptotique. Types and typical sequences. Asymptotic equipartition property.
• Transmission de données sur canaux bruités. Théorème de Shannon. Data transmission over noisy channels; Shannon's theorem.
• Codes aléatoires, codes linéaires, codes de Reed-Solomon, codes polaires. Random codes, linear codes, Reed-Solomon codes, polar codes.
• Algorithme somme-produit, codes LDPC. Sum-product algorithm, LDPC codes.
• Variables continues, canaux gaussiens. Continuous variables, Gaussian channels.

Ressources

• Notes de cours qui seront mises à jour au fur et à mesure -- An English version of the lecture notes will be provided as the course progresses. (Dernière mise à jour: 19 janvier)
• [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)

Sujets de présentation

• Coding for channels with side-information at the transmitter: Max Costa, Writing on dirty paper
• Broadcast channels: Katalin Marton, A coding theorem for the discrete memoryless broadcast channel
• The Blahut-Arimoto algorithm: Richard Blahut, Computation of channel capacity and rate-distortion functions et Suguru Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless channels
• Geometric programming: Mung Chiang, Geometric programming for communication systems
• Quantum information theory: Nielsen and Chuang, Quantum computation and quantum information, or Mark Wilde, From classical to quantum Shannon theory (Not recommended if you have no prior experience with quantum mechanics!)
• Raptor codes: Amin Shokrollahi, Raptor codes
• Rate-distortion theory (i.e. lossy compression): [CT, Ch. 13]
• (Julien?) Zero-error channel capacity: Claude Shannon, The zero error capacity of a noisy channel (article original de Shannon sur le sujet), László Lovász, On the Shannon capacity of a graph, Noga Alon et Eyal Lubetzky, The Shannon capacity of a graph and the independence numbers of its powers
• Information theory and financial portfolios: [CT, Ch 6 et 15]
• (Ashutosh) Strong converse for channel coding
• Votre sujet préféré que je n'ai pas listé ici (mais demandez-le moi avant!) Your favorite topic I haven't listed here (but ask me first!)