- Lectures
- Omar Fawzi & Stephan Thomasse
- Default time is fridays 10:15-12:15 but multiple exceptions to be expected
- Amphi B

- Tutorials
- Tien-Nam Le & Eugenia Oschurku
- Mondays 10:15 - 12:15

- Definition and properties of entropy functions
- Data compression
- Shannon's noisy coding theorem
- Applications of information theory to combinatorics, cryptography, complexity theory
- Error correcting codes: Definitions, properties and examples
- Applications of error correcting codes

- [CT] Elements of Information Theory
- [Mac] Information Theory, Inference and Learning Algorithms
- [PW] Lecture notes on Information Theory
- [GRS] Essential Coding Theory
- [Sen] Introduction a la theorie de l'information

- A final exam
- One midterm exam
- Homeworks (every 1 or 2 weeks)
- Small project, such as writing a wikipedia article (bonus)

Date | Topic | References |

Tue Sep 12th 10:15-12:15 | Admin. Overview of the fundamental problem of noisy channel coding. Definition of entropy. |
Ch 1 of [Mac], Ch 2 of [CT], Shannon's paper |

Wed Sep 13th 15:45-17:45 | Conditional entropy, mutual information, relative entropy. Data compression, variable-length lossless compressor. |
Ch 8.1 of [PW], Ch 4 of [Mac], Ch 2,3,5 of [CT] |

Fri Sep 22nd 9:00-12:00 |
Continuing variable-length coding. Prefix codes, Kraft's inequality, H(X) < L(C) < H(X)+1. Fixed-length compression, general bounds in terms of the tail probabilities for the surprisal h_X(X). Special case of memoryless sources: Shannon's source coding theorem. |
Ch 8.2 of [PW], Ch 5,6 of [Mac], Ch 5 of [CT], Ch 9.1 of [PW] |

Fri Oct 13th 9:00-12:00 |
Universal compression: arithmetic coding and Lempel-Ziv. Channel coding: Information capacity of a channel. Additivity of information capacity for independent channels. Converse bounds |
Ch 16.1 of [PW], Ch 6 of [Mac], Ch 16.3 [PW], Ch 7 of [CT]. |

Fri Oct 27rd 9:00-12:00 |
Achievability bounds. Shannon noisy coding theorem. |
Ch 16.4 [PW], Ch 7 of [CT] |

Fri Nov 10th 10:15-12:15 | Midterm exam |