Metodi probabilistici per l'informatica

A.A. 2024/2025
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
Questo insegnamento è dedicato allo studio delle tecniche e degli strumenti probabilistici utilizzati in generale in vari settori dell'informatica. In particolare un obiettivo specifico è quello di rendere familiare agli studenti l'utilizzo di metodi e nozioni di carattere probabilistico nella progettazione e nell'analisi di algoritmi randomizzati.
Risultati apprendimento attesi
Un primo risultato atteso consiste nella conoscenza di un corpo di nozioni e proprietà probabilistiche usate nella progettazione di algoritmi e in generale nelle applicazioni di carattere informatico e computazionale. Lo studente apprenderà a svolgere ragionamenti e dimostrazioni di tipo probabilistico in contesti di carattere informatico. In particolare ci si attende che impari ad applicare a nuovi semplici problemi i metodi e le tecniche probabilistiche studiate nell'analisi di classici algoritmi randomizzati.
Corso singolo

Questo insegnamento può essere seguito come corso singolo.

Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre

Programma
1. Richiami di calcolo delle probabilità.
Variabili aleatorie discrete e continue, funzioni densità e distribuzione, momenti, esempi classici.
Disuguaglianze di Markov e di Chebychev. Disuguaglianza di Chernoff e sue applicazioni. Generalità sui processi stocastici. Cenni ai processi di Poisson.
2. Introduzione agli algoritmi probabilistici.
Classificazione: algoritmi Las Vegas, 1-sided error, a errore limitato e illimitato. Metodi di riduzione della probabilità di errore.
3. Grafi e matrici.
Grafi orientati e matrici non negative. Classificazione dei nodi, loro periodo e proprietà relative.
Matrici irriducibili e primitive. Periodo delle matrici primitive. Il teorema di Perron-Frobenius.
Matrici e vettori stocastici.
4. Catene di Markov.
Catene di Markov finite e omogenee. Classificazione degli stati. Classi ricorrenti e transienti. Catene di Markov irriducibili e aperiodiche.
Tempi di prima entrata in uno stato. Distribuzione stazionaria. Catene di Markov ergodiche e proprietà di convergenza alla distribuzione stazionaria.
Catene di Markov reversibili. Passeggiate a caso su grafi. Algoritmo probabilistico per 2-SODD.
5. Applicazioni algoritmiche delle catene di Markov.
Generazione casuale non uniforme e simulazione di catene di Markov.
Metodi Monte Carlo basati su catene di Markov (MCMC). Campionatori di Gibbs. Algoritmo di Metropolis. Generazione casuale di insiemi indipendenti e di colorazioni di un grafo.
Analisi della velocità di convergenza alla distribuzione stazionaria: il caso generale, metodo dell'accoppiamento e l'esempio della generazione casuale di colorazioni di grafi.
Algoritmi di conteggio approssimato mediante catene di Markov: calcolo del numero di colorazioni di un grafo.
Prerequisiti
Nozioni di base di algebra lineare, proprietà delle matrici, elementi di calcolo delle probabilità.
Si consiglia di aver superato almeno gli esami degli insegnamenti di matematica e di calcolo delle probabilità in un corso di laurea triennale di informatica.
Metodi didattici
L'insegnamento è basato su lezioni tradizionali.
Materiale di riferimento
- Pagina web : http://users.mat.unimi.it/users/goldwurm/Metodi_probabilistici/
dove sarà riportato anche il link alla pagina MyAriel del corso per il nuovo anno accademico.
Testo principale:
Massimiliano Goldwurm, Catene di Markov e applicazioni algoritmiche. Milano University Press, Gennaio 2024
(disponibile al sito https://libri.unimi.it/index.php/milanoup/catalog/book/158).
- Dispense disponibili ai siti citati sopra:
· M. Goldwurm, Compendio di calcolo delle probabilità,
dispense ausiliarie dedicate alle nozioni introduttive di probabilità e ad alcuni argomenti avanzati,
Università degli Studi di Milano, anno accademico 2016/2017.
- Altri testi di riferimento:
· B.V. Gnedenko, The theory of Probability, 6th edition, Gordon and Breach Science Publishers, 1997.
· M. Iosifescu, Finite Markov Processes and their Applications, John Wiley & Sons, 1980.
· O. Häggström. Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003.
· E. Seneta, Non-negative Matrices and Markov Chains, Springer-Verlag, 1981.
· W. Woess, Catene di Markov e teoria del potenziale nel discreto, Quaderni dell'U.M.I., Pitagora Editrice, 1996.
· M. Mitzenmacher, E. Upfal, Probability and Computing, Cambridge university Press, 2005.
· J. Hromkovic, Design and Analysis of Randomized Algorithms, Springer, 2005.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste in una prova orale volta ad accertare la conoscenza degli argomenti del programma, la comprensione dei metodi usati nell'analisi dei modelli probabilistici e degli algoritmi presentati a lezione. Si intende anche accertare la capacità di applicare le stesse tecniche a semplici nuovi problemi.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Turni:
Turno
Docente: Goldwurm Massimiliano
Docente/i
Ricevimento:
su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).