算法的历史

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

对于今天排序技术的探索可以追溯到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月的刊物上，这些论文是当时技术发展水平的很好代表。

这个很难界定，看看下面资料吧 1.西元1801年法国人约瑟夫�6�4杰夸德(JosephJacquard)发明使用打孔卡片(Punched carboard card)控制的自动化织布机。对未来电脑的发展引进两个重要的观念：一、资讯可以在打孔卡片上编脊毁高码(Coded)二、资讯可以储存在卡片上，而且当这些卡片成串的组合在一起，就可以做为一连串的指令 - 实际上也就是程式。 2.西元1833年英国数学家剑桥大学的查理�6�4巴贝基(Charles Babbage)完成一部差分机(Difference engine)，尔后并完成一部功能更强的机器，称为分析机(Analytical engine)，这一部机器在观念上与现代电脑极为相似，对计算机余渗贡献良多，因尊称为「电脑之父」。至於分析机的有些构思是来自其密友兼同事 - 萝蕾斯伯爵夫人(Countess of Lovelace)，即诗人拜仑(Byron)的女儿艾达�6�4奥古斯塔(Ada Augusta)的惊人见解。她被公认为"程式设计的鼻祖"(The first programmer)，她所研究就是一种用来送入分析机，并能使这部机器执行工作的指令。 3. 西元1890年，美国政府授命赫勒里斯制造一部机器，来协助执行1890年美国人口普查工作。这部机器是以打孔片储存资料，而且是由电力带动的。由於这部机器的协助，人口普查的统计结果只花了三年的时间就完成了(如1880年度的人口普查资料花了七年的时间才统计完成，而且官员们还担心著是否会遗漏了其中某些的细节)。 这些发明只是用来辅助计算的工具樱尺，它们都没有记忆与储存资料的功能， 因此不能称为 『 电脑 』。 二.发展史：世界上第一部『 电脑 』是由 美国人毛琪雷与爱克特在 1946 年发明。随著电脑科技之进步，『 电脑 』已由庞然大物演变到现在的微型电脑，也就是我们所称的 个人电脑 ( Personal Computer ) 简称 PC。 三. 电脑的特性： 1.速度快 2.储存容量大 3.准确性高

---