`

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

阅读更多

转自<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,了解即可。

分享到:
评论

相关推荐

    全球变风量(VAV)系统市场研究:年复合增长率(CAGR)为 5.8%

    在全球建筑行业不断追求节能与智能化发展的浪潮中,变风量(VAV)系统市场正展现出蓬勃的发展潜力。根据 QYResearch 报告出版商的深入调研统计,预计到 2031 年,全球变风量(VAV)系统市场销售额将飙升至 1241.3 亿元,在 2025 年至 2031 年期间,年复合增长率(CAGR)为 5.8%。这一令人瞩目的数据,不仅彰显了 VAV 系统在当今建筑领域的重要地位,更预示着其未来广阔的市场前景。​ 变风量系统的起源可追溯到 20 世纪 60 年代的美国。它犹如建筑空调系统中的 “智能管家”,能够敏锐地感知室内负荷或室内所需参数的变化,通过维持恒定的送风温度,自动、精准地调节空调系统的送风量,从而确保室内各项参数始终满足空调系统的严格要求。从系统构成来看,变风量系统主要由四个基本部分协同运作。变风量末端设备,包括 VAV 箱和室温控制器,如同系统的 “神经末梢”,负责接收室内环境变化的信号并做出初步响应;空气处理及输送设备则承担着对空气进行净化、加热、冷却等处理以及高效输送的重任;风管系统,涵盖新风、排风、送风、回风等管道,构建起了空气流通的 “高速公路”;而自动控制系统宛

    《基于YOLOv8的跆拳道训练系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    探究ChatGPT情感化交互对其用户情绪健康的多方法研究

    内容概要:本文探讨了ChatGPT这种高级语音模式的人工智能聊天机器人与用户的互动对其情绪健康的影响。研究采用了两种互补的方法:大规模平台数据分析和随机对照试验(RCT)。平台数据部分通过对超过400万次对话进行隐私保护的大规模自动化分析以及对4000多名用户的调查,揭示了高频率使用者表现出更多的情感依赖和较低的社会交往意愿。RCT部分则通过近1000名参与者为期28天的研究,发现语音模型相较于文本模型能带来更好的情绪健康效果,但长时间使用可能导致负面后果。此外,初始情绪状态较差的用户在使用更具吸引力的语音模型时,情绪有所改善。 适合人群:对人机交互、情感计算和社会心理学感兴趣的科研人员和技术开发者。 使用场景及目标:本研究旨在为AI聊天机器人的设计提供指导,确保它们不仅能满足任务需求,还能促进用户的心理健康。同时,也为政策制定者提供了关于AI伦理使用的思考。 其他说明:研究强调了长期使用AI聊天机器人可能带来的复杂心理效应,特别是对于那些已经感到孤独或社交孤立的人来说,过度依赖可能会加剧这些问题。未来的研究应该更加关注这些极端情况下的用户体验。

    Java反射性能优化:深入探讨setAccessible与MethodHandle的技术差异及应用场景

    Java 反射(Reflection)是一种强大的机制,允许程序在运行时检查和操作类的成员变量和方法。然而,传统的 `setAccessible(true)` 方式虽然便捷,但存在安全性问题,并且性能相对较低。在 Java 7 引入 `MethodHandle` 后,我们可以通过 `MethodHandles.Lookup.findVirtual()` 提供更优雅、高效的方式来访问对象属性。本文将对比这两种反射方式,并分析它们的优缺点。

    loongdomShop.tar.gz

    loongdomShop.tar.gz

    人工智能与人类行为对聊天机器人社会心理效应的纵向随机对照研究

    内容概要:本文探讨了不同交互模式(文本、中性语音、吸引人语音)和对话类型(开放式、非个人化、个人化)对聊天机器人使用者的心理社会效果(如孤独感、社交互动、情感依赖、不当使用)的影响。研究表明,在初期阶段,语音型聊天机器人比文本型更能缓解孤独感并减少情感依赖,但随着每日使用时间增加,这种优势逐渐消失,尤其是对于中性语音聊天机器人。此外,个人话题对话略微增加了孤独感,而非个人话题则导致更高的情感依赖。总体而言,高频率使用聊天机器人的用户表现出更多的孤独感、情感依赖和不当使用,同时减少了真实人际交往。研究还发现,某些个体特征(如依恋倾向、情绪回避)使用户更容易受到负面影响。 适合人群:心理学家、社会学家、人工智能研究人员以及关注心理健康和人机交互的专业人士。 使用场景及目标:①帮助理解不同类型聊天机器人对用户心理健康的潜在影响;②为设计更健康的人工智能系统提供指导;③制定政策和规范,确保聊天机器人的安全和有效使用。 其他说明:研究强调了进一步探索聊天机器人管理情感内容而不引发依赖或替代人际关系的重要性,呼吁更多跨学科的研究来评估长期影响。

    MP4575GF-Z 产品规格书

    MP4575GF-Z MP4575 TSSOP-20 降压型可调DC-DC电源芯片

    界面设计_SwiftUI_习惯养成_项目管理_1742850611.zip

    界面设计_SwiftUI_习惯养成_项目管理_1742850611.zip

    免安装版的logic软件包 支持波形实时查看 内含驱动文件

    免安装版的logic软件包。支持波形实时查看。内含驱动文件。

    基于Springboot+Mysql的学生毕业离校系统(含LW+PPT+源码+系统演示视频+安装说明).zip

    1. **系统名称**:学生毕业离校系统 2. **技术栈**:Java技术、MySQL数据库、Spring Boot框架、B/S架构、Tomcat服务器、Eclipse开发环境 3. **系统功能**: - **管理员功能**:首页、个人中心、学生管理、教师管理、离校信息管理、费用结算管理、论文审核管理、管理员管理、留言板管理、系统管理。 - **学生功能**:首页、个人中心、费用结算管理、论文审核管理、我的收藏管理。 - **教师功能**:首页、个人中心、学生管理、离校信息管理、费用结算管理、论文审核管理。

    WebSocket测试Demo程序

    配套文章:https://blog.csdn.net/gust2013/article/details/139608432

    蓝凌OA系统V15.0管理员手册

    蓝凌OA系统V15.0管理员手册

    《基于YOLOv8的生物样本识别系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    mips-gcc520-glibc222编译工具链.zip

    mips-gcc520-glibc222编译工具链.zip

    社交网络_React_Native_开发教程_学习资源_1742847416.zip

    app开发

    Swift编程语言的基础特性与应用开发入门教程

    内容概要:本文档详细介绍了Swift编程语言的基础知识,涵盖语言特点、基础语法、集合类型、控制流、函数定义、面向对象编程、可选类型、错误处理、协议与扩展以及内存管理等方面的内容。此外还简要提及了Swift与UIKit/SwiftUI的关系,并提供了进一步学习的资源推荐。通过这份文档,读者可以全面了解Swift的基本概念及其在iOS/macOS/watchOS/tvOS平台的应用开发中的使用方法。 适合人群:初学者或者希望从其他编程语言转向Swift的开发者。 使用场景及目标:帮助读者快速上手Swift编程,掌握其基本语法和特性,能够独立完成简单的程序编写任务,为进一步学习高级主题如并发编程、图形界面设计打下坚实的基础。 阅读建议:由于Swift是一门现代化的语言,拥有许多独特的特性和最佳实践方式,在学习过程中应当多加练习并尝试理解背后的原理。同时利用提供的官方文档和其他辅助材料加深印象。

    《基于YOLOv8的泰拳训练辅助系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    《基于YOLOv8的室内装修质量检测系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    《基于YOLOv8的雕塑识别系统》(包含源码、完整数据集、可视化界面、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

Global site tag (gtag.js) - Google Analytics