Information-Theoretic Modeling
Exam
Lectures
Time | Room | Lecturer | Date |
---|---|---|---|
Wed 10-12 | C222 | Jyrki Kivinen | 05.09.2012-12.10.2012 |
Fri 10-12 | C222 | Jyrki Kivinen | 05.09.2012-12.10.2012 |
Exercise groups
Time | Room | Instructor | Date | Observe |
---|---|---|---|---|
Tue 10-12 | C220 | Hannes Wettig | 10.09.2012—12.10.2012 |
General
The course has ended. Thanks to everyone who participated.
- course results
- exam problems
- comments on the grading of the exam (graded by Hannes Wettig)
You still have a little time to fill in the course feedback form, if you haven't done that yet. The lecturer's reply to the feedback, and some other comments on the course, will appear in this space soon.
The content of the course was mainly the same as in the Autumn 2009 version lectured by Teemu Roos.
Prerequisites
The course has no formal prerequisites. Familiarity with basic concepts and manipulations from probability theory and calculus is however essential for successfully participating in the course.
Contents
- basic concepts of information theory: entropy, mutual information etc.
- lossy coding, noisy channel coding theorem
- lossless source coding, theory: Shannon's theorem, Kraft's inequality
- important lossless codes: Shannon-Fano, Huffman, arithmetic
- universal codes and minimum description length (MDL)
- Kolmogorov complexity
Completing the course
The course consisted of weekly exercise sessions (beginning from week 2) and a course exam. Sufficient participation in the exercises was compulsory.
This course is a prerequisite for 582651 Project in Information-Theoretic Modeling in the next period. The project is not a part of this course, but doing also the project is highly recommended.
Literature and material
There is no textbook. The homework and exam will be based on the lectures. The lecture material will appear on this page.
Lecture notes
- Lecture 1 (5 September): course administration, introductory examples. We covered these slides except for the last example (noisy channel coding), which was covered on 7 September
- Lecture 2 (7 September): mathematical preliminaries. We covered parts 1 (calculus) and 2 (probabilities), leaving part 3 (inequalities) until 12 September.
- Lecture 3 (12 September): we covered entropy, mutual information and basic inequalities. AEP was left for Friday.
- Lecture 4 (14 September): noisy channels, capacities and rates, channel coding theorem. Hamming codes were left for next week.
- Lectures 5 and 6 (19 and 21 September): prefix codes, Kraft inequality. Shannon coding, Huffman coding.
- Lecture 7 (26 September): arithmetic coding
- Lecture 8 (28 September): universal source coding, two-part codes, other universal codes
- Lecture 9 (3 October): MDL principle
- Lecture 10 (5 October): more MDL principle: examples and some technicalities
- Lecture 11 (10 October): Kolmogorov complexity (we did not cover gambling)
- Last lecture (12 October): we had a guest lecture by Teemu Roos and a quick summary of the course.
Exercises
Exercise sessions will be held on Tuesdays at 10:15–12:00 in classroom C220.
- Homework 1 (September 11): problems, solutions
- Homework 2 (September 18): problems, solutions
- Homework 3 (September 25): problems, files, solutions
- Homework 4 (October 2): problems, solutions
-
Homework 5 (October 9): problems, files, solutions
Added 4 October: Filling in the course feedback form counts as one problem for this homework.
Recommended extra reading
- Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley 2006 (2nd edition).