大话“20 世纪10大算法”

大话“20 世纪10大算法”

1946 蒙特卡洛方法
在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，呃，能帮我算算这个不规则图形的面积么？蒙特卡洛(Monte Carlo)方法便是解决这个问题的巧妙方法:随机向该正方形内扔N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个:那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确.

1947 单纯形法
单纯形法是由大名鼎鼎的“预测未来”的兰德公司的Grorge Dantzig发明的，它成为线性规划学科的重要基石。所谓线性规划，简单的说，就是给定一组线性（所有变量都是一次幂）约束条件（例如a1*x1+ b1*x2+c1*x3>0)，求一个给定的目标函数的极值

1950 Krylov 子空间迭代法
50年代初的这两个算法都是关于线性代数中的矩阵计算的。Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而K r y l o v 方法则巧妙地将其变为Kxi+1=Kxi+b-Axi的迭代形式来求解。它将复杂问题化简为阶段性的易于计算的子步骤。

1951 矩阵计算的分解方法
1951年由橡树岭国家实验室的AlstonHouseholder 提出的矩阵计算的分解方法，则证明了任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵，该算法的意义使得开发灵活的矩阵计算软件包成为可能。

1957 优化的Fortran 编译器
Fortran是第一种能将数学公式转化为计算机程序的高级语言，它的诞生使得科学家们真正开始利用计算机作为计算工具为他们的研究服务，这是计算机应用技术的一个里程碑级别的贡献。

1959-61 计算矩阵特征值的QR算法
呼，又是一个和线性代数有关的算法，计算特征值是矩阵计算的最核心内容之一，传统的求解方案涉及到高次方程求根，当问题规模大的时候十分困难。QR算法把矩阵分解成一个正交矩阵和前面提到的 Krylov 方法类似，这又是一个迭代算法，它把复杂的高次方程求根问题化简为阶段性的易于计算的子步骤，使得用计算机求解大规模矩阵特征值成为可能。这个算法的作者是来自英国伦敦的J.G.F. Francis。

1962 快速排序算法
不论是ANSI C,C++ STL,还是Java SDK,天下几乎所有的SDK里都能找到它的某种实现版本。
快速排序算法最早由Tony Hoare爵士设计，它的基本思想是将待排序列分为两半，左边的一半总是“小的”，右边的一半总是“大的”，这一过程不断递归持续下去，直到整个序列有序。
快速排序的平均时间复杂度仅仅为O(Nlog(N))，相比于普通选择排序和冒泡排序等而言，实在是历史性的创举。

1965 快速傅立叶变换
如果要评选对我们的日常生活影响最大的算法，快速傅立叶变换算法应该是当仁不让的总冠军.哪里有数字信号处理，哪里就有快速傅立叶变换。快速傅立叶算法是离散傅立叶算法（这可是数字信号处理的基石）的一种快速算法，它有 IBM 华生研究院的James Cooley和普林斯顿大学的John Tukey共同提出，其时间复杂度仅为O(Nlog(N))；比时间效率更为重要的是，快速傅立叶算法非常容易用硬件实现，因此它在电子技术领域得到极其广泛的应用。

1977 整数关系探测算法
整数关系探测是个古老的问题，其历史甚至可以追溯到欧几里德的时代。
具体的说:给定—组实数X1,X2,...,Xn，是否存在不全为零的整数a1,a2,...an，使得:a1*X1 + a2*X2 + . . . + an*Xn ＝ 0
这一年BrighamYoung大学的Helaman Ferguson 和Rodney Forcade解决了这一问题。至于这个算法的意义嘛，呃，该算法应用于“简化量子场论中的Feynman图的计算”——太深奥的学问拉！

1987 快速多极算法
日历翻到了1987 年，这一年的算法似乎更加玄奥了，耶鲁大学的L e s l i eGreengard和Vladimir Rokhlin提出的快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算