76304 - Information theory and Complexity

Academic Year 2017/2018

  • Docente: Marco Lenci
  • Credits: 6
  • SSD: MAT/07
  • Language: Italian
  • Teaching Mode: Traditional lectures
  • Campus: Bologna
  • Corso: Second cycle degree programme (LM) in Mathematics (cod. 8208)

Learning outcomes

Upon successful completion of this course, the student: - has acquired notions of information theory and algorithmic complexity, also from an applicational viewpoint; - is able to autonomously conduct further studies in the aformentioned topics and its applications.

Course contents

Entropy of a partition and of a random variable. Joint and conditional entropies. Relative entropy. Mutual information. Asymptotic Equipartition Lemma and Shannon-McMillan-Breiman Theorem for i.i.d. random variables. Application to data compression. Entropy rate for stationary stochastic processes. Description of the general Shannon-McMillan-Breiman Theorem. Applications. Codes. Kraft inequality. Optimal codes. Shannon code. Bounds on the efficiency of a code. Wrong codes. Huffman code. Shannon-Elias-Fano code. Universal codes. Algorithm LZ78. Algorithm LZW.

Turing Machines. Universal computers. Kolmogorov algorithmic complexity. Kolmogorov complexity and entropy. Complexity of integers and strings. Universal probability. Halting Problem. Chaitin's numbers. Relation between complexity and universal probability.

Readings/Bibliography

The reference textbook is:

T. M. Cover & J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley-Interscience

The course will be delivered at a slightly higher mathematical level that the textbook's. The purpose of this is to help the students (who have a mathematical modus operandi). A support text in this sense is:

Sinai, "Probability Theory", Springer

 

 

Teaching methods

Classroom lectures.

In case international students are attending, the lectures might be held in English.

Assessment methods

The grade will be assigned upon oral examination.

Each exam will include theoretical questions, questions on the applications of the material covered in the course, and the solution of at least one problem. In this way, the student will be evaluated both on his/her comprehension of the material and of its usefulness. The student's ability to perform simple computations will be evaluated as well.

Office hours

See the website of Marco Lenci