Logica e Metodi Probabilistici per l'Informatica

Laurea del Primo Livello in Ingegneria Informatica ed Automatica 

Anno Accademico 2023/2024 - II Semestre

Proff. Maurizio Lenzerini e Stefano Leonardi 

Pagina web principale del corso 

Sezione II, Metodi Probabilistici per l'informatica

A partire dal 3 Aprile!

Aula 108 Marco Polo 

Lunedì ore 08:00 - 10:00

Mercoledì ore 08:00 - 10:00 

Classroom code: 5sd2cfm

Sezione 1: Logica ed Informatica 

Docente: Prof. Maurizio Lenzerini - lenzerini@diag.uniroma1.it

Pagina web della Sezione 1 

Venerdì ore 08:00 - 10:00 

Sezione 2: Metodi Probabilistici per l'Informatica 

A partire dal 3 Aprile!

Docente: Prof. Stefano Leonardi - leonardi@diag.uniroma1.it

Tutor: Dr. Federico Fusco - fuscof@diag.uniorma1.it 

Lunedì, ore 08:00 - 10:00 

Mercoledì ore 08:00 - 10:00 

La seconda parte del corso di Metodi Quantitativi per l'Informatica intende illustrare alcune aspetti fondamentali dei metodi probabilistici in Informatica e alcune loro applicazioni a problemi numerici e combinatorici, all’apprendimento automatico, e all’analisi dei dati e delle reti ad ampia scala. Il corso si articola in tre sezioni:

1. Algoritmi e probabilità Riferimento [1], Capp. 1, 2 (tutti)

• Probabilità, Eventi, e Variabili Aleatorie

• Le distribuzioni binomiale e geometrica 

• Analisi di algoritmi probabilistici: 

• Algoritmi con e senza memoria

•  The coupon collector problem 

•  Selezione del k elemento minimo 

•   Quicksort randomizzato 

•  L'algoritmo di min-cut

2. Metodi di campionamento e allocazione probabilistica. Riferimento [1], Cap 3 tutto, Cap. 4.1-4.2 10.1-10.2  5.1-5.2

• Momenti e Deviazione 

• Le funzioni generatrici ed i Chernoff-Hoeffding bounds 

• Il metodo Monte Carlo 

• Metodi di campionamento imparziali 

• Balls in Bins 

• Counting triangles 

3. Processi stocastici ed applicazioni Riferimento [1] Cap. 7.1-7.4

• Le catene di Markov e le proprietà di convergenza 

• Random walks e l'algoritmo di Pagerank 

• Random walks for 2-SAT 

• Random Walks in undirected graphs

Il materiale didattico e gli esercizi sono disponibili sul sito Piazza del corso. 

Riferimenti: 

[1]  Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitznmacher, E. Upfal, Cambridge University Press, 

[2]  Algorithms,  S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Mc. Graw Hill.