算法历史

① 关于历史时间算法的!

公元纪年是指耶稣降生的那一年，这一年是公元1年【楼上错了，没有公元0年】，之前是公元前1年。
也就是说，公元前1年之后就是公元1年。
公元前的年代数字越大越早，公元后的不用说是数字越大越晚。
公元前几世纪的算法与公元后一样，如：公元19世纪就是1800——1900。
这样明白嘛？

② 最早的算法是什么，他的背景及来源

欧几里得算法被人们认为是史上第一个算法。

欧几里得算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。

欧几里得算法产生的背景：
我们知道，约公元前300年，古希腊着名数学家欧几里得在前人基础上写成的不配名着《几何原本》，几乎包括了中小学所学习的平面几何、立体几何的全部内容。如此古老的几何内容，自然成了历次数学课程改革关注的焦点。其中最为激进的，如法国布尔巴基学派主要人物狄奥东尼甚至喊出了“欧几里得滚出去”的口号。但改来改去，欧氏几何的一些内容，仍然构成了多数国家中小学数学几何部分的主要内容。有人称之为“不倒翁现象”。

③ 求排序算法的发展史

对于今天排序技术的探索可以追溯到19世纪，美国人口统计局的Herman Hollerith发明了第一批具有排序装置的制表机，成功地应用到1890年的美国人口普查。关于Hollerith及其制表机的故事，Leon E. Truesdell曾在【The Development of Punch Card Tabulation（Washington: U. S. Bureau of the Census, 1965）】中进行了有趣而详尽地描述。

排序例程曾经是为存储程序式计算机编写的第一个程序，因为它集中体现了计算机潜在的非数值应用。冯·诺伊曼在1954年为了检验EDVAC计算机指令代码的适用性以及评价他所建议的计算机组织的优点，编写了内部归并排序程序，Knuth在【Computing Surveys 2(1970), 247~260】中描述了这个发展细节。

在德国，K. Zuse于1945年独立编写了用于直接插入排序的程序，作为他的Plankalkul语言中线性表操作的例子之一，这一开创性的工作推迟了近30年才发表。

1946年在穆尔学校举行的有关计算的专题讨论会上，John Mauchly作了“排序和整理”的演讲，是第一个公开发表的关于计算机排序的讨论，包括直接插入排序和折半插入排序。

到1952年左右，内部排序的许多方法已在程序设计领域广为流传，但理论上的研究却相对很少。Daniel Goldenberg用Whirlwind计算机编写了5个不同方法的排序程序，分别就最好情况和最坏情况进行了分析。

由Howard B. Demuth于1956年撰写的博士论文【Electronic Data Sorting. Stanford University, 1956】可以说是一篇非常值得关注的论文，因为这篇论文有助于奠定计算复杂性理论的基础。论文利用循环的、线性的以及随机的存储器，考虑了排序问题的3个抽象模型，并对每个模型提出了最优（或接近最优）的方法。Demuth的论文建立了如何把理论同实践相联系的重要思想。

事实上，计算的大多数早期历史都出现在比较难以得到的报告中，因为那时仅有少数人同计算机打交道。有关排序文献的第一次付印是在1955年，用的是三篇重要的综述性文章。第一篇文章是由J. C. Hosken撰写的【Proc. Eastern Joint Computer Conference 8(1955), 39~55】，综述了在计算机上进行排序的方法，以及所有可利用的专用设备，文中的54项参考文献大多数是以厂家的手册为基础的。第二篇文章是由E. H. Friend撰写的【Sorting on Electronic Computer Systems. Journal of the ACM 3(1956), 134~168】是排序技术发展史的一个重要里程碑，Friend对相当多的内部和外部排序算法给出了细致的描述。第三篇文章是由D. W. Davies撰写的【Proc. Inst. Elec. Engineers 103B, Supplement 1(1956), 87~93】。

1962年11月ACM主持召开了一次关于排序的研讨会，在会上宣读的大多数论文都发表在COMMUNICATIONS OF THE ACM1963年5月的刊物上，这些论文是当时技术发展水平的很好代表。

④ MPS算法的发展历史

1968年,联合国公布SNA体系,并于1970年起在全世界推广。
到上世纪八十年代中期,我国一直用的是MPS体系。 而日本的GDP算法与中国不同,日本采用SNA算法。

⑤ K平均算法的发明历史

k平均聚类发明于1956年， 该算法最常见的形式是采用被称为劳埃德算法(Lloyd algorithm)的迭代式改进探索法。劳埃德算法首先把输入点分成k个初始化分组，可以是随机的或者使用一些启发式数据。然后计算每组的中心点，根据中心点的位置把对象分到离它最近的中心，重新确定分组。继续重复不断地计算中心并重新分组，直到收敛，即对象不再改变分组（中心点位置不再改变）。
劳埃德算法和k平均通常是紧密联系的，但是在实际应用中，劳埃德算法是解决k平均问题的启发式法则，对于某些起始点和重心的组合，劳埃德算法可能实际上收敛于错误的结果。（上面函数中存在的不同的最优解）
虽然存在变异，但是劳埃德算法仍旧保持流行，因为它在实际中收敛非常快。实际上，观察发现迭代次数远远少于点的数量。然而最近，David Arthur和Sergei Vassilvitskii提出存在特定的点集使得k平均算法花费超多项式时间达到收敛。
近似的k平均算法已经被设计用于原始数据子集的计算。
从算法的表现上来说，它并不保证一定得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于该算法的速度很快，因此常用的一种方法是多次运行k平均算法，选择最优解。
k平均算法的一个缺点是，分组的数目k是一个输入参数，不合适的k可能返回较差的结果。另外，算法还假设均方误差是计算群组分散度的最佳参数。

⑥ 辗转相除法、更相减损法和秦九韶算法的历史

辗转相除法,
又名欧几里德算法（Euclidean
algorithm），是已知最古老的算法,
其可追溯至前300年。它首次出现于欧几里德的《几何原本》（第VII卷，命题i和ii）中
更相减损术,又称"等值算法"
，<九章算术>中介绍了这个方法,叫做”更相减损术”,数学家刘徽对此法进行了明确的注解和说明，成书时间在汉朝，先秦就开始编纂。
秦九韶是南宋数学家，所以是南宋。

⑦ 算法的历史

“算法”即算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为algorism，意思是阿拉伯数字的运算法则，在18世纪演变为algorithm。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为well-defined procere缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了着名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用。

⑧ 谁能详细说说Monte Carlo算法的历史

权权的《Monte Carlo方法》系列预告出来时我已注意到，但由于近来时间有限而直到今晚才有时间细读了第一篇《积分方法》。总体而言写得非常清楚，希望能够坚持继续下去。由于整个Bayesian统计学的根基就在Monte Carlo计算法，我对这个领域一向很感兴趣。但由于在研究工作中尚没有机会使用Bayesian统计学，因此有关的知识都还属间接经验，能够在本论坛探讨这个话题肯定会受益。

在点评之前先推荐几本参考资料，我相信下面这个书单是相当不错的，可惜本人尚无时间深入钻研：

* 对英文着作尚有心理障碍者可以参考一本出色的中文教科书：冯康先生所着《数
值计算方法》的第七章《蒙特卡洛方法》（国防工业出版社，1978）；

* 一本可读性极强的英文专着，美国哈佛大学教授Jun Liu所着"Monte Carlo
Strategies in Scientific Computing" (Springer 2002);

* 对Monte Carlo方法在Bayesian统计学中的广泛应用有兴趣者可以适当参考
Andrew Gelman等人所着的"Bayesian Data Analysis" (Second Edition,
2003)之第三部分。

权权将贴子发在物理论坛的目的显然是强调该方法在物理上的运用，我选择在数学论坛加以点评是更看重其统计学背景，着重点各有不同。

>> 蒙特卡洛（Monte Carlo）是摩纳哥公国一个城镇，位于地中海沿岸，以其赌场和豪华
>> 酒店而闻名，所以就有了以随机方法应用于数值计算的一类方法，被称为Monte Carlo

有关Monte Carlo方法历史背景的最精确描述来自Jun Liu的专着，他指出一批物理学家在二战期间为估算薛定谔方程的本征值而发明了一种基于统计抽样的数值计算法，其最初想法归功于Ulam。后来Ulam的同事Metropolis将该方法命名为Monte Carlo。1950年代Metropolis和几名统计物理学同事发表了一篇经典论文，提出了Markov Chain Monte Carlo(MCMC)算法。而MCMC法后来是Bayesian统计学能够不断前进的主要动力。

>> I = ∫ f(x)p(x)dx

这里可以强调一下x是个矢量。而这个积分是概率统计中数学期望的基本定义，可以写成E(f(x))。对于初学者而言，不要忘记概率密度函数p(x)的取值是可以大于1的，归一化条件是对累积密度函数而言。

>> 上述变换就是Monte Carlo积分的基本精神，因为需要用到随机抽样，必然伴随统计误差。

需要用到随机抽样，其动机是想用数值模拟实验中的频率来直接估计一个概率值，而这个概率值是计算许多复杂高维积分的关键。而数值模拟需要产生一个序列的随机数来保证抽样过程的随机性。

>> 因为x_i是按照概率密度p(x)分布的随机变量，f(x_i)也是随机变量

为了论述的清晰，应该说x_i是一个随机矢量，那么f(x_i)就是随机变量（标量）。

>> 而中心极限定理告诉我们，一组独立随机变量之和的概率分布是高斯，其方差等于每一
>> 项随机变量的方差之和

这里关于“中心极限定理”的表述不够精确，容易引起读者混淆，特将Kai-Lai Chung(钟开莱，我国着名数理统计大师许宝禄先生的弟子)概率论教科书中的定义按我的理解方式用英文转述一下：

[Central Limit Theorem] For mutually independent (or weakly correlated) random variables X_1, X_2, ..., X_n with mean mu and variance sigma^2,

√n ( Xbar - mu) / sigma --> N(0,1) in distribution,

where N(0,1) stands for standard Gaussian distribution. This means that the distribution shape of Xbar is more and more like a Gaussian random variable as n increases.

权权的中文表述中漏说了这组随机变量必须来自同一个总体(population)这个重要条件，而且“是高斯”必须改成“在n不断增大时趋向于高斯分布”。

>> 而计算高维积分时，Monte Carlo 方法是较优的选择。

权权只从收敛速度的视角来说明Monte Carlo方法在高维情形下的优越性是不够的，更关键的一点是---Monte Carlo模拟结果的精度和概型的维数D无关！结果的精度显然比收敛速度更为重要，因此Monte Carlo方法特别适合求解高维问题。

另外要指出Monte Carlo方法以O(1/√N)的速度收敛，这在理论上已经无法改善。关键要在实际应用中通过巧妙设计模拟概型和改进抽样方法来降低方差。降低方差的技巧是衡量各种Monte Carlo方法优劣的重要指标。

>> 不妨回顾一下布丰投针实验来结束本篇，在分布着等距平行木纹的地板上投针，要求
>> 针的长度小于木纹之间的距离，几何概形计算结果表明，针与一条木纹相交的概率可
>> 以用针的长度、木纹间距和圆周率π表示。而用几何概形计算概率实质上归结为面积的
>> 计算，也就是积分的计算，布丰投针实验可以说是用随机抽样计算积分的始祖。

Buffon投针实验看似简单，其中蕴含的几何概型思想值得细细品味。令针的长度为L，木纹间距为S，要求L < S。若针的中点到最近的一条平行线的距离为H，用a表示针与平行线的夹角。显然有约束条件0 <= H <= S/2 和 0 <= a <= π。为了使针与平行线相交，必须满足

H <= (L/2) sin(a)

这样针与平行线相交的概率就是两块面积的比值：

p = ∫_0^π (L/2) sin(a) da / (π S/2 ) = 2L / (π S)

这就是权权所说“而用几何概型计算概率实质上归结为面积的计算，也就是积分的计算”。倘若上式分子中的积分是一个复杂的高维积分，我们就可以用Monte Carlo方法模拟出的p值来估算它。当然假如我们感兴趣的是无理数π值的估算，那么由上式可推出：

π_hat = lim 2L / (S p_n)

极限中的n趋向于正无穷。

希望权权在接下来的系列文章中能谈到以下四种Monte Carlo抽样方法：

* Crude Sampling
* Acceptance-Rejection Sampling
* Stratified Sampling
* Importance Sampling

若能谈及MCMC类方法在统计物理学上的运用则更能引人入胜。

⑨ 公钥算法的历史

密码术有很长的历史。古代人在没有高速运算设备的条件下想尽了各种方法，也包含了许多巧妙的构思。早在公元前1900年，一个古埃及书写员就在一个铭文中使用了非标准的象形文字，这是人类最早的有记录的密码术。其后，古代人使用的密码术有如把字母表的顺序颠倒过来、进行字母替代，或者用错后一定数目的位置的字母替代前面的字母。其中有些密码术的构思也是十分巧妙的。
现代密码术的划时代突破，是威特菲尔德;迪菲(Whitfield Diffie)和马丁;海尔曼(Martin Hellman)有关公开密钥加密系统的构想，这是在1976年发表的。但威特菲尔德;迪菲和马丁;海尔曼提供的MH背包算法于1984年被破译，因而失去了实际意义。真正有生命力的公开密钥加密系统算法是由隆;里维斯特(Ronald L. Rivest)、阿迪;沙米尔(Adi Shamir)和雷奥纳德;阿德尔曼(Leonard M.Adlemen)在威特菲尔德·迪菲和马丁;海尔曼的论文的启发下，在1977年发明的，这就是沿用至今的RSA算法。它是第一个既能用于数据加密也能用于数字签名的算法。