Metodi probabilistici per l'informatica

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.