二十世纪最伟大的十大算法

在此列举一下在 20 世纪对科学和工程领域的发展产生最大影响力的十大算法。

算法们

  1. 蒙特卡洛方法
    • 时间: 1946
    • 论文: John von Neumann, Stan Ulam, and Nick Metropolis, all at the Los Alamos Scientific Laboratory, cook up the Metropolis algorithm, also known as the Monte Carlo method
    • 说人话: Wikipedia
  2. 单纯形法
    • 时间: 1947
    • 论文: George Dantzig, at the RAND Corporation, creates the simplex method for linear programming
    • 说人话: Wikipedia
  3. Krylov 子空间迭代法
    • 时间: 1950
    • 论文: Magnus Hestenes, Eduard Stiefel, and Cornelius Lanczos, all from the Institute for Numerical Analysis at the National Bureau of Standards, initiate the development of Krylov subspace iteration methods
    • 说人话: Wikipedia
  4. 矩阵计算的分解方法
    • 时间: 1951
    • 论文: Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach
      to matrix computations
  5. 优化的 Fortran 编译器
    • 时间: 1957
    • 论文: John Backus leads a team at IBM in developing the Fortran optimizing compiler
    • 说人话: Wikipedia
  6. 计算矩阵特征值的 QR 算法
    • 时间: 1959-1961
    • 论文: J.G.F. Francis of Ferranti Ltd., London, finds a stable method for computing eigenvalues, known as the QR algorithm
    • 说人话: Wikipedia
  7. 快速排序算法
    • 时间: 1962
    • 论文: Tony Hoare of Elliott Brothers, Ltd., London, presents Quicksort
    • 说人话: Wikipedia
  8. 快速傅立叶变换
    • 时间: 1965
    • 论文: James Cooley of the IBM T.J. Watson Research Center and John Tukey of Princeton
      University and AT&T Bell Laboratories unveil the fast Fourier transform
    • 说人话: Wikipedia
  9. 整数关系检测算法
    • 时间: 1977
    • 论文: Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer relation detection algorithm
    • 说人话: Wikipedia
  10. 快速多极算法
    • 时间: 1987
    • 论文: Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole algorithm
    • 说人话: Wikipedia

唠叨

“一百年,就留下了这 10 个影响深远的算法”。不过各行各业应该都有自己的 “20 世纪最伟大的算法” 吧。并且每个人对 “影响深远” 的看法也不同。我就奇怪为什么 Dijkstra 没有上榜,难道是因为太难读了?

上面的算法大多数都是各种数学数学数学…… 哭…… 在计算机中比较常见的好像有子空间迭代(用于矩阵计算)、快速排序(飞入寻常百姓家)、快速傅立叶变换(非常常用但是看不懂)。至于自己实现一下算法么…… 我选择快排!快排!快排!

参考文献