野狼地带分享 http://blog.sciencenet.cn/u/huguanhu 踏实做人,认真做事。

博文

20世纪的十大算法

已有 6609 次阅读 2011-7-25 13:20 |个人分类:生活点滴|系统分类:科研笔记| 20世纪的10大算法

20世纪的十大算法

本世纪初,美国物理学会(American Institute of Physics)IEEE计算机社团 (IEEE Computer Society)的一本联合刊物《科学与工程中的计算》发表了由田纳西大学的Jack Dongarra和橡树岭国家实验室的Francis Sullivan 联名撰写的“世纪十大算法”一文,该 文“试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法”。作者苦于 “任何选择都将是充满争议的,因为实在是没有最好的算法”,他们只好用编年顺序依次列 出了这十项算法领域人类智慧的巅峰之作——给出了一份没有排名的算法排行榜。有趣的是 ,该期杂志还专门邀请了这些算法相关领域的“大拿”为这十大算法撰写十篇综述文章,实 在是蔚为壮观。本文的目的,便是要带领读者走马观花,一同回顾当年这一算法界的盛举。

1.   1946年计算蒙特卡洛过程度伦敦算法;

    在广场上画一个边长一米的正方形,在正方形内部随意用粉笔画一个不规则的形状,呃,能帮我算算这个不规则图形的面积么?蒙特卡洛(Monte Carlo)方法便是解决这个问题的巧妙方法:随机向该正方形内扔NN 是一个很大的自然数)个黄豆,随后数数有多少个黄豆在这个不规则几何形状内部,比如说有M:那么,这个奇怪形状的面积便近似于M/NN越大,算出来的值便越精确。别小看这个数黄豆的笨办法,大到国家的民意测验,小到中子的移动轨迹,从金融市场的风险分析,到军事演习的沙盘推演,蒙特卡洛方法无处不在背后发挥着它的神奇威力。蒙特卡洛方法由美国拉斯阿莫斯国家实验室的三位科学家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 GreengardVladimir 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



http://blog.sciencenet.cn/blog-83029-468247.html

上一篇:国家重点基础研究发展计划2011年重要支持方向——制造与工程科学
下一篇:教育搞不好,万恶难除根!

4 田灿荣 许培扬 汤奔阳 杨正瓴

该博文允许注册用户评论 请点击登录 评论 (4 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2020-11-29 10:49

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部