博文
20世纪的十大算法
|||
本世纪初，美国物理学会(American Institute of Physics)和IEEE计算机社团 (IEEE Computer Society)的一本联合刊物《科学与工程中的计算》发表了由田纳西大学的Jack Dongarra和橡树岭国家实验室的Francis Sullivan 联名撰写的“世纪十大算法”一文，该 文“试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法”。作者苦于 “任何选择都将是充满争议的，因为实在是没有最好的算法”，他们只好用编年顺序依次列 出了这十项算法领域人类智慧的巅峰之作——给出了一份没有排名的算法排行榜。有趣的是 ，该期杂志还专门邀请了这些算法相关领域的“大拿”为这十大算法撰写十篇综述文章，实 在是蔚为壮观。本文的目的，便是要带领读者走马观花，一同回顾当年这一算法界的盛举。
1. 1946年计算蒙特卡洛过程度伦敦算法；
在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，呃，能帮我算算这个不规则图形的面积么？蒙特卡洛(Monte Carlo)方法便是解决这个问题的巧妙方法:随机向该正方形内扔N（N 是一个很大的自然数）个黄豆，随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个:那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。别小看这个数黄豆的笨办法，大到国家的民意测验，小到中子的移动轨迹，从金融市场的风险分析，到军事演习的沙盘推演，蒙特卡洛方法无处不在背后发挥着它的神奇威力。蒙特卡洛方法由美国拉斯阿莫斯国家实验室的三位科学家John von Neumann（看清楚了，这位可是冯诺伊曼同志！）,Stan Ulam 和 Nick Metropolis共同发明。就其本质而言，蒙特卡洛方法是用类似于物理实验的近似方法求解问题，它的魔力在于，对于那些规模极大的问题，求解难度随着问题的维数（自变量个数）的增加呈指数级别增长，出现所谓的“维数的灾难”（Course of Dimensionality）。对此，传统方法无能为力，而蒙特卡洛方法却可以独辟蹊径，基于随机仿真的过程给出近似的结果。
最后八卦一下，Monte Carlo这个名字是怎么来的？它是摩纳哥的一座以博彩业闻名的城市，赌博其实是门概率的高深学问，不是么？
2. 1947 单纯形法
单纯形法是由大名鼎鼎的“预测未来”的兰德公司的Grorge Dantzig发明的，它成为线性规划学科的重要基石。所谓线性规划，简单的说，就是给定一组线性（所有变量都是一次幂）约束条件（例如a1*x1+ b1*x2+c1*x3>0)，求一个给定的目标函数的极值。这么说似乎也太太太抽象了，但在现实中能派上用场的例子可不罕见——比如对于一个公司而言，其能够投入生产的人力物力有限（“线性约束条件”），而公司的目标是利润最大化（“目标函数取最大值”），看，线性规划并不抽象吧！线性规划作为运筹学(operation research)的一部
分，成为管理科学领域的一种重要工具。而Dantzig提出的单纯形法便是求解类似线性规划
问题的一个极其有效的方法，说来惭愧，本科二年级的时候笔者也学过一学期的运筹学，现
在脑子里能想起的居然只剩下单纯形法了——不过这不也正说明了该方法的简单和直么？顺便说句题外话，写过《万历十五年》的黄仁宇曾说中国的传统是“不能从数目字上管理”
，我们习惯于“拍脑袋”，而不是基于严格的数据做决定，也许改变这一传统的方法之一就
是全民动员学习线性规划喔。
3. 1950 Krylov子空间迭代法
4. 1951 矩阵计算的分解方法
50年代初的这两个算法都是关于线性代数中的矩阵计算的，看到数学就头大的读者恐怕看到 算法的名字已经开始皱眉毛了。Krylov子空间叠代法是用来求解形如Ax=b 的方程，A是一个 n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为 Kxi+1=Kxi+b-Axi的迭代形式来求解。这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤.1951年由橡树岭国家实验室的Alston House holder提出的矩阵计算的分解方法，则证明了任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵，该算法的意义使得开发灵活的矩阵计算软件包成为可能。
5. 1957 优化的Fortran编译器
说实话，在这份学术气息无比浓郁的榜单里突然冒出一个编译器(Compiler)如此工程化的东 东实在让人有“关公战秦琼”的感觉。不过换个角度想想，Fortran这一门几乎为科学计算 度身定制的编程语言对于科学家（尤其是数学家，物理学家）们实在是太重要了，简直是他 们形影不离的一把瑞士军刀，这也难怪他们纷纷抢着要把票投给了它。要知道，Fortran是 第一种能将数学公式转化为计算机程序的高级语言，它的诞生使得科学家们真正开始利用计 算机作为计算工具为他们的研究服务，这是计算机应用技术的一个里程碑级别的贡献。话说回来，当年这帮开发Fortran的家伙真是天才——只用23500行汇编指令就完成了一个 Fortran编译器，而且其效率之高令人叹为观止:当年在IBM主持这一项目的负责人 JohnBackus在数十年后，回首这段往事的时候也感慨，说它生成代码的效率“出乎了所有开发者的想象”。看来作为程序员，自己写的程序跑起来“出乎自己的想象”，有时候还真不 一定是件坏事！
6. 1959-61 计算矩阵特征值的QR算法
呼，又是一个和线性代数有关的算法，学过线性代数的应该还记得“矩阵的特征值”吧？计 算特征值是矩阵计算的最核心内容之一，传统的求解方案涉及到高次方程求根，当问题规模 大的时候十分困难。QR算法把矩阵分解成一个正交矩阵（什么是正交矩阵？！还是赶紧去翻书吧！）与一个上三角矩阵的积，和前面提到的 Krylov 方法类似，这又是一个迭代算法， 它把复杂的高次方程求根问题化简为阶段性的易于计算的子步骤，使得用计算机求解大规模 矩阵特征值成为可能。这个算法的作者是来自英国伦敦的J.G.F. Francis。
7. 1962 快速排序算法
不少读者恐怕和我一样,看到“快速排序算法”（Quick Sort）这个条目时,心里的感觉是——“这可总算找到组织了”。相比于其他一些对程序员而言高深莫测的数学物理公式,快速 排序算法真是我们朝夕相处的好伙伴——老板让你写个排序算法,如果你写出来的不是快速 排序,你都不好意思跟同事打招呼。其实根本不用自己动手实现, 不论是ANSI C,C++ STL,还 是Java SDK,天下几乎所有的SDK里都能找到它的某种实现版本。快速排序算法最早由Tony Hoare爵士设计，它的基本思想是将待排序列分为两半，左边的一半总是“小的”，右边的一半总是“大的”，这一过程不断递归持续下去，直到整个序列有 序。说起这位Tony Hoare爵士，快速排序算法其实只是他不经意间的小小发现而已，他对于计算机贡献主要包括形式化方法理论，以及ALGOL60 编程语言的发明等，他也因这些成就获得1980 年图灵奖。快速排序的平均时间复杂度仅仅为O(Nlog(N))，相比于普通选择排序和冒泡排序等而言，实在是历史性的创举。
8. 1965 快速傅立叶变换
如果要评选对我们的日常生活影响最大的算法，快速傅立叶变换算法应该是当仁不让的总冠 军——每天当拿起话筒，打开手机，听mp3，看DVD，用DC拍照 ——毫不夸张的说，哪里有 数字信号处理，哪里就有快速傅立叶变换。快速傅立叶算法是离散傅立叶算法（这可是数字 信号处理的基石）的一种快速算法，它有 IBM 华生研究院的James Cooley和普林斯顿大学 的John Tukey共同提出，其时间复杂度仅为O(Nlog(N))；比时间效率更为重要的是，快速傅立叶算法非常容易用硬件实现，因此它在电子技术领域得到极其广泛的应用。
9. 1977 整数关系探测算法
整数关系探测是个古老的问题，其历史甚至可以追溯到欧几里德的时代。具体的说:给定—组实数X1,X2,...,Xn，是否存在不全为零的整数a1,a2,...an，使得:a 1 x 1 +a 2 x
2 + . . . + a n x n ＝ 0 这一年BrighamYoung大学的Helaman Ferguson 和Rodney Forcade解决了这一问题。至于这个算法的意义嘛，呃，该算法应用于“简化量子场论中的 Feynman图的计算”——太深奥的学问拉！
10. 1987 快速多极算法
日历翻到了1987 年，这一年的算法似乎更加玄奥了，耶鲁大学的Leslie Greengard和Vladimir Rokhlin提出的快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算——例如银河系中的星体，或者蛋白质中的原子间的相互作用”，天哪，不是我不明白，这世界真是变得快！
所谓浪花淘尽英雄，这些算法的发明者许多已经驾鹤西去。二十一世纪的头五年也已经在不知不觉中从我们指尖滑过，不知下一次十大算法评选的盛事何时再有，也许我们那时已经垂垂老去，也许我们早已不在人世，只是心中唯一的希望——里面该有个中国人的名字吧！
--如欲平治天下，当今之世，舍我其谁！！！
相关文献：
1 Jack Dongarra, Francis Sullivan,Guest Editors Introduction The Top 10 Algorithms,Computing in Science and Engineering,Volume 2, Number 1, January/February 2000, pages 22-23.
Guest Editors Introduction The Top 10 Algorithms.pdf
2 Barry Cipra, The Best of the 20th Century: Editors Name Top 10 Algorithms,SIAM News,Volume 33, Number 4, May 2000, page 1.
The Best of the 20th Century Editors Name Top 10 Algorithms.pdf
3 The Top 10 Computational Methods of the 20th Century, IACM Expressions, Number 11, September 2001, pages 5-9.
the top 10 computational methods of the 20th century.pdf
https://blog.sciencenet.cn/blog-83029-468247.html
上一篇：国家重点基础研究发展计划2011年重要支持方向——制造与工程科学
下一篇：教育搞不好，万恶难除根！
