- 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. 5827)
Also valid for Second cycle degree programme (LM) in Mathematics (cod. 8208)
Learning outcomes
Upon successful completion of the course, the student: - has acquired then most important notions of information theory and the fundamentals of the theory of algorithmic complexity, also with reference to applications; - is able to autonomously conduct further studies, computational implementations and devise applications related to the aformentioned topics.
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). Good support texts in this sense are:
Ya. G. Sinai, "Probability Theory", Springer
R. Durrett, "Probability: Theory and Examples", Cambridge
Teaching methods
Classroom lectures (with possibly a few pre-recorded video lectures).
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.
Teaching tools
Extra material (further readings, videos, etc.) will be suggested throughout the class and posted on Virtuale.
Office hours
See the website of Marco Lenci