# 76304 - TEORIA DELL'INFORMAZIONE E COMPLESSITA'

• 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. 8208)

Valido anche per Laurea Magistrale in Matematica (cod. 5827)

## Conoscenze e abilità da conseguire

Al termine del corso, lo studente: - possiede nozioni approfondite di teoria dell'informazione e della complessità algoritmica nei loro principali aspetti applicativi; - è in grado di condurre autonomamente l'approfondimento anche computazionale, delle tematiche sopra citate.

## 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