关于20世纪最伟大的算法简述

一、蒙特卡洛方法

1946年，美国拉斯阿莫斯国家实验室的三位科学家John von Neumann,Stan Ulam 和 Nick Metropolis 共同发明，被称为蒙特卡洛方法。

蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。

蒙特卡罗方法解题过程的三个主要步骤:(1)构造或描述概率过程；(2)实现从已知概率分布抽样；(3)建立各种估计量。

二、单纯形法

单纯形法是由美国数学家G.B.丹齐克（1914～　）于1947年提出来的，它与苏联数学家Л.Β.坎托罗维奇（1912～　）于1938年提出的解乘数法相类似。

单纯形法，可按现代电子计算机标准程序求解线性规划模型的一般方法。分为代数形式的单纯形法和表格形式的单纯形法。前者提供基本算法所依据的逻辑规则，适用于在电子计算机上进行求解运算；后者将变量和数据列成表格，适用于笔算。两者在数学上是等价的。

单纯形法的一般解题步骤可归纳如下:①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件(这时目标函数值不能再改善)，即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

三、Krylov 子空间迭代法

1950年：美国国家标准局数值分析研究所的，马格努斯Hestenes，爱德华施蒂费尔和科尼利厄斯的Lanczos，发明了Krylov子空间迭代法。

Krylov子空间迭代法是用来求解形如Ax=b 的方程，A是一个n*n 的矩阵，当n充分大时，直接计算变得非常困难，而Krylov方法则巧妙地将其变为Kxi+1=Kxi+b-Axi的迭代形式来求解。

这里的K(来源于作者俄国人Nikolai Krylov姓氏的首字母)是一个构造出来的接近于A的矩阵，而迭代形式的算法的妙处在于，它将复杂问题化简为阶段性的易于计算的子步骤。

四、矩阵计算的分解方法

1951年，阿尔斯通橡树岭国家实验室的Alston Householder提出，矩阵计算的分解方法。

这个算法证明了任何矩阵都可以分解为三角、对角、正交和其他特殊形式的矩阵，该算法的意义使得开发灵活的矩阵计算软件包成为可能。

五、快速排序算法

由C. A. R. Hoare在1962年提出，它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

六、快速傅立叶变换

快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的，快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称，简称FFT。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点:一是周期性;二是对称性，这里符号*代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。