Programma

Il oggetivo del corso e' di vedere diversi metodi moderni della teoria della probabilita' e la loro applicazioni per risolvere problemi fondamentali di altre aree, come l'informatica (algoritmi random, random networks), combinatoria e data science. In particolare, vedremo diversi applicazioni dove il problema da essere risolto e' in realta' non-aleatorio, ma si sceglie di usare la probabilita' di maniera opportunistica per risolverlo (per esempio, perche' porta a un algoritmo piu' efficiente, o perche' porta a una soluzione piu' protetta contra il attaco di un avversario, o semplicemente perche' ci porta a una soluzione semplice e matematicamente molto elegante per un problema apparentemente difficile).

Alcuni argomenti visti nel corso sono i seguenti:
* Algoritmi random
* Si puo' usare aleatorieta' perfetta in informatica?
* Processi di allocazione "balls into bins" e struttura dati aleatoria hash
* Processi di ramificazioni e di diffusione di infezioni
* Metodo probabilistico e applicazioni della probabilita' alla combinatoria e teoria dei giocchi
* Concentrazione di variabile aleatoria e Martingale, applicazione al problema di network routing e riduzione della dimensione di dati
* Percolazione, grafi aleatori Erdos-Renyi e random networks
* Passegiata aleatoria su grafi e applicazione al problema di clustering data

Testi Adottati

"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis", Mitzenmacher and Upfal, Cambridge University Press
"The probabilistic method", Alon and Spencer, John Wiley & Sons

Modalità Erogazione

Lezioni frontali

Modalità Valutazione

Fogli di esercizi da risolvere a casa piu un esame orale e/o un seminario.

Programma

Il oggetivo del corso e' di vedere diversi metodi moderni della teoria della probabilita' e la loro applicazioni per risolvere problemi fondamentali di altre aree, come l'informatica (algoritmi random, random networks), combinatoria e data science. In particolare, vedremo diversi applicazioni dove il problema da essere risolto e' in realta' non-aleatorio, ma si sceglie di usare la probabilita' di maniera opportunistica per risolverlo (per esempio, perche' porta a un algoritmo piu' efficiente, o perche' porta a una soluzione piu' protetta contra il attaco di un avversario, o semplicemente perche' ci porta a una soluzione semplice e matematicamente molto elegante per un problema apparentemente difficile).

Alcuni argomenti visti nel corso sono i seguenti:
* Algoritmi random
* Si puo' usare aleatorieta' perfetta in informatica?
* Processi di allocazione "balls into bins" e struttura dati aleatoria hash
* Processi di ramificazioni e di diffusione di infezioni
* Metodo probabilistico e applicazioni della probabilita' alla combinatoria e teoria dei giocchi
* Concentrazione di variabile aleatoria e Martingale, applicazione al problema di network routing e riduzione della dimensione di dati
* Percolazione, grafi aleatori Erdos-Renyi e random networks
* Passegiata aleatoria su grafi e applicazione al problema di clustering data

Testi Adottati

"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis", Mitzenmacher and Upfal, Cambridge University Press
"The probabilistic method", Alon and Spencer, John Wiley & Sons

Modalità Erogazione

Lezioni frontali

Modalità Valutazione

Fogli di esercizi da risolvere a casa piu un esame orale e/o un seminario.