Randomized Algorithms Probabilità

Question

mi sto prendendo un livello grad randomizzato algoritmi corso in autunno. Il professore è noto per essere molto particolare orientato e matematicamente rigoroso, così sarò necessario avere una comprensione approfondita della probabilità. Quale sarebbe un libro buona probabilità di imparare da che sarebbe intuitivo, ma anche avere un certo rigore matematico ad esso?

Answer 1

Quali libri di testo fa il corso consiglia? Mi piace "Probabilità e Computing" di Mitzenmacher e Upfal e "Randomized Algorithms" di Motwani e Raghavan. Essi introducono la teoria necessario dal punto di vista algoritmi. Raccomando anche un libro sulle disuguaglianze, come delimitazione cose è abbastanza essenziale per l'analisi degli algoritmi randomizzati. Per lo meno questo Cheat Sheet .

Answer 2

in realtà non ha bisogno di un testo matematicamente rigoroso sulla teoria della probabilità. Dubito che il professore userà $ \ sigma $ -algebre e simili (a meno che non citerò martingale e preferiscono discutere utilizzando questi termini, nessuno sarebbe in grado di seguire). Quello che probabilmente bisogno è un comprensione della teoria della probabilità, che si può ottenere solo da "giocare" con essa, per esempio in un corso del genere. Se non si hanno a tutti, basta prendere un testo introduttivo e di lavoro attraverso alcune delle esercitazioni.