Metodi probabilistici per l'informatica
A.A. 2018/2019
Obiettivi formativi
Questo corso è dedicato agli strumenti probabilistici utilizzati nell'informatica e in particolare nell'analisi degli algoritmi randomizzati.
Lo scopo è quello di un corso che svolga la funzione di ponte tra il tradizionale calcolo delle probabilità e le discipline di carattere informatico
Lo scopo è quello di un corso che svolga la funzione di ponte tra il tradizionale calcolo delle probabilità e le discipline di carattere informatico
Risultati apprendimento attesi
Non definiti
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
Programma
1) Richiami di calcolo delle probabilità. Disuguaglianza di Chernoff e sue applicazioni.
2) Algoritmi probabilistici
Classificazione: algoritmi Las Vegas, 1-sided error, a errore limitato e illimitato. Metodi di riduzione della probabilità di errore.
Esempi particolari: protocolli di comunicazione, commutatività di matrici.
3) Catene di Markov
Grafi orientati e matrici associate. Matrici irriducibili e primitive. Il periodo delle matrici irriducibili. Il teorema di Perron-Frobenius. Matrici e vettori stocastici.
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. Esempi di passeggiate a caso su grafi. Algoritmo probabilistico per 2-SODD.
4) Applicazioni algoritmiche delle catene di Markov
Generazione casuale non uniforme. Procedure di simulazione di catene di Markov. Algoritmi Markov Chain Monte Carlo (MCMC).
Campionatori di Gibbs: generazione casuale di insiemi indipendenti e di colorazioni di un grafo. L'algoritmo di Metropolis.
Analisi della velocità di convergenza alla distribuzione stazionaria: il caso generale, il metodo dell'accoppiamento, 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.
5) Introduzione ai processi continui (cenni ai processi di Poisson e ai processi di Markov).
2) Algoritmi probabilistici
Classificazione: algoritmi Las Vegas, 1-sided error, a errore limitato e illimitato. Metodi di riduzione della probabilità di errore.
Esempi particolari: protocolli di comunicazione, commutatività di matrici.
3) Catene di Markov
Grafi orientati e matrici associate. Matrici irriducibili e primitive. Il periodo delle matrici irriducibili. Il teorema di Perron-Frobenius. Matrici e vettori stocastici.
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. Esempi di passeggiate a caso su grafi. Algoritmo probabilistico per 2-SODD.
4) Applicazioni algoritmiche delle catene di Markov
Generazione casuale non uniforme. Procedure di simulazione di catene di Markov. Algoritmi Markov Chain Monte Carlo (MCMC).
Campionatori di Gibbs: generazione casuale di insiemi indipendenti e di colorazioni di un grafo. L'algoritmo di Metropolis.
Analisi della velocità di convergenza alla distribuzione stazionaria: il caso generale, il metodo dell'accoppiamento, 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.
5) Introduzione ai processi continui (cenni ai processi di Poisson e ai processi di Markov).
Informazioni sul programma
L'argomento centrale del corso è costituito dalle catene di Markov finite e omogenee e dalle loro applicazioni algoritmiche per la soluzione di problemi di ottimizzazione e conteggio computazionalmente difficili.
Propedeuticità
Calcolo delle probabilità e statistica (o Statistica e analisi dei dati). Algoritmi e strutture dati
Prerequisiti
Prerequisiti
Nozioni di base di algebra lineare, proprietà delle matrici. Nozioni di base di calcolo delle probabilità.
Modalità di esame: una prova orale volta ad accertare la conoscenza delle nozioni fondamentali sulle catene di Markov e degli aspetti principali delle applicazioni algoritmiche presentate nel corso.
Modalità di frequenza: consigliata.
Nozioni di base di algebra lineare, proprietà delle matrici. Nozioni di base di calcolo delle probabilità.
Modalità di esame: una prova orale volta ad accertare la conoscenza delle nozioni fondamentali sulle catene di Markov e degli aspetti principali delle applicazioni algoritmiche presentate nel corso.
Modalità di frequenza: consigliata.
Materiale di riferimento
· 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.
· Eugene 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.
Dispense (reperibili alla pagina web del corso)
· M. Goldwurm, Introduzione alle catene di Markov finite (dispense sulla prima parte del corso), Rapporto interno n. 321-08, Dip. Scienze dell'Informazione, Università degli Studi di Milano.
· M. Goldwurm, Applicazioni algoritmiche delle catene di Markov, Rapporto interno, Dip. Scienze dell'Informazione, Università degli Studi di Milano.
· O. Häggström. Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003.
· Eugene 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.
Dispense (reperibili alla pagina web del corso)
· M. Goldwurm, Introduzione alle catene di Markov finite (dispense sulla prima parte del corso), Rapporto interno n. 321-08, Dip. Scienze dell'Informazione, Università degli Studi di Milano.
· M. Goldwurm, Applicazioni algoritmiche delle catene di Markov, Rapporto interno, Dip. Scienze dell'Informazione, Università degli Studi di Milano.
Docente/i
Ricevimento:
su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).