The course aims at providing the basic elements on the connection between the methods of statistical physics and the most important problems of information theory. This connection will be made explicit with the discussion of examples taken from typical combinatorial optimization problems such as the number partitioning problem or the minimum spanning tree, so that students can see the algorithms used to address them and the corresponding treatment based on statistical physics methods.

- Knowledge and understanding: Acquire knowledge of
fundamental concepts of statistical physics and the techniques with which they can be applied to problems of information theory and combinatorial optimization.

- Applied knowledge and understanding: Acquire the ability
to critically understand the applications of statistical physics to information theory and their interconnections.

- Independent judgment:
Enable the student to apply the concepts and tools learned in a critical way, checking the logical coherence of the proposed arguments.

- Communication skill: Making the student capable of explaining the knowledge learned and capable of transmitting it to others; to be able to frame a specific problem in a broader context.

- Ability to learn: Enable the student to critically learn concepts and resolution tools.

Basic elements of analysis and linear algebra.

1) Random variables and entropy 2) Correlated variables 3) Data transmission and compression 4) Basic notions of combinatorial optimization and reminder on complexity computational 5) The Boltzmann distribution 6) Notes on statistical mechanics models relevant for combinatorial optimization and coding problems 7) Notes on large deviations for independent variables 8) The random energy model and the random code ensemble 9) Number partitioning and its treatment with statistical physics methods 10) Notes on belief propagation

M. Mezard and A. Montanari: Information, Physics and Computation

Random variables, entropy and sequences of random variables

Correlated variables and their study using the entropy

Notions of probability theory: sum of i.i.d. variables and connection with the central limit theorem

Fundamentals of information theory: codes, channels and Shannon theorems

Notions of statistical physics of spins systems
and their connection with the problems covered in the first part of the course

Discussion of specific examples (Ising variables, one/two spins, chains, mean field)

Problems of combinatorial optimization: examples and their computational complexity

Large deviations and fluctuation-dissipation theorem

Definition and thermodynamics of the random energy model - its application to coding problems

Number partitioning problem - study of the associated statistical physics model

Belief propagation method - belief propagation on trees

Lectures on the blackboard / tablet - exercises - simple numerical
simulations.

Written and oral exam. The final grade takes into account the ability to correctly solve and clearly discuss the proposed exercises and topics. The written test consists of carrying out exercises on Probability Theory, Statistical Physics, Information Theory and Combinatorial Optimisation. The written test is made up of 4 exercises divided into 3 or 4 points to be carried out commenting on the results obtained. To each exercise is given a score from 8 to 10. The maximum score for an exercise is assigned to carry out the exercise clearly and correctly. The grade of the writing is equal to the sum of the marks obtained in the individual exercises. The student is admitted to the oral exam if it is obtained at least the score in the written exam minimum of 18. The oral exam focuses on the part of statistical physics and its applications to information theory. The questions focus on definition of basic concepts and reasoned understanding of the concepts studied. The oral exam is assigned a score out of 30 (independent of the score obtained in the written exam). The final vote average the grade obtained in the written test with the evaluation reported in the oral exam (which must be at least 18/30).

9 - Industries, innovation and infrastructure