Seguiremo il testo "Probability and computing" di Mitzenmacher e Upfal.
PARTE 1) La prima parte del corso sarà un richiamo degli strumenti di teoria delle probabilità viste nel corso di laurea triennale (corrispondenti grossomodo ai primi tre capitoli del libro).
PARTE 2) Seguiranno poi argomenti più avanzati, motivati da applicazioni informatiche. A seconda del tempo a disposizione tratteremo una parte dei seguenti argomenti: disuguaglianze di concentrazione (capitolo 4), urne e grafi aleatori (capitolo 5), catene di Markov e passeggiate aleatorie (capitolo 7), tempo di mixing (non sul libro), teoria dell'informazione (capitolo 10), metodo Montecarlo (capitolo 11), martingale (capitolo 13), funzioni Hash (capitolo 15). |