# Introduction to Information Theory

Information theory is the science of operations on data such as compression, storage, and communication. This course is a basic introduction to information theory at the graduate or advanced undergraduate level. Prerequisites include a basic knowledge of elementary probability, which, however, will be reviewed in the first weeks. The first central notions covered are entropy and variable length encoding, leading to the noiseless coding theorem of Claude Shannon (1948) which relates the average codeword length for an encoding of a source to its entropy. However, when information must be transmitted over a noisy channel, one must reconsider how to encode information efficiently while minimizing the probability of uncorrected errors in the transmission. This leads to the notion of channel capacity and, finally, the famous noisy coding theorem. Measures of information and uncertainty like entropy, mutual information, and relative entropy have applications in many diverse fields, e.g., pattern recognition, computer vision, and plagiarism detection, some of which will be studied at the end of the course. References include S. Roman, Coding and Information Theory, Graduate Texts in Mathematics, Springer, 1994, and T. M. Cover and J. A. Thomas, Elements of Information Theory, Second Edition, Wiley, 2006.

A part of the book on information theory: index.php?eID=tx_nawsecuredl&u=0&g=0&t=1506207693&hash=a4b5d07e4ec1b6bdcc4a2e6110d2219215e0416c&file=fileadmin/informatik/ag-saupe/Images/Coding_and_Information_Theory.pdfPDF

A short review of basic (discrete) probability theory: index.php?eID=tx_nawsecuredl&u=0&g=0&t=1506207693&hash=6426266ebe49356f9a3c98dab42c71d4b8b53b92&file=fileadmin/informatik/ag-saupe/Images/Pattern_Classification.pdfPDF

List of homework assignments (weeks are calendar weeks):

Week 16 / 2012: PDF

Week 17 / 2012: PDF

Week 18 / 2012: PDF

Week 19 / 2012: Problems 10, 11 on page 29 of the book

Week 20 / 2012: Problems 8, 9 on page 29 and problem 3, page 37 of the book. Finally, try problem 8, page 38.

This is a hard problem: do the easy case q = 0 first, using the equalities in exercise 1, then do the general case.

Week 21 / 2012: problems 1, 2, 3, 15, 16, 17 on pages 50, 51

Week 22 / 2012: lecture and problem session cancelled

Week 23 / 2012: problems 4, 10, 12 on page 61

Week 24 / 2012: problems 13, 14 on page 61

Week 25 / 2012: problems 7, 9 on page 66

Week 26 / 2012: problems 6, 15, 17 on page 79

Week 27 / 2012: problems 2, 3, 6, 16 on page 86

Week 28 / 2012: lecture and problem session postponed, new date t.b.a.

Class and Problem Session, Wed 9:00 - 12:15, Z 613

Exam (oral) Tuesday, July 31, 2012, 14:00h

Exam (makeup) Tuesday, October 16, 2012, 14:00h