Probability and Computing
Formulario della materia 75 definizioni e teoremi in una pagina
Argomenti
IProbabilità discreta e algoritmi randomizzati
- Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione
- Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici
- Taglio minimo randomizzato - algoritmo di Karger
Esercizi svolti
- Esercizio - Accoppiamento perfetto con la matrice di Edmonds e Schwartz-Zippel
- Esercizio - Algoritmo di Freivalds su matrici 3x3 con elementi sbagliati
- Esercizio - Contrazione di Karger a mano su un grafo con cinque vertici
- Esercizio - Da Las Vegas a Monte Carlo con Markov e da Monte Carlo a Las Vegas
- Esercizio - Dimostrazione che ZPP è uguale a RP intersecato co-RP
- Esercizio - Due scatole di caramelle e soglia casuale contro ogni input (lezioni MIT)
- Esercizio - Impronta di stringhe con un primo casuale e comunicazione
- Esercizio - Moneta a due teste e regola di Bayes per le risposte di un test randomizzato (lezioni MIT)
- Esercizio - Numero di ripetizioni di Karger per un errore prefissato
- Esercizio - Numero di tagli minimi di un grafo, dimostrazione e casi estremi
- Esercizio - Probabilità esatte di Karger sul ciclo e sul grafo completo
- Esercizio - Ripetizioni di un Monte Carlo a errore unilaterale per un errore prefissato
- Esercizio - Schwartz-Zippel su identità vere e false modulo 101
- Esercizio - Test di Miller-Rabin su 221 e 561 e confronto con il test di Fermat
- Esercizio - Union bound e inclusione-esclusione, due dadi e collisioni di una funzione hash
- Esercizio - Voto di maggioranza per un algoritmo a errore bilaterale
IIVariabili aleatorie e valore atteso
- Linearità del valore atteso e variabili indicatrici
- Analisi probabilistica di quicksort e quickselect
Esercizi svolti
- Esercizio - aggiornamenti del massimo corrente in una scansione (record)
- Esercizio - album di 20 figurine, acquisti attesi per completarlo
- Esercizio - cappotti restituiti a caso e punti fissi di una permutazione
- Esercizio - confronti attesi di quicksort su 5 elementi, tre metodi
- Esercizio - Dado lanciato fino al primo sei con tutti i lanci pari (lezioni MIT)
- Esercizio - distribuzione esatta dei confronti di quicksort su 6 elementi e caso pessimo
- Esercizio - identità di Wald, somma dei lanci di un dado fino al primo sei
- Esercizio - inversioni di una permutazione casuale e confronti dell'insertion sort
- Esercizio - massimo e minimo di due dadi, linearità senza indipendenza
- Esercizio - quali coppie vengono confrontate, confronti del minimo e della mediana in quicksort
- Esercizio - quickselect, confronti attesi per il minimo, la mediana e il massimo
- Esercizio - ricorrenza di quicksort, forma chiusa e confronto con n log n
- Esercizio - tempo atteso per vedere HH, HT e HHH nei lanci di una moneta
- Esercizio - triangoli, vertici isolati e cricche in un grafo casuale
IIIMomenti e concentrazione
Esercizi svolti
- Esercizio - 1023 bit indipendenti a coppie da dieci bit casuali
- Esercizio - amplificazione di un algoritmo BPP con il voto di maggioranza
- Esercizio - bilanciamento di insiemi con un colore casuale
- Esercizio - Chebyshev non si può migliorare e le due forme del secondo momento
- Esercizio - Chebyshev sul collezionista, 50 tipi di figurine
- Esercizio - Chernoff e i mutui del 2008, perché serve l'indipendenza (lezioni MIT)
- Esercizio - Chernoff su una binomiale, code superiore e inferiore
- Esercizio - Concentrazione del numero cromatico di un grafo casuale con le differenze limitate (lezioni MIT)
- Esercizio - coppie di compleanni uguali e indipendenza a coppie
- Esercizio - esistenza di triangoli con il secondo momento in G(n,p)
- Esercizio - Hoeffding per una somma di variabili con ampiezze diverse
- Esercizio - Markov traslato e ribaltato sui punteggi di un esame (lezioni MIT)
- Esercizio - mediana randomizzata, parametri e probabilità di fallimento
- Esercizio - mille lanci di moneta, cinque limiti per la coda
- Esercizio - quanti campioni per stimare una probabilità con una data confidenza
- Esercizio - urne vuote e disuguaglianza delle differenze limitate
- Esercizio - varianza dei punti fissi di una permutazione e Chebyshev
IVPalline e urne e hashing
- Palline e urne - compleanno, carico massimo e approssimazione di Poisson
- Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint
- Algoritmi di streaming - campionamento di riserva e conteggio degli elementi distinti
Esercizi svolti
- Esercizio - Approssimazione di Poisson dei carichi e limite sul carico massimo
- Esercizio - Campionamento di riserva su un flusso di cinque elementi
- Esercizio - Contatore di Morris - distribuzione esatta, varianza e numero di contatori
- Esercizio - Count-Min sketch - tabella a mano e dimensionamento
- Esercizio - Dimensionamento di un filtro di Bloom e fingerprint di documenti
- Esercizio - Famiglia universale mod p mod m - verifica esaustiva e controesempio
- Esercizio - Hashing perfetto a due livelli su otto chiavi
- Esercizio - Liste di collisione con hash universale e dimensionamento della tabella
- Esercizio - Paradosso del compleanno e collisioni di un hash a 32 bit
- Esercizio - Stima degli elementi distinti con il k-esimo minimo
- Esercizio - Tre persone con lo stesso compleanno e due scelte nel bilanciamento
- Esercizio - Urne vuote e carico massimo con mille server
VMetodo probabilistico
Esercizi svolti
- Esercizio - Cammini hamiltoniani in un torneo casuale (lezioni MIT)
- Esercizio - Insiemi indipendenti con alterazione e lemma locale di Lovász per k-SAT
- Esercizio - Limiti inferiori dei numeri di Ramsey con il metodo probabilistico
- Esercizio - MAX-SAT con clausole miste e aspettative condizionate
- Esercizio - Taglio grande e derandomizzazione sul grafo di Petersen
- Esercizio - Teorema di Turán dal limite di Caro-Wei (lezioni MIT)
VICatene di Markov e passeggiate aleatorie
- Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionaria
- Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi
Esercizi svolti
- Esercizio - Algoritmo randomizzato per 2-SAT eseguito su un'istanza con quattro variabili
- Esercizio - Catena di Markov a tre stati, potenze di P e distribuzione stazionaria
- Esercizio - Classificazione degli stati e probabilità di assorbimento in una catena a sei stati
- Esercizio - Dimostrazioni sulle catene di Markov - potenze, aperiodicità e matrici doppiamente stocastiche
- Esercizio - Modello di Ehrenfest con quattro palline e bilancio dettagliato
- Esercizio - PageRank di quattro pagine con teletrasporto e iterazione di potenza
- Esercizio - Passeggiata aleatoria su un grafo con triangolo e coda - stazionaria, raggiungimento e copertura
- Esercizio - Rovina del giocatore alla roulette - probabilità di vittoria e durata attesa
VIIProcessi continui e metodi Monte Carlo
- Distribuzione esponenziale e processo di Poisson per l'informatica
- Metodi Monte Carlo - stima, generazione di variabili aleatorie e MCMC
Esercizi svolti
- Esercizio - Conteggio delle soluzioni di una formula DNF con l'algoritmo di Karp e Luby
- Esercizio - Dimostrazioni su esponenziale, Erlang e processo di Poisson (domande da orale)
- Esercizio - Gara fra server con tempi di servizio esponenziali - minimo, massimo e richieste replicate
- Esercizio - Generazione di variabili aleatorie con trasformazione inversa e accettazione-rifiuto
- Esercizio - Metropolis-Hastings su tre stati con proposta asimmetrica
- Esercizio - Poissonizzazione di cento palline in cento urne e confronto con il modello esatto
- Esercizio - Router con due sorgenti Poisson - sovrapposizione, filtraggio e tempo del quinto pacchetto
- Esercizio - Stima Monte Carlo di pi greco e di una probabilità rara con campionamento per importanza