Logica e Metodi Probabilistici per l'Informatica

Laurea del Primo Livello in Scienze Matematiche per l'intelligenza Artificiale 

Anno Accademico 2024/2025 - II Semestre

Proff. Lorenzo Marconi e  Stefano Leonardi 

Sezione 1: Logica ed Informatica 

Docente: Prof. Lorenzo Marconi - marconi@diag.uniroma1.it

Classroom della prima parte del corso

Sezione 2: Metodi Probabilistici per l'Informatica 

A partire dal 10 Aprile!

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

Tutor: Simone Di Gregorio - simone.digregorio@uniroma1.it

Aula Picone  

Martedi' ore 15:00 -17:00

Giovedi' ore 13:00 - 15:00 

Classroom code: 5sd2cfm

La seconda parte del corso 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 

• VC dimension

• Random projections

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.