- Docente: Marco Lenci
- Crediti formativi: 6
- SSD: MAT/07
- Lingua di insegnamento: Italiano
- Modalità didattica: Convenzionale - Lezioni in presenza
- Campus: Bologna
-
Corso:
Laurea Magistrale in
Matematica (cod. 5827)
Valido anche per Laurea Magistrale in Matematica (cod. 8208)
Conoscenze e abilità da conseguire
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.
Contenuti
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.
Testi/Bibliografia
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
Metodi didattici
Classroom lectures (with possibly a few pre-recorded video lectures).
Modalità di verifica e valutazione dell'apprendimento
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.
Strumenti a supporto della didattica
Extra material (further readings, videos, etc.) will be suggested throughout the class and posted on Virtuale.
Orario di ricevimento
Consulta il sito web di Marco Lenci