1. Presentazione del corso
2. Avvisi
3. Programma
4. Propedeuticità consigliate
5. Testo di riferimento
6. Altri testi
7. Modalità d'esame
8. Appelli per l'anno accademico corrente
9. Orari di lezione e ricevimento
10. Sito MyAriel del corso
11. Sito Ariel del corso

PRESENTAZIONE DEL CORSO

In questo corso si presentano alcuni metodi e strumenti probabilistici ampiamente utilizzati nell'analisi di algoritmi, nello studio di sistemi di comunicazione e in vari settori di area informatica. Il tema centrale è quello delle catene di Markov e delle loro applicazioni algoritmiche per la soluzione di problemi di ottimizzazione e conteggio computazionalmente difficili. Esempi classici sono quelli dell'annealing simulato e delle procedure per la generazione di clique e di colorazioni di grafi. Ricordiamo che i modelli Markoviani sono utilizzati in molti altri ambiti di ricerca come per esempio nella biologia computazionale, nel riconoscimento di segnali vocali, nell'analisi di procedure di esplorazione della rete web.

AVVISI

• Lezione cancellata
  Si avvisano gli studenti che la lezione del presente corso prevista per giovedì 11 aprile dalle 8:30 alle 10:30 (aula 110 al settore didattico) è cancellata. Il corso riprenderà regolarmente il lunedì successivo.
  

• Sito My Ariel
  È attualmente operativo il sito MyAriel del presente corso all'indirizzo pagina MyAriel, che sostituisce il precedente sito Ariel.
  

• Lezioni
  Il corso si tiene in presenza nel secondo semestre. Non si prevede erogazione delle lezioni per via telematica.
  

• Prove orali
  Le prove orali si svolgono normalmente in presenza su appuntamento.
  Dopo essersi iscritti a un appello, gli studenti interessati sono tenuti a concordare per e-mail con il docente del corso il luogo e la data effettiva di svolgimento della prova.
  Si ricorda che non è possibile sostenere l'orale prima della data ufficiale dell'appello prescelto.
  

• Ricevimento sospeso
  Il ricevimento previsto per martedì 27 febbraio 2024 è annullato.

PROGRAMMA

• 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.
  
• Algoritmi probabilistici
  Classificazione: algoritmi Las Vegas, 1-sided error, a errore limitato e illimitato. Metodi di riduzione della probabilità di errore.
  
• Grafi e matrici
  Grafi orientati e matrici non negative. Classificazione e periodo dei nodi e loro proprietà. Matrici irriducibili e primitive. Il periodo delle matrici irriducibili. Il teorema di Perron-Frobenius. Matrici e vettori stocastici.
• 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.
  
• 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.

PROPEDEUTICITA' CONSIGLIATE

TESTO DI RIFERIMENTO

ALTRI TESTI

• Olle Häggström, Finite Markov Chains and Algorithmic Applications, London Mathematical Society, 2003 (esiste versione disponibile in rete).
• Marius Iosifescu, Finite Markov Processes and their Applications, John Wiley & Sons, 1980.
• Michael Mitzenmacher, Eli Upfal, Probability and Computing, Cambridge University Press, 2005.
• Juraj Hromkovic Design and Analysis of Randomized Algorithms, Springer, 2005.
• Wolfgang Wöss, Catene di Markov e teoria del potenziale nel discreto, Quaderni dell'Unione Matematica Italiana, Pitagora Editrice, 1996.

MODALITÀ D'ESAME

APPELLI D'ESAME

ORARIO DELLE LEZIONI

ORARIO DI RICEVIMENTO