AN INTRODUCTION TO RANDOMIZED ALGORITHMS
AN INTRODUCTION TO RANDOMIZED ALGORITHMS
复制标题
DOI：
10.1016/0166-218x(91)90086-c
复制
发表时间：
1991-11-21
影响因子：
1.1
通讯作者：
KARP, RM
中科院分区：
文献类型：
--
作者：
KARP, RM
过去15年的研究已经充分证明了算法在执行过程中随机选择的优势。本文提出了各种各样的例子，旨在说明随机算法的应用范围，以及在其构造中最常用的一般原则和方法。这些例子来自许多领域，包括数论、代数、图论、模式匹配、选择、排序、搜索、计算几何、组合枚举以及并行和分布式计算。
Research conducted over the past fifteen years has amply demonstrated the advantages of algorithms that make random choices in the course of their execution. This paper presents a wide variety of examples intended to illustrate the range of applications of randomized algorithms, and the general principles and approaches that are of greatest use in their construction. The examples are drawn from many areas, including number theory, algebra, graph theory, pattern matching, selection, sorting, searching, computational geometry, combinatorial enumeration, and parallel and distributed computation.