转自<http://blog.csdn.net/v_july_v/article/details/6127953>
译者:July 二零一一年一月十日
------------------------------------
参考文献:
The Best of the 20th Century: Editors Name Top 10 Algorithms。
By Barry A. Cipra。地址:http://www.uta.edu/faculty/rcli/TopTen/topten.pdf。
博主说明:
1、此20世纪的十大算法,除了快速排序算法,或者快速傅里叶变换算法,其它算法只要稍作了解即可。
2、此文非最新文章,只是本人对算法比较感兴趣,所以也做翻译,学习研究下。
===============================
发明十大算法的其中几位算法大师
一、1946 蒙特卡洛方法
[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.]
1946年,美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis
共同发明,被称为蒙特卡洛方法。
它的具体定义是:
在广场上画一个边长一米的正方形,在正方形内部随意用粉笔画一个不规则的形状,
现在要计算这个不规则图形的面积,怎么计算列?
蒙特卡洛(Monte Carlo)方法告诉我们,均匀的向该正方形内撒N(N 是一个很大的自然数)个黄豆,
随后数数有多少个黄豆在这个不规则几何形状内部,比如说有M个,
那么,这个奇怪形状的面积便近似于M/N,N越大,算出来的值便越精确。
在这里我们要假定豆子都在一个平面上,相互之间没有重叠。(撒黄豆只是一个比喻。)
蒙特卡洛方法可用于近似计算圆周率:
让计算机每次随机生成两个0到1之间的数,看这两个实数是否在单位圆内。
生成一系列随机点,统计单位圆内的点数与总点数,内接圆面积和正方形面积之比为PI:4,PI为圆周率。
(多谢网友七里河蠢才指出:S内接圆:S正=PI:4。具体,请看文下第99条评论。十六日修正),
当随机点取得越多(但即使取10的9次方个随机点时,其结果也仅在前4位与圆周率吻合)时,
其结果越接近于圆周率。
二、1947 单纯形法
[1947: George Dantzig, at the RAND Corporation, creates the simplex method for linear programming.]
1947年,兰德公司的,Grorge Dantzig,发明了单纯形方法。
单纯形法,此后成为了线性规划学科的重要基石。
所谓线性规划,简单的说,就是给定一组线性(所有变量都是一次幂)约束条件
(例如a1*x1+b1*x2+c1*x3>0),求一个给定的目标函数的极值。
这么说似乎也太太太抽象了,但在现实中能派上用场的例子可不罕见——比如对于一个公司而言,其能够投入生产的人力物力有限(“线性约束条件”),而公司的目标是利润最大化(“目标函数取最大值”),看,线性规划并不抽象吧!
线性规划作为运筹学(operation research)的一部分,成为管理科学领域的一种重要工具。
而Dantzig提出的单纯形法便是求解类似线性规划问题的一个极其有效的方法。
三、1950 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.]
1950年:美国国家标准局数值分析研究所的,马格努斯Hestenes,爱德华施蒂费尔和
科尼利厄斯的Lanczos,发明了Krylov子空间迭代法。
Krylov子空间迭代法是用来求解形如Ax=b 的方程,A是一个n*n 的矩阵,当n充分大时,直接计算变得非常
困难,而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi的迭代形式来求解。
这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵,
而迭代形式的算法的妙处在于,它将复杂问题化简为阶段性的易于计算的子步骤。
四、1951 矩阵计算的分解方法
[1951: Alston Householder of Oak Ridge National Laboratory formalizes the decompositional approach to matrix computations.]
1951年,阿尔斯通橡树岭国家实验室的Alston Householder提出,矩阵计算的分解方法。
这个算法证明了任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵,
该算法的意义使得开发灵活的矩阵计算软件包成为可能。
五、1957 优化的Fortran编译器
[1957: John Backus leads a team at IBM in developing the Fortran optimizing compiler.]
1957年:约翰巴库斯领导开发的IBM的团队,创造了Fortran优化编译器。
Fortran,亦译为福传,是由Formula Translation两个字所组合而成,意思是“公式翻译”。
它是世界上第一个被正式采用并流传至今的高级编程语言。
这个语言现在,已经发展到了,Fortran 2008,并为人们所熟知。
六、1959-61 计算矩阵特征值的QR算法
[1959–61: J.G.F. Francis of Ferranti Ltd, London, finds a stable method for computing
eigenvalues, known as the QR algorithm.]
1959-61:伦敦费伦蒂有限公司的J.G.F. Francis,找到了一种稳定的特征值的计算方法,
这就是著名的QR算法。
这也是一个和线性代数有关的算法,学过线性代数的应该记得“矩阵的特征值”,计算特征值是矩阵计算的
最核心内容之一,传统的求解方案涉及到高次方程求根,当问题规模大的时候十分困难。
QR算法把矩阵分解成一个正交矩阵(希望读此文的你,知道什么是正交矩阵。:D。)与一个上三角矩阵的积,
和前面提到的Krylov 方法类似,这又是一个迭代算法,它把复杂的高次方程求根问题化简为阶段性的易于
计算的子步骤,使得用计算机求解大规模矩阵特征值成为可能。
这个算法的作者是来自英国伦敦的J.G.F. Francis。
七、1962 快速排序算法
[1962: Tony Hoare of Elliott Brothers, Ltd., London, presents Quicksort.]
1962年:伦敦的,托尼埃利奥特兄弟有限公司,霍尔提出了快速排序。
哈哈,恭喜你,终于看到了可能是你第一个比较熟悉的算法~。
快速排序算法作为排序算法中的经典算法,它被应用的影子随处可见。
快速排序算法最早由Tony Hoare爵士设计,它的基本思想是将待排序列分为两半,
左边的一半总是“小的”,右边的一半总是“大的”,这一过程不断递归持续下去,直到整个序列有序。
说起这位Tony Hoare爵士,快速排序算法其实只是他不经意间的小小发现而已,他对于计算机贡献主要包括
形式化方法理论,以及ALGOL60 编程语言的发明等,他也因这些成就获得1980 年图灵奖。
快速排序的平均时间复杂度仅仅为O(Nlog(N)),相比于普通选择排序和冒泡排序等而言,
实在是历史性的创举。
八、1965 快速傅立叶变换
[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.]
1965年:IBM 华生研究院的James Cooley,和普林斯顿大学的John Tukey,
AT&T贝尔实验室共同推出了快速傅立叶变换。
快速傅立叶算法是离散傅立叶算法(这可是数字信号处理的基石)的一种快速算法,其时间复杂度仅为O
(Nlog(N));比时间效率更为重要的是,快速傅立叶算法非常容易用硬件实现,因此它在电子技术领域得到
极其广泛的应用。
日后,我会在我的经典算法研究系列,着重阐述此算法。
九、1977 整数关系探测算法
[1977: Helaman Ferguson and Rodney Forcade of Brigham Young University advance an integer
relation detection algorithm.]
1977年:Helaman Ferguson和 伯明翰大学的Rodney Forcade,提出了Forcade检测算法的整数关系。
整数关系探测是个古老的问题,其历史甚至可以追溯到欧几里德的时代。具体的说:
给定—组实数X1,X2,...,Xn,是否存在不全为零的整数a1,a2,...an,使得:a1 x 1 +a2 x2 + . . . + an x
n =0?
这一年BrighamYoung大学的Helaman Ferguson 和Rodney Forcade解决了这一问题。
该算法应用于“简化量子场论中的Feynman图的计算”。ok,它并不要你懂,了解即可。:D。
十、1987 快速多极算法
[1987: Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipole
algorithm.]
1987年:Greengard,和耶鲁大学的Rokhlin发明了快速多极算法。
此快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算
——例如银河系中的星体,或者蛋白质中的原子间的相互作用”。ok,了解即可。
相关推荐
### 20世纪10个最伟大的算法 在20世纪,随着计算机科学与工程的发展,许多里程碑式的算法被提出并极大地推动了信息技术的进步。以下是从Computer in Science & Engineering 和 IEEE Computer Society联合评选出的20...
【世纪最伟大的十大算法】是IT领域中极具影响力的算法集合,这些算法对计算机科学和相关应用产生了深远影响。以下是对这三大算法的详细介绍: 1. **蒙特卡洛方法**: - 蒙特卡洛方法是由John von Neumann、Stan ...
在数模领域,掌握高效的算法是至关重要的,因为这些算法能帮助我们解决各种复杂的问题,并在有限的时间内得出最优解。本文将详细讨论被称为“数模十大算法”的一系列方法,特别是其中与遗传学相关的算法。这十大算法...
Matlab十大算法源代码 Floyd算法 动态规划 分治算法 概率算法 灰色预测 聚类算法 类比法 蒙特卡洛 模拟退火,禁忌搜索,遗传算法,神经网络-MATLAB程序合集 模拟退火算法 神经网络 搜索算法 贪婪算法 图论...
十大算法精讲资料中包含了<树>、<链表栈递归>、<图论>、<贪心法与动态规划>、<认识机器学习>、<概率分治机器学习>、等算法的详细介绍。
20世纪10大算法(数学、电子信息、计算机等专业必备基本背景知识
蒙特卡罗方法是由John von Neumann、Stan Ulam和Nick Metropolis于1946年共同开发,被列为20世纪最伟大的算法之一。它基于概率统计理论,利用随机数或伪随机数来解决计算问题。适用于处理高维度和复杂性问题,如...
1. 蒙特卡罗算法:由John von Neumann、Stan Ulam和Nick Metropolis于1946年共同发明,是20世纪最伟大的算法之一。这种方法基于概率统计理论,使用随机数或伪随机数来解决复杂的计算问题。例如,通过随机投掷虚拟...
常见10大算法,从原理,动图解析到代码实现,逐步分析,让你轻松入门算法
数学建模十大经典算法
算法导论第二十四章答案 算法导论第二十四章答案 算法导论第二十四章答案
在十六十七世纪,数学发展中的算法倾向是一个关键的主题,这一时期的数学成就为现代大数据和算法研究奠定了基础。本文通过对卡尔丹诺的《大术》、笛卡尔的《几何学》以及沃利斯的插值方法这三例详尽的研究,揭示了...
数学建模竞赛中应当掌握的十类算法,数学建模十大算法程序详解,源代码
这份名为“数据挖掘十大算法英文版pdf”的资源,包含了对数据挖掘领域最具有影响力的十种算法的详细解析,对于学习和理解这些核心算法至关重要。下面将分别介绍这十个算法,并探讨它们在实际应用中的作用。 1. **ID...
数学建模的十大常用算法,包括遗传算法,退火算法,聚类算法,蒙特卡洛算法等。含有代码和文档
资源名:数学建模十大算法程序详解_打包了_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有...
数学建模十大算法 ( 包含:蒙特卡罗算法、数据拟合、参数估计、 插值等数据处理算法、线性规划、整数规划、多元规划、二次规划等规划类问题、 图论算法、动态规划、回溯搜索、分治算法、分支定界等计算机算法、 最...
数据挖掘十大算法,经典资料。包含多种算法原理、模型及细节描述
十种经典的排序算法,桶排序,快速排序,计数排序,插入排序,希尔排序,堆排序等的Java描述与动图示意