Vai al contenuto principale
Se prosegui nella navigazione del sito, ne accetti le politiche:
  • Condizioni di utilizzo e trattamento dei dati
Prosegui
x
Se prosegui nella navigazione del sito, ne accetti le politiche:
  • Condizioni di utilizzo e trattamento dei dati
Prosegui
x
e-Learning - UNIMIB
  • Home
  • Altro
Ascolta questa pagina con ReadSpeaker
Italiano ‎(it)‎
English ‎(en)‎ Italiano ‎(it)‎
 Login
e-Learning - UNIMIB
Home
Percorso della pagina
  1. Area di Scienze
  2. Corso di Laurea Magistrale
  3. Matematica [F4002Q - F4001Q]
  4. Insegnamenti
  5. A.A. 2023-2024
  6. 1° anno
  1. Sistemi Dinamici, Informazione, Complessità
  2. Introduzione
Insegnamento Titolo del corso
Sistemi Dinamici, Informazione, Complessità
Codice identificativo del corso
2324-1-F4001Q116
Descrizione del corso SYLLABUS

Syllabus del corso

  • Italiano ‎(it)‎
  • English ‎(en)‎
Esporta

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:

  1. 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.
  2. 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.
  3. 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.
Il corso è previsto in lingua italiana ma potrebbe essere tenuto in lingua inglese in presenza di studenti stranieri.

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

Non sono previste prove parziali.
L'esame finale consiste in una prova 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.

Esporta

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:

  1. Examples of discrete-time dynamical systems. Elements of topological dynamics. Symbolic dynamics. Ergodic theory. Kolmogorov-Sinai entropy.
  2. 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.
  3. 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

Lectures with blackboard.
Lectures are scheduled in Italian but they could be held in English in the presence of foreign students.

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

There are not partial exams. The final evaluation will be an 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.

Entra

Scheda del corso

Settore disciplinare
MAT/07
CFU
8
Periodo
Secondo Semestre
Tipo di attività
Obbligatorio a scelta
Ore
56
Tipologia CdS
Laurea Magistrale
Lingua
Italiano

Staff

    Docente

  • GC
    Giampaolo Cristadoro

Opinione studenti

Vedi valutazione del precedente anno accademico

Bibliografia

Trova i libri per questo corso nella Biblioteca di Ateneo

Metodi di iscrizione

Iscrizione manuale
Iscrizione spontanea (Studente)

Non sei collegato. (Login)
Politiche
Ottieni l'app mobile
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy
  • Accessibilità
  • Statistiche