Algorithm from THE BOOK

Proofs from THE BOOK是一本收集了很多精妙数学证明的书。


在cstheory.stackexchange.com上有人召集大家讨论假如上帝有一本收集精妙算法的书,那么,那本书应该包含一些什么算法呢?


Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.

If God had a similar book for algorithms, what algorithm(s) do you think would be a candidate(s)?

If possible, please also supply a clickable reference and the key insight(s) which make it work.


原链接:http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book?page=1&tab=votes#tab-top



根据大家投票,Algorithm from THE BOOK Top 候选:


1. 并查集. 维护等价关系的更新和查询的数据结构(103)

     http://en.wikipedia.org/wiki/Disjoint-set_data_structure


2. KMP字符串匹配算法 (99)

     http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm


3. BFPRT算法. 寻找第k大元素的线性算法 (81)

    名字来源于发明算法的五位大牛: Blum,Floyd,Pratt,Rivest,Tarjan

     http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

     http://en.wikipedia.org/wiki/Median_of_medians


4. 二分查找算法(75)

     http://en.wikipedia.org/wiki/Binary_search_algorithm


5. Floyd-Warshall算法 (70)

   O(N^3) 计算给定加权图任意两点间最短路径长度

    给定加权图的边上权重可正可负, 只要不包含负权圈即可。(如果存在负权圈, 圈内任意两点间最短路的长度为-inf)

     http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm


6. 欧几里德算法(65)

   快速计算最大公约数算法

     http://en.wikipedia.org/wiki/Euclidean_algorithm


7. 快速排序算法 (61)

     http://en.wikipedia.org/wiki/Quicksort


8. 霍夫曼编码. 用于数据压缩(48)

     http://en.wikipedia.org/wiki/Huffman_coding


9. Schwartz-Zippel lemma - 多项式快速等价判定 (45)

     http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma


10. 素性判断算法 (44)

     Miller-Rabin算法: http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

     AKS算法: http://en.wikipedia.org/wiki/AKS_primality_test (确定性的多项式时间素性判断算法)


11. Depth First Search (深度优先搜索) (39)

     http://en.wikipedia.org/wiki/Depth-first_search


12. Eratosthenes筛法(37)

     http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


13. Horner's Algorithm/秦九韶算法 (37)

     http://en.wikipedia.org/wiki/Horner_scheme


14. Dijkstra's algorithm - 单源最短路问题 (37)

      http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm


15. 快速傅立叶变换 (36)

     http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

     http://en.wikipedia.org/wiki/Butterfly_diagram


16. Fully Homomorphic Encryption Scheme (全同态加密方案) (35)

     同态是一个数学概念,如 H(f(a, b)) = F(H(a), H(b)), H(.)是一个同态映射

     假设加密操作为E(.), 明文为m, 密文为e, 如果针对明文的操作f,可以根据E构造出F,使得 E(f(m)) = F(e). 那么E就是一个针对f的同态加密算法。 如果f可以支持加法和乘法, 那么E就是全同态加密算法

     同态加密有非常明显的使用场景: 允许第三方在密文e的基础上进行F操作。 我们拿到处理完的结果F(e)后进行解密可以得到我们期望的结果f(m), 而第三方在整个过程中都不了解明文m。


     Craig Gentry在2009年提出的全同态加密方案论文: A Fully Homomorphic Encryption Scheme  http://crypto.stanford.edu/craig/craig-thesis.pdf

     2009年底针对计算效率优化后的简化版本 BGV System: Fully Homomorphic Encryption over the integers http://eprint.iacr.org/2009/616.pdf

     http://portal.acm.org/citation.cfm?id=1666420.1666445

     整数上全同态加密方案分析(1)--献给全同态加密的初学者 http://blog.sciencenet.cn/blog-411071-617182.html

     整数上全同态加密方案分析(2)--献给全同态加密的初学者 http://blog.sciencenet.cn/blog-411071-617185.html

     整数上全同态加密方案分析(3)--献给全同态加密的初学者 http://blog.sciencenet.cn/blog-411071-617188.html

     开源 HELib: https://github.com/shaih/HElib


17. Strassen algorithm 矩阵乘法算法(35)

     http://en.wikipedia.org/wiki/Strassen_algorithm


18. 后缀数组的线性构造算法(31)

     http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf


19. 2-approximation for MAX-CUT(27)

     对于最大化问题,2-approximation max-cut算法是一个简单的随机算法,能得到超过最优解1/2的近似解。

     http://en.wikipedia.org/wiki/Maximum_cut

     回复中,提到一篇提出最大化次模函数的常数近似比算法的论文

     http://theory.stanford.edu/~jvondrak/data/submod-max-SICOMP.pdf


20. Reservoir sampling (蓄水池采样)(27)

     http://en.wikipedia.org/wiki/Reservoir_sampling#cite_note-1


21. 稳定婚姻问题算法(27)

     http://en.wikipedia.org/wiki/Stable_marriage_problem


22. 高斯消元法(26)

     http://en.wikipedia.org/wiki/Gaussian_elimination


23. Christofides's algorithm - 3/2 approximation for metric TSP(25)

     http://en.wikipedia.org/wiki/Christofides_algorithm

     http://en.wikipedia.org/wiki/Traveling_salesman_problem#Metric_TSP


24. Grover量子搜索算法(25)

     一个需要O(log N)空间和O(sqrt(N))时间对N个无序元素进行排序的概率算法。

     http://en.wikipedia.org/wiki/Grover%27s_algorithm


25. Tortoise and hard algorithm - 圈检测(24)

     http://en.wikipedia.org/wiki/Cycle_detection


26. 线性规划算法:单纯形法,  椭球法, 内点算法(24)

     http://en.wikipedia.org/wiki/Linear_programming#Algorithms


27. Robin Moser algorithm - 解决特定类型SAT问题(21)

     http://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma

     http://arxiv.org/abs/0903.0544


28. 归并排序(21)

     http://en.wikipedia.org/wiki/Merge_sort


29. Knuth's Algorithm X(20)

     http://en.wikipedia.org/wiki/Knuth's_Algorithm_X

     Dancing Links: http://arxiv.org/abs/cs/0011047


30. Marcus Hutter's "The Fastest and Shortest Algorithm for All Well-Defined Problems"(19)

     http://www.hutter1.net/ai/pfastprg.pdf

     http://arxiv.org/ps/cs/0102018


31. Schieber-Vishkin算法 - 最小公共祖先(19)

     http://en.wikipedia.org/wiki/Lowest_common_ancestor


32. Expander codes (膨胀码)(17)

     Tanner (1981) http://www.ldpc-codes.com/papers/rlcc.pdf

     Sipser and Spielman(1994) http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=365734

     "Linear-time encodable and decodable error-correcting codes" Spielman (1995) http://dl.acm.org/citation.cfm?doid=225058.225165

     "Randomness conductors and constant-degree lossless expanders" (2002) http://dl.acm.org/citation.cfm?doid=509907.510003


33. Timothy Chan's O(N*logN)平面凸包算法(16)

     http://www.cs.uwaterloo.ca/~tmchan/conv23d.ps.gz


34. Universal Hash/Pairwise indepent hash functions(14)

     http://en.wikipedia.org/wiki/Universal_hashing

     "Universal Classes of Hash Functions" http://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/universalclasses.pdf

     "Introduction to pairwise independent hashing" http://www.wisdom.weizmann.ac.il/~oded/CC/X/hash.pdf


35. 平面图最近点问题线性算法(14)

     “Geometric Approximation Algorithms” http://sarielhp.org/teach/notes/aprx/lec/01_min_disk.pdf


36. Edge-flipping Algorithm - 构造2D Delaunay Triangulation(12)

     http://en.wikipedia.org/wiki/Delaunay_triangulation#Flip_algorithms


37. Linear Majority Voting Algorithm(12)

     MJRTY - A Fast Majority Vote Algorithm, with R.S. Boyer. In R.S. Boyer (ed.)


38. Berlekamp-Massey's algorithm - 构造最短线性反馈移动寄存器(11)

      http://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm


39.  Goemans-williamson algorithm - 最大割近似算法(11)

     http://en.wikipedia.org/wiki/Semidefinite_programming#Example_3_.28Goemans-Williamson_MAX_CUT_approximation_algorithm.29     


40. Binary Decision Diagrams(10)

     http://en.wikipedia.org/wiki/Binary_decision_diagram

     http://www.cs.unb.ca/~gdueck/courses/cs4835/bdd97.pdf

     Knuth TAOCP Vol4, Fas 1, Page 202-280


41. Ford-Fulkerson Algirithm - 最大流算法(9)

     http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm


42. Euclidean TSP近似算法(9)

     "Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems" Sanjeev Arora 


43. Random Projection - 降维(9)

     “Random projection in Dim reduction: applications to image and text data”: http://users.ics.aalto.fi/ella/publications/randproj_kdd.pdf

     http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma


44. Kosaraju's Algorithm - 寻找有向图强连通分支(8)

     http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm


45. LLL Algorithm (Lenstra-Lenstra-Lovász) Lattice Basis Reduction(8)

     http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm


46. Steepest descent 最速下降法(7)

     http://en.wikipedia.org/wiki/Method_of_steepest_descent

     http://mathworld.wolfram.com/MethodofSteepestDescent.html

     http://sces.phys.utk.edu/~moreo/mm08/XuWangP571.pdf


47. Persistant data structure (持久化数据结构)(7)

     这里的持久化,表示数据结构的更新历史被保存下来;而不同于一般软件开发中的持久化。

     http://en.wikipedia.org/wiki/Persistent_data_structure

     Persistant Array: “Fully Persistent Arrays for Efficient Incremental Updates and Voluminous Reads (1992)"


48. Hash Consing(7)

     http://en.wikipedia.org/wiki/Hash_consing


49. 最大子序列和的线性算法(7)

     http://www.cs.bell-labs.com/cm/cs/pearls/maxsum.c


50. Schöning's random-walk algorithm for 3-SAT(7)

     http://theory.stanford.edu/~trevisan/cs174/notes/note9.ps


51. Viterbi Algorithm(7)

     http://en.wikipedia.org/wiki/Viterbi_algorithm


52. Low-density parity-check codes(7)

     http://en.wikipedia.org/wiki/Ldpc


53. Turbo codes(7)

     http://en.wikipedia.org/wiki/Turbo_code


54. Reed-Solomon Coding(7)

     http://en.wikipedia.org/wiki/Reed_Solomon


55. Knuth-Bendix Algorithm(6)

     http://en.wikipedia.org/wiki/Knuth%E2%80%93Bendix_completion_algorithm


56. Buckberger's Algorithm(6)

     http://en.wikipedia.org/wiki/Buchberger%27s_algorithm


57. 全组合/全排列生成算法(6)

     http://en.wikipedia.org/wiki/Combination

     http://en.wikipedia.org/wiki/Permutation


58. Fixed Parameterized Algorithm for Vertex Cover(6)

     http://www.sciencedirect.com/science/article/pii/S0020019097002135


59. Rabin-Karp 字符串匹配算法(6)

     http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm


60. Risch Algorithm(6)

     http://en.wikipedia.org/wiki/Risch_algorithm


61. Boyer-Moore 字符串匹配算法(6)

     http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

     Boyer-Moorse in grep: http://ridiculousfish.com/blog/posts/old-age-and-treachery.html


62. 2-approximation algorithm for Knapsack(6)

     http://en.wikipedia.org/wiki/Knapsack_problem

     http://www.cs.sunysb.edu/~keriko/approx.pdf


63. LR parsers(5)

     http://en.wikipedia.org/wiki/LR_parser


64. Immerman's Algorithm for non-reachability in directed graph in non-deterministic log space(5)

     http://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem


65. Bucket Sort(5)

     http://en.wikipedia.org/wiki/Bucket_sort


66. 实数集不可数的对角证明(5)

     http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument


67. Knuth-Fisher-Yates Suffles(5)

     http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

     Knuth Suffle和蓄水池采样之间的联系: http://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to_Fisher-Yates_shuffle


68. Shor's quantum factoring algorithm(5)

     http://en.wikipedia.org/wiki/Shor's_algorithm

     http://arxiv.org/abs/quant-ph/0010034


69. Ramsey-based complementation construction for Buechi Automata(3)

     http://www.cs.rice.edu/~vardi/papers/icalp85rj.pdf


70. Bitap Algorithm (Shift-Or, Shift-And) 字符串匹配(3)

     http://en.wikipedia.org/wiki/Bitap_algorithm


71. Bellman-Ford Algorithm - 单源最短路算法(3)

     http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm


72. 快速平方根求解(3)

     http://en.wikipedia.org/wiki/Fast_inverse_square_root


73. Savitch's Algorithm - simple recursive algorithm for the reachability problem(3)

     http://en.wikipedia.org/wiki/Savitch%27s_theorem


74. Linear Feedback Shift Registers 线性反馈移位寄存器(2)

     http://en.wikipedia.org/wiki/LFSR


75. Kalman Filter(2)

     http://en.wikipedia.org/wiki/Kalman_filter


76. In place 2-way shuffle(2)

     http://arxiv.org/abs/0805.1598


77. Thompson NFA构造算法(2)

     http://en.wikipedia.org/wiki/Thompson's_construction_algorithm

     http://swtch.com/~rsc/regexp/regexp1.html


78. "The power of random two choices" Paradiam(2)

     http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf


79. Michael Shamos O(n*logn)平面最近点对算法(2)

    https://en.wikipedia.org/wiki/Closest_pair_of_points_problem


80. Hensel Lifting(1)

     http://www.cse.iitk.ac.in/users/manindra/CS681/2005/Lecture17.pdf


81. 布隆过滤器(1)

    https://en.wikipedia.org/wiki/Bloom_filter


82. 基于pascal三角的组合数(a choose b)计算(0)

     http://en.wikipedia.org/wiki/Longest_increasing_subsequence


83. CORDIC(Coordinate Rotation Digital Computer) 算法 - 坐标旋转数字计算方法(0)

     http://en.wikipedia.org/wiki/CORDIC


84. Ancient Egyptian Multiplication(0)

     http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication


85. Tarjan's parallel biconnectivity algorithm(0)

     http://www.umiacs.umd.edu/users/vishkin/TEACHING/ENEE759KS12/TV85.pdf


86. 平面最大割问题的多项式算法(0)
    http://web.eecs.umich.edu/~pettie/matching/Hadlock-maxcut-planar-graph-reduction-to-T-join.pdf


87. 最长递增子序列算法(0)

     http://en.wikipedia.org/wiki/Longest_increasing_subsequence


88. 线性扫描(0)

     http://en.wikipedia.org/wiki/Linear_search


更多内容

  • 一封来自Alice的回信

  • 一封来自Bob的密信

  • 图像风格化技术(1)

  • 也谈深度残差网络

  • 谈谈分类器的损失函数(2)


欢迎关注公众号: 竹目草集

本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院