论文标题
关于随机算法的注释
Notes on Randomized Algorithms
论文作者
论文摘要
耶鲁计算机科学课程CPSC 469/569的讲义随机算法。适用于作为随机算法的入门研究生或高级本科课程的补充文本。讨论了概率理论的工具，包括随机变量和期望，联合界定论点，集中界，马尔天群岛和马尔可夫链的应用以及Lovász局部引理。算法主题包括对经典随机算法的分析，例如QuickSort和Hoare的发现，随机树数据结构，哈希，马尔可夫链蒙特卡洛采样，随机近似计数，降低计算，量子计算以及一些随机分布式算法的示例。
Lecture notes for the Yale Computer Science course CPSC 469/569 Randomized Algorithms. Suitable for use as a supplementary text for an introductory graduate or advanced undergraduate course on randomized algorithms. Discusses tools from probability theory, including random variables and expectations, union bound arguments, concentration bounds, applications of martingales and Markov chains, and the Lovász Local Lemma. Algorithmic topics include analysis of classic randomized algorithms such as Quicksort and Hoare's FIND, randomized tree data structures, hashing, Markov chain Monte Carlo sampling, randomized approximate counting, derandomization, quantum computing, and some examples of randomized distributed algorithms.
