细数 20 世纪最伟大的十大算法

英文:Barry A. Cipra 译者:JULY 链接:blog.csdn.net/v_july_v/article/details/6127953 发明十大算法的其中几位算法大师

一、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为圆周率。

当随机点取得越多(但即使取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,使得:a1x1 + a2x2 + . . . + anxn =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,了解即可。

免责声明:本文系网络转载。版权归原作者所有。如涉及版权,请联系删除!

原文发布于微信公众号 - 智能算法(AI_Algorithm)

原文发表时间:2016-07-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

水波模拟算法

一、理论依据 水波的物理学模型便是理论依据。水波有如下特性: 扩散:水波总是从被扰动的中心向外扩散。在水波扩散过程中每个点都在得到能量后以自己为中心震动,并向四...

4059
来自专栏用户3246163的专栏

3.2 利率相关产品

CF(receive FRA) value = L * (FRA-R)*(T2-T1)

5613
来自专栏深度学习与数据挖掘实战

前沿|概率图模型

在过去10年里,特别是在深度学习(Deep Learning)红得发紫之前,概率图模型(Probabilistic Graphical Model)曾经是当仁不...

1331
来自专栏量子位

如何用卷积神经网络从歌曲中提取纯人声?这里有教程+代码

安妮 编译整理自 Madebyollin博客 量子位 报道 | 公众号 QbitAI 你应该对阿卡贝拉(Acapella)不陌生吧。这种无伴奏合唱的纯音乐起源于...

5207
来自专栏量化投资与机器学习

机器学习的前期入门汇总

机器学习机器学习是近20多年兴起的一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以...

2405
来自专栏大数据文摘

英国科学期刊选出了世界上最美丽的10个公式

1603
来自专栏机器之心

机器之心「GMIS 2017」嘉宾揭秘:LSTM之父Jürgen Schmidhuber

2017 全球机器智能峰会(GMIS 2017),让我们近距离接触「LSTM 之父」Jürgen Schmidhuber。 2017 全球机器智能峰会(GMIS...

3198
来自专栏机器人网

无人机用陀螺仪的数据处理

1 陀螺仪数据校准 1.1 原理 一款飞控上的传感器是需要进行校准的,比如这里讲的陀螺仪。目前大多数的陀螺校准其实就是去掉零点偏移量,采集一定的数据,求平均,...

6986
来自专栏龙行天下CSIEM

科学瞎想系列之五十 场是个神马鬼

无论你信与不信,它无时无刻不存在着; 无论你用与不用,它无时无刻不作用着; 无论你懂与不懂,它无时无刻不影响着。 ...

3104
来自专栏Vamei实验室

线性代数01 线性的大脑

作者:Vamei 出处:http://www.cnblogs.com/vamei 严禁任何形式转载。

1593

扫码关注云+社区

领取腾讯云代金券