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

Bibliografia Di Riferimento

"Percolation", Grimmett, Springer "Probability on Graphs", Grimmett, Cambridge University Press "Random Graphs and Complex Networks", van der Hofstad, Cambridge Series in Statistical and Probabilistic Mathematics "Probability on Trees and Networks", Lyons and Peres, Cambridge University Press "Markov chain mixing times", Levin and Peres, with contributions by Wilmer, American Mathematical Society "Percolation", Bollobas and Riordan, Cambridge University Press

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

Bibliografia Di Riferimento

"Percolation", Grimmett, Springer "Probability on Graphs", Grimmett, Cambridge University Press "Random Graphs and Complex Networks", van der Hofstad, Cambridge Series in Statistical and Probabilistic Mathematics "Probability on Trees and Networks", Lyons and Peres, Cambridge University Press "Markov chain mixing times", Levin and Peres, with contributions by Wilmer, American Mathematical Society "Percolation", Bollobas and Riordan, Cambridge University Press

Modalità Erogazione

Lezioni frontali

Modalità Valutazione

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