CP450 -
Probabilità Discreta
II semestre, 2019-20
Informazione sul corso
Docente:
Alexandre Stauffer
email: astauffer mat uniroma3 it
Ufficio: Dip. Matematica, Stanza 110.
Ricevimento: in aula subito dopo le lezione o su appuntamento (via email).
Lezioni:
Lunedi 9-12 (Aula 211), Venerdi 11-13 (Aula 211)
Testi di riferimento:
[MU] Probability and Computing: randomized algorithms and probabilistic analysis; Mitzenmacher and Upfal.
[LPW] Markov chain mixing times; Levin, Peres and Wilmer. 2nd edition.
[G] Percolation; Grimmett. 2nd edition.
[AS] The probabilistic method; Alon and Spencer. 3rd edition
Ultimi aggiornamenti
12/03: Gli informazioni sul corso saranno da adesso disponibili sono sul Moodle.
05/03: Cancellamento delle lezioni del 6, 9 e 13 marzo. Gli studenti saranno contattati per email per il proseguimento del corso.
02/03: Cambio orario delle lezioni di venerdi.
17/02: Cambio aula (adesso tutte le lezione sarano nella 211).
Diario delle lezioni
- Lezione 1 (24 febbraio). Introduzione agli algoritmi aleatori. Macchina di Turing con stream di bits aleatori.
Algoritmo aleatorio di Las Vegas e Monte Carlo. Ridurre la probabilità del errore del output
tramite ripetizioni. Esempi di algoritmi aleatori: controllo di moltiplicazione di matrici e identità di due polinomi.
- Lezione 2 (28 febbraio). Algoritmo aleatorio per Min-Cut [MU 1.5], introduzione al metodo probabilistico [MU 6.1, 6.2] e applicazione al
numero di Ramsey e Max-cut.
- Lezione 3 (2 marzo). Metodo probabilistico con alterazioni. Esempi per independent sets, geometria (massimizzazione dell'area del triangolo più piccolo)
e teoria dei giocchi [AS 3.2, 3.3; MU 6.4]