Introduction to Information Theory

Program: Bachelor Mathematics, Informatics, AI, Physics & Astronomy (WI, WInf, IN, KI, NS)
Lecturer: Michael Walter
Teaching assistants: Freek Witteveen
Schedule: Sept-Oct 2019
Further information: DataNose, Canvas

This is the official course homepage. All material will be provided here.

Course description

Reading your email on the metro may not strike you as particularly memorable. Isn’t it remarkable, though, that – despite relying on a noisy cellphone signal underground – none of your messages arrive corrupted? In this course you will learn the mathematics of how this is achieved.

This course will give an introduction to information theory – the mathematical theory of information. Ever since its inception in the 50s, information theory has had a profound impact on society. It underpins important technological developments, from reliable memories to mobile phone standards, and its versatile mathematical toolbox has found use in computer science, machine learning, physics, and even pure mathematics.

Starting from probability theory, we will discuss how to mathematically model information sources and communication channels, how to optimally compress and transmit information, and how to design error-correcting codes that allow us to reliably communicate over noisy communication channels. We will also see how techniques used in information theory can be applied more generally to make predictions from noisy data.

Students interested in writing a thesis in quantum information theory are also encouraged to follow Maris Ozol’s course Introduction to Quantum Computing.

Prerequisites

We will use rigorous definitions and proofs, hence some “mathematical maturity” will be assumed. Familiarity with basic probability theory will be expected (but we will remind you of the most important facts). In addition, some of the homework problems will require programming. You can use the programming language of your choice; examples and solution will be given in Python.

Lecture notes

A playlist of all lecture recordings can be founded here. 🎞

Main reference is David J. C. MacKay’s textbook “Information Theory, Inference, and Learning Algorithms”, Cambridge (2003), which is available online. 📖

Homework

Exercises classes

All exercises refer to MacKay’s textbook:

Learning Objectives

At the end of the course, you will be able to:

Format

Lectures, exercises classes, self-study.

Assessment

The final grade will be determined by the maximum of the following two options:

In addition, your exam grade alone has to be a passing grade. The same rule applies for the re-sit exam.

There will be one homework problem set per week (in total 6), posted on the course homepage by Friday. You must submit your completed homework before the exercise class on Friday the week after – either directly in the exercise class or by email to Freek Witteveen. The solutions will be discussed in the Friday exercise class (among other things).

If you have extenuating circumstances (such as sickness or family emergency) you must confirm with the lecturer before the deadline.

Everything that we discussed in class and on the homework is in principle in scope for the exam. We recommend that you revisit the homework problems and the exercises as a preparation. You are allowed to bring one self-prepared “cheat sheet” to the exam (A4 paper, hand-written, you can use both sides).