Probabilité aléatoire Algorithmes

Question

Je prends un niveau de cours grad algorithmes randomisés à l'automne. Le professeur est connu pour être très orienté et mathématiquement détail rigoureux, donc je serai tenu d'avoir une compréhension approfondie de la probabilité. Quel serait un bon livre de probabilité d'apprendre que serait intuitive, mais aussi une certaine rigueur mathématique pour elle?

Answer 1

Qu'est-ce que les manuels scolaires ne recommande le cours? Je aime « Probabilités et Computing » par Mitzenmacher et Upfal et « algorithmes probabilistes » par Motwani et Raghavan. Ils introduisent la théorie nécessaire du point de vue des algorithmes. Je vous recommande aussi un livre sur les inégalités, comme limitant les choses est tout à fait essentiel à l'analyse des algorithmes probabilistes. À tout le moins cette antisèche .

Answer 2

Vous ne fait pas besoin d'un texte mathématique rigoureux sur la théorie des probabilités. Je doute que le professeur utilisera $ \ sigma $ algèbres et similaires (à moins qu'ils ne mentionneront martingales et préfèrent en discuter en utilisant ces termes, personne ne serait en mesure de suivre). Qu'est-ce que vous avez probablement besoin est comprendre de la théorie des probabilités, que vous ne pouvez obtenir par « jouer » avec, par exemple dans un cours comme ça. Si vous avez aucun arrière-plan, il suffit de prendre un texte d'introduction et de travail à travers quelques-uns des exercices.