Syllabus del corso
Obiettivi
l corso si propone di fornire allo studente
- le conoscenze di nozioni di base della moderna teoria dei sistemi dinamici, della teoria dell’informazione e della complessità algoritmica;
- le competenze utili a comprendere i metodi dimostrativi connessi alla teoria ed a condurre in modo autonomo l’approfondimento di alcune delle tematiche sopra citate;
- le abilità necessarie all’applicazione delle nozioni acquisite allo studio di sistemi dinamici elementari, alla risoluzione di esercizi di diversi gradi di difficoltà, all’analisi anche computazionale di sequenze simboliche di diversa natura, con particolare attenzione alle applicazioni in campo biologico e letterario.
Contenuti sintetici
Il corso intende fornire allo studente una conoscenza approfondita del quadro teorico necessario allo studio e analisi di sequenze simboliche di diversa natura. I principali contenuti comprendono: approccio statistico ai sistemi dinamici, sorgenti di informazione, contenuto di informazione algoritmica.
Programma esteso
Il corso è suddiviso in tre parti:
- Esempi di sistemi dinamici a tempo discreto. Cenni di dinamica topologica. Dinamica simbolica. Ricorrenza, misure invarianti ed ergodiche. Teoremi ergodici. Mescolamento. Entropia di Kolmogorov-Sinai.
- Entropia di Shannon. Entropia relativa, mutua informazione. Equipartizione asintotica. Tasso di entropia per processi stocastici stazionari. Codici: disuguaglianza di Kraft, codici ottimali, stima dell’efficienza di un codice. Compressori universali. Algoritmo LZ78.
- Macchine di Turing. Calcolatori universali. Complessità algoritmica di Kolmogorov. Probabilità universale. Problema dell’arresto. Numero di Chaitin. Teorema di Brudno.
Prerequisiti
È sufficiente avere familiarità con le conoscenze, competenze e abilità apprese durante la laurea triennale, in particolare nei corsi di Sistemi Dinamici e Meccanica Classica, Teoria della Misura e Calcolo delle Probabilità.
Modalità didattica
Lezioni frontali, con uso di lavagna.
Materiale didattico
Non c’è un unico testo che copra tutti gli argomenti del corso, di conseguenza verranno dati di volta in volta dal docente riferimenti opportuni. Verranno inoltre fornite note del docente per alcune parti del corso.
Gran parte degli argomenti trattati si possono trovare nei testi seguenti:
- M.Brin & G. Stuck, "Introduction to Dynamical Systems", Cambridge University Press. 2002 (1 copia disponibili al prestito in biblioteca; (e-book disponibile sul sito della biblioteca)
- P.Walters, “An Introduction to Ergodic Theory”, GTM 89, Springer-Verlag (2 copie disponibili al prestito in biblioteca; (e-book non disponibile in biblioteca)
- T. M. Cover & J. A. Thomas, “Elements of Information Theory”, 2nd ed., Wiley-Interscience (2 copie disponibili al prestito in biblioteca; (e-book disponibile sul sito della biblioteca)
- M.Li, P.Vitányi, “An Introduction to Kolmogorov Complexity and Its Applications”, second edition, GTCS, Springer-Verlag, 1997; (e-book disponibile sul sito della biblioteca)
Periodo di erogazione dell'insegnamento
II semestre.
Modalità di verifica del profitto e valutazione
Esame orale, della durata indicativa di 45 minuti in cui lo studente verrà valutato sia sull'apprendimento delle nozioni da un punto di vista matematico (definizioni, enunciati, dimostrazioni) che sulla loro utilità (esempi presentati durante il corso), nonché sulla capacità di maneggiarle in autonomia. In via facoltativa lo studente può integrare il colloquio con la presentazione di un progetto di stampo applicativo o di un approfondimento teorico su argomenti di interesse. La scelta dell'argomento della parte facoltativa va concordata in anticipo col docente. La valutazione dell'eventuale progetto/approfondimento peserà per 1/2 sul giudizio finale.
Orario di ricevimento
Su appuntamento.
Aims
At the end of the course, students will have acquired the following:
- knowledge: some of the basic results of the modern theory of Dynamical Systems, Information theory and Algorithmic Complexity;
- competence : understanding of the techniques and methods related to the theory together with the ability to deepen specific topic independently;
- skills: useful to apply the theory to the investigation of some simple dynamical systems, to solve exercise of increasing level of difficulty, to analyse (even computationally) symbolic sequences of different origin, with particular attention towards applications to biological or literary data.
Contents
The course aims to provide the student with an in-depth knowledge of the theoretical framework underlying the analysis of symbolic sequences of different origin. The main contents include: statistical approach to dynamical systems, information sources, algorithmic information content.
Detailed program
The course is divided into three parts:
- Examples of discrete-time dynamical systems. Elements of topological dynamics. Symbolic dynamics. Ergodic theory. Kolmogorov-Sinai entropy.
- Shannon entropy. Relative entropy, mutual information. Asymptotic equipartition. Entropy rate for stationary stochastic processes. Codes: Kraft inequality, optimal codes, efficiency of a code. Universal compressors. LZ78 algorithm.
- Turing machines. Universal machines. Kolmogorov algorithmic complexity. Universal probability. Halting problem. Chaitin's number. Brudno's theorem.
Prerequisites
No course of the Master Degree in Mathematics is strictly required for attending the present course. The only prerequisites are the mathematical knowledge, competences and skills acquired during the three-year grade, especially in the courses of Dynamical Systems and Classical Mechanics, Measure Theory, Probability.
Teaching form
Textbook and teaching resource
There is not a single textbook covering all topics.
Many of the topics are covered by:
- M.Brin & G. Stuck, "Introduction to Dynamical Systems", Cambridge University Press. 2002 (1 copia disponibili al prestito in biblioteca; (e-book online)
- P.Walters, “An Introduction to Ergodic Theory”, GTM 89, Springer-Verlag (2 copie disponibili al prestito in biblioteca; (e-book not available)
- T. M. Cover & J. A. Thomas, “Elements of Information Theory”, 2nd ed., Wiley-Interscience (2 copie disponibili al prestito in biblioteca; (e-book online)
- M.Li, P.Vitányi, “An Introduction to Kolmogorov Complexity and Its Applications”, second edition, GTCS, Springer-Verlag, 1997; (e-book online)
Lecture notes will be distributed covering all the arguments.
Semester
II Semester.
Assessment method
Oral exam (of about 45 minutes) in which the student will be assessed both on mathematical aspects of the theory (definitions, statements, proofs), on the application of the theory (examples discussed during lectures), as well as on the ability to handle the topic independently. Optionally, the student can integrate the exam with the presentation of a project (the choice of the project should be discussed in advance with the instructor). In this case, the relative weight of the project and of the oral examination is equal.
Office hours
Upon appointment.
Scheda del corso
Staff
-
Giampaolo Cristadoro