Metodi probabilistici per l'informatica

A.A. 2021/2022
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.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre
In relazione alle modalità di erogazione delle attività formative per l'anno 2021/22, verranno date informazioni più specifiche nei prossimi mesi, in base all'evoluzione della situazione sanitaria.
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à.
E' vivamente consigliato 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/
- Dispense:
· M. Goldwurm, Catene di Markov e applicazioni algoritmiche,
Laurea Magistrale di Informatica, Università degli Studi di Milano, maggio 2018.
· 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.
- 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.

Sito Ariel dell'insegnamento disponibile all'indirizzo:
https://mgoldwurmmpi.ariel.ctu.unimi.it/v5/Home/
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 nel corso. Si intende anche accertare la capacità di applicare le stesse tecniche a semplici nuovi problemi.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Siti didattici
Docente/i
Ricevimento:
martedì dalle 9:30 alle 11:30, oppure su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).