发明十大算法的其中几位算法大师
一、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:1,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 年图灵奖。
========
关于快速排序算法的具体认识与应用,可参考我写的一篇文章,
精通八大排序算法系列、一、快速排序算法:
http://blog.csdn.net/v_JULY_v/archive/2011/01/04/6116297.aspx
------------------------------------------------------------
快速排序的平均时间复杂度仅仅为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 integerrelation 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,它并不要你懂,了解即可。
十、1987 快速多极算法
[1987: Leslie Greengard and Vladimir Rokhlin of Yale University invent the fast multipolealgorithm.]
1987年:莱斯利的Greengard,和耶鲁大学的Rokhlin发明了快速多极算法。
此快速多极算法用来计算“经由引力或静电力相互作用的N 个粒子运动的精确计算——例如银河系中的星体,或者蛋白质中的原子间的相互作用”。ok,了解即可。
本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/v_JULY_v/archive/2011/01/10/6127953.aspx
相关推荐
【程序员须知的二十世纪最伟大的十大算法】涵盖了计算机科学早期的一些里程碑式创新,这些算法在今天仍然具有重要价值,并广泛应用于各种计算问题。以下是这五个算法的详细说明: 1. **蒙特卡洛方法**(1946年): ...
程序员实用算法+源码,本书一共七个部分全部下载才可正常解压
本文将对程序员必须知道的10大基础实用算法进行讲解,这些算法包括快速排序、堆排序、归并排序、二分查找、BFPRT和深度优先搜索等。这些算法都是编程中经常使用的基础算法,对于程序员的编程能力和代码质量都有着...
在IT行业中,算法是程序员解决问题的关键工具,它们是编程的基础,能够帮助我们高效地处理数据和执行任务。本文档集合中的四个PHP文档深入探讨了程序员应掌握的一些经典算法,这对于提升编程技能至关重要。 首先,...
10. **概率与随机化算法**:如Monte Carlo方法、鸽巢原理等,它们在处理大规模数据和近似计算时特别有用。 学习并熟练掌握这些算法对程序员来说至关重要,不仅能够提高编程效率,还能为解决复杂问题提供有力工具。...
《程序员面试算法大全》是一本面向准备面试的程序员的重要参考资料,涵盖了广泛的算法和数据结构知识。这本书通过详细的代码实现和解题思路,帮助读者提升在面试中的表现,从而提高获得理想职位的机会。以下是对其中...
《程序员的算法趣题》是一本专门为IT从业者和有志于进入这个领域的学习者准备的算法书籍。它通过一系列有趣且富有挑战性的题目,旨在帮助读者深入理解和掌握计算机科学中的核心算法,提升解决实际问题的能力。这本书...
这本书主要聚焦于算法和数据结构,旨在帮助读者掌握在面试中常见的问题,并提供最优解。"左神"作为标签,暗示了这本书的作者或者内容在编程界具有较高的权威性和影响力,"左神"通常是对在编程领域有深厚造诣的人的一...
10. 字符串匹配算法:如KMP算法、Boyer-Moore算法和Rabin-Karp算法,用于在文本中查找特定子串。 以上只是部分编程算法的概述,源代码文件"SourceCode"可能包含了这些算法的实现细节,供程序员学习和参考。理解并...
《程序员实用算法》这本书主要涵盖了计算机科学中程序员经常会遇到的各种算法,这些算法是解决实际问题、优化程序性能的关键。在编程领域,算法就如同工具箱中的各种工具,它们可以帮助程序员高效地处理数据,解决...
【程序员十大技术须知】 1. XML(可扩展标记语言):XML 是现代软件开发中的核心技术,用于存储和传输结构化数据。它采用自描述的文本格式,允许数据以树形结构表示,既能存储结构化数据,也能处理非结构化数据。...
《程序员算法趣题——随书源码》是一个与算法相关的学习资源,包含了增井敏克著作《程序员算法趣题》中的实例代码。增井敏克是算法领域知名的专家,他的书籍通常深入浅出,旨在帮助程序员提升算法思维和解决实际问题...
10. **优化算法**:线性规划、整数规划、遗传算法、模拟退火等,用于求解实际问题的最优解。 通过阅读和实践这些源码,程序员可以加深对算法的理解,提高编程技巧,解决实际项目中的难题,从而提升个人的竞争力。...
《程序员面试经典算法题》是针对程序员在面试过程中可能会遇到的算法问题进行深入解析的一份资源。这份资料旨在帮助程序员提升算法思维,从而在技术面试中脱颖而出。通过学习和掌握这些经典算法,不仅可以提高编程...
常见的算法包括排序(冒泡排序、选择排序、插入排序、快速排序、归并排序等)、查找(线性查找、二分查找、哈希查找)、图算法(深度优先搜索、广度优先搜索、Dijkstra算法、Floyd算法)、字符串匹配(KMP算法、...
《程序员实用算法》这本书是为IT从业者,尤其是程序员量身打造的一本算法学习资料。算法在编程领域中占据着至关重要的地位,它们是解决问题、优化程序效率的关键工具。本书旨在帮助读者理解和掌握实用的算法,提升...
《程序员实用算法》 在IT行业中,算法是程序员的核心竞争力之一。它不仅是解决问题的关键工具,也是提升代码效率、优化程序性能的重要手段。本资源“程序员实用算法”专注于为程序员提供一系列实际工作中的算法知识...