20世纪最好的10个算法

━╅点滴╆━ | 2007-09-24 08:09:00 | 阅读 1532 次 | 评论(0)
  20世纪最好的算法,计算机时代的挑选标准是对科学和工程的研究和实践影响最大。本文按年代次序排列的20世纪最好的10个算法。

  人类在20世纪产生了10个著名的算法,是什么算法?本文介绍了美国科学家评出的10个算法。

一、算法一词的来源

  Algos是希腊字,意思是“疼”,A1gor是拉丁字,意思是“冷却”。这两个字都不是Algorithm(算法)一词的词根,a1gorithm一词却与9世纪的阿拉伯学者al-Khwarizmi有关,他写的书《al-jabr w’al muqabalah》(代数学)演变成为现在中学的代数教科书。Ad-Khwarizmi强调求解问题的有条理的步骤。如果他能活到今天的话,他一定会被以他的名字而得名的方法的进展所感动。

二、20世纪10最好的算法

  20世纪最好的算法,计算机时代的挑选标准是对科学和工程的研究和实践影响最大。下面就是按年代次序排列的20世纪最好的10个算法。

1. Monte Carlo方法

1946年,在洛斯阿拉莫斯科学实验室工作的John von Neumann,Stan Ulam和Nick Metropolis编制了Metropolis算法,也称为Monte Carlo方法。Metropolis算法旨在通过模仿随机过程,来得到具有难以控制的大量的自由度的数值问题和具有阶乘规模的组合问题的近似解法。数字计算机是确定性问题的计算的强有力工具,但是对于随机性(不确定性)问题如何当时并不知晓,Metropolis算法可以说是最早的用来生成随机数,解决不确定性问题的算法之一。

2. 线性规划的单纯形方法

1947年,兰德公司的Grorge Dantzig创造了线性规划的单纯形方法。就其广泛的应用而言,Dantzig算法一直是最成功的算法之一。线性规划对于那些要想在经济上站住脚,同时又有赖于是否具有在预算和其他约束条件下达到最优化的能力的工业界,有着决定性的影响(当然,工业中的“实际”问题往往是非线性的;使用线性规划有时候是由于估计的预算,从而简化了模型而促成的)。单纯形法是一种能达到最优解的精细的方法。尽管理论上讲其效果是指数衰减的,但在实践中该算法是高度有效的——它本身说明了有关计算的本质的一些有趣的事情。

3. Krylov子空间叠代法

1950年,来自美国国家标准局的数值分析研究所的Magnus Hestenes, Eduard Stiefel和Cornelius Lanczos开创了Krylov子空间叠代法的研制。这些算法处理看似简单的求解形为
Ax=b
的方程的问题。当然隐藏的困难在于A是一个巨型的n*n 矩阵,致使代数解
x=b/A
是不容易计算的(确实,矩阵的“相除”不是一个实际上有用的概念)。叠代法——诸如求解形为
Kx(k+1)=Kx(k)+b-Ax(k)
的方程,其中K 是一个理想地“接近”A 的较为简单的矩阵——导致了Krylov子空间的研究。以俄罗斯数学家Nikolai Krylov命名的Krylov子空间由作用在初始“余量”向量
r(0)=b-Ax(0)
上的矩阵幂张成的。当 A是对称矩阵时,Lanczos找到了一种生成这种子空间的正交基的极好的方法。对于对称正定的方程组,Hestenes 和Stiefel提出了称为共轭梯度法的甚至更妙的方法。过去的50年中,许多研究人员改进并扩展了这些算法。当前的一套方法包括非对称方程组的求解技巧,像字首缩拼词为GMRES和Bi-CGSTAB那样的算法。(GMRES和Bi-CGSTAB分别首次出现于1986和1992 SIAM journal on Scientific and Statistical computing(美国工业与应用数学学会的科学和统计计算杂志)。

4. 矩阵计算的分解方法

1951年,橡树岭国家实验室的A1ston Householder系统阐述了矩阵计算的分解方法。研究证明能把矩阵因子分解为三角、对角、正交和其他特殊形式的矩阵是极其有用的。这种分解方法使软件研究人员能生产出灵活有效的矩阵软件包。这也促进了数值线性代数中反复出现的大问题之一的舍入误差分析问题。 (1961年伦敦国家物理实验室的James Wilkinson基于把矩阵分解为下和上三角矩阵因子的积的LU分解,在美国计算机协会(ACM)的杂志上发表了一篇题为“矩阵逆的直接方法的误差分析”的重要文章。)

5. Fortran最优编译程序

1957年,John Backus在IBM领导一个小组研制Fortran最优编译程序。Fortran的创造可能是计算机编程历史上独一无二的最重要的事件:科学家(和其他人)终于可以无需依靠像地狱那样可怕的机器代码,就可告诉计算机他们想要做什么。虽然现代编译程序的标准并不过分――Fortran I只包含23,500条汇编语言指令――早期的编译程序仍然能完成令人吃惊的复杂计算。就像Backus本人在1998年在IEEE annals of the History of computing 发表的有关Fortran I,II, III的近代历史的文章中回忆道:编译程序“所产生的如此有效的代码,使得其输出令研究它的编程人员都感到吓了一跳。”

6. 矩阵本征值计算的QR算法

1959—61年,伦敦Ferranti Ltd.的J.G. F. Francis找到了一种称为QR算法的计算本征值的稳定的方法。本征值大

文章评论,共0条
游客请输入验证码