算法的发展史.doc

算法的发展史（时间轴）公元前4000年 - 在这儿，我们必须提到远古的苏美尔人。 我们都知道，人类文明的发祥地是在两河流域一带，约公元前4000年，在两河流域的交汇处，孕育着聪明的苏美尔人，是他们发明了人类最早的文字楔形文字，以及“一周七天”，“一年十二个月”等历算法。公元前3000年 - 一个多位数的乘法就是通过多次使用一位数乘法, 一位数加法和进位运算规则实现的, 可以看作是一个算法过程. 人类最早关于算法的记录是在两河流域发现的公元前两三千年的黏土板, 其中的一个典型例子就是计算利息何时能够等于本金. 算法早期发展中值得一提的另一个成果应归功于古希腊的欧几里德 .一个多位数的乘法就是通过多次使用一位数乘法, 一位数加法和进位运算规则实现的, 可以看作是一个算法过程. 人类最早关于算法的记录是在两河流域发现的公元前两三千年的黏土板, 其中的一个典型例子就是计算利息何时能够等于本金.公元前2698年 - 5、黄帝，与炎帝同为少典所生，史记记载炎帝、黄帝为兄弟，公元前2698年，黄帝的有熊部落打败炎帝的神农部落和蚩尤的九黎部落统一中国，建立黄帝王朝。 点评：黄帝原名姬轩辕，为儒家尊崇的五帝之一。 传说中黄帝发明了房屋、衣裳、车船、兵器、阵法、音乐、器具、井田。 黄帝的妻子和大臣 .黄帝，与炎帝同为少典所生，史记记载炎帝、黄帝为兄弟，公元前2698年，黄帝的有熊部落打败炎帝的神农部落和蚩尤的九黎部落统一中国，建立黄帝王朝。 点评：黄帝原名姬轩辕，为儒家尊崇的五帝之一。 传说中黄帝发明了房屋、衣裳、车船、兵器、阵法、音乐、器具、井田。 黄帝的妻子和大臣也各有贡献，妻子螺祖发明养蚕抽丝，大臣仓颉发明文字，大臣隶首发明算法，大臣容成发明历法。公元前2100年 - 从这些历史资料中，人们发现：在公元前2100年左右，美索不达米亚人已有了乘法表，其中使用着六十进位制的算法。这些符号实际上就是巴比伦人所用的文字，人们称它为“楔形文字”。 科学家经过研究发现，泥版上记载的，是巴比伦人已获得的知识，其中有大量的数学知识，大约有300块是纯数学的内容，其中约200块是各种数表,包括乘法表、倒数表、平方和立方表等。 从这些历史资料中，人们发现：在公元前2100年左右，美索不达米亚人已有了乘法表，其中使用着六十进位制的算法。公元前2100年 - 公元前2100年，中国夏朝出现象征吉祥的河图洛书纵横图，即为“九宫算”，这被认为是现代“组合数学”最古老的发现。 美索不达米亚人已有了乘法表，其中使用着六十进位制的算法。 公元前1900前1600，古埃及的纸草书上出现数学记载，已有基于十进制的记数法，将乘法简化为加法的算术、分数 .公元前2100年，中国夏朝出现象征吉祥的河图洛书纵横图，即为“九宫算”，这被认为是现代“组合数学”最古老的发现。 美索不达米亚人已有了乘法表，其中使用着六十进位制的算法。公元前2000年 - 在大约公元前两千年，巴比伦人设计了一个以两朔月29 1/2天平均周期为基本的历制。 在这个历制中，一年分为十二个阴历月，总计354 日。 由于这套算法比太阳日少了11天， 不久后收获祭典举行的季节不对了。 为了保证祭典和季节之间的正确关系，祭司忽然想出一套仍在使用的办法-闰法，将 .在大约公元前两千年，巴比伦人设计了一个以两朔月29 1/2天平均周期为基本的历制。 在这个历制中，一年分为十二个阴历月，总计354 日。 由于这套算法比太阳日少了11天， 不久后收获祭典举行的季节不对了。 为了保证祭典和季节之间的正确关系，祭司忽然想出一套仍在使用的办法-闰法，将额外的日或月加入，以修正不吻合的天文周期，而使得历制和自然节期调和。公元前2000年 - 在一些方面，达罗毗托人的文化比埃及和苏马连文化高。 他们有自己的独特的文字，有十进制的算法。 大约公元前两千年的时候，印度人就已经使用51个字母组成的文字，数学在印度曾被认为最重要的科学之一。 和许多古老的民族一样，它的头一批数学家也是僧侣。早在公元前1900年,一个古埃及书写员就在一个铭文中使用了非标准的象形文字,这是人类最早的有记录的密码术.公元前1400年 - 大约在这时，美索不达米亚人有了乘法表，其中使用着六十进位制的算法。 稍后，即公元前1900前1600，古埃及的纸草书上出现数学记载。公元前400年 -密码最早用于军事用途应该是公元前400年的斯巴达人，他们使用了一种叫做“天言”的情报传递方式。恺撒密码只是很经典，古典密码阶段各种经典算法都是由其变化而来， 不过确实称不上第一。公元前300年 - 辗转相除法是求最大公约数的一种算法，是由古希腊著名数学家欧几里得在公元前300年左右提出的,因而又叫欧几里得算法. 这个算法本质上揭示了一个定理:对于两个正整数ab ,如果a=bq+r(0rb),那么a,b的最大公约数等于b,r的最大公约数. 其算法的具体步骤为: 第一步:输入两个正整数a,b(ab .辗转相除法是求最大公约数的一种算法，是由古希腊著名数学家欧几里得在公元前300年左右提出的,因而又叫欧几里得算法. 这个算法本质上揭示了一个定理:对于两个正整数ab ,如果a=bq+r(0rb),那么a,b的最大公约数等于b,r的最大公约数. 其算法的具体步骤为: 第一步:输入两个正整数a,b(ab), 第二步:计算ab的余数r; 第三步:a=b,b=r; 第四步:若r=0,则最大公约数为m;否则返回第二步.公元前240年 - 约公元前240年，古希腊数学家埃拉托斯特尼首先提出了一种判断一个数是否素数的简单方法。 但随着数字的增大，使用这种方法所需的时间成指数增长。 从那以后数学家们一直试图寻找一种“多项式时间”算法，以便在合理时间里解决问题。公元前200年 - 矩阵作为数的长方阵列，大概出现在公元前200年的中国数学中，不过它们仅仅是线性方程组的缩写。 矩阵变得重要仅当它们被施以加法、减法、尤其是乘法；矩阵变得更重要，这通过它们能派的用处就能看出来。 在高斯的算术研究（Disquisitiones）中，矩阵被隐式地作为线性变换的缩写而提出 .矩阵作为数的长方阵列，大概出现在公元前200年的中国数学中，不过它们仅仅是线性方程组的缩写。 矩阵变得重要仅当它们被施以加法、减法、尤其是乘法；矩阵变得更重要，这通过它们能派的用处就能看出来。 在高斯的算术研究（Disquisitiones）中，矩阵被隐式地作为线性变换的缩写而提出，但现在却是以一种意义深远的方式。 高斯对二元二次型f(x,y)=ax 2 +bxy+cy 2 的算法理论做了深入研究。公元前50年 - 密文:mldqjal qrupdo xqlyhuvlwb 公元前50年,古罗马的凯撒大帝在高卢战争中采用的加密方法. 凯撒密码算法就是把每个英文字母向前推移K位.公元前46年 - 由于资料欠缺加强读者的记忆在先开始虽然讲了关于历史的知识和一些算法，虽然有些罗嗦但希望对读者有些帮助。 这还得从公历历法谈起： 原来公历的前身是公元前46年古罗马皇帝儒略 恺撒创始的。 恺撒当皇帝时，当时的历法与天象气候等相差3个月之多（冬天变成了春天，春天变成了夏天，夏天变 .公历的前身是公元前46年古罗马皇帝儒略 恺撒创始的。 恺撒当皇帝时，当时的历法与天象气候等相差3个月之多（冬天变成了春天，春天变成了夏天，夏天变成了秋天，秋天变成了冬天），于是他采纳了一位埃及天文学家的建议，废除旧历，颁布一种完全的太阳历，即儒略历。公元50年 - 给出了多项式求值的“秦九韶算法”. 创造了解线性方程组的“首图终图法”，等价于高斯消元法. 给出了求三角形面积的“三斜求积公式”，等价于古希腊数学家海伦于公元50年给出“ 海伦公式”.公元100年 - 九章数学成书于公元1百年，记录加减乘除四种运算和比例算法，开平方、开立米、求解一元二次方程和负数观点都是世界最先的公元263年 - 263年，三国魏人刘徽注释九章算术，在九章算术注中不仅对原书的方法、公式和定理进行一般的解释和推导，系统地阐述了中国传统数学的理论体系与数学原理，而且在其论述中多有创造，在卷1方田中创立割圆术（即用圆内接正多边形面积无限逼近圆面积的办法），为圆周率的研究工作 .263年，三国魏人刘徽注释九章算术，在九章算术注中不仅对原书的方法、公式和定理进行一般的解释和推导，系统地阐述了中国传统数学的理论体系与数学原理，而且在其论述中多有创造，在卷1方田中创立割圆术（即用圆内接正多边形面积无限逼近圆面积的办法），为圆周率的研究工作奠定理论基础和提供了科学的算法，他运用“割圆术”得出圆周率的近似值为3927/1250（即3.1416）；公元321年 - 321年，君士坦丁大帝于3月7日正式公布“公历”，成为定制，逐渐成为国际惯例。 我国古代历法把二十八宿按日、月、火、水、木、金、土的次序排列，七日为一周，称为“七曜”。 这种算法与西方历法暗合。 按七天一周的记日法由来颇为古老，已难于考证。 据说古代巴比伦人以太阳、月亮和金、木 .321年，君士坦丁大帝于3月7日正式公布“公历”，成为定制，逐渐成为国际惯例。 我国古代历法把二十八宿按日、月、火、水、木、金、土的次序排列，七日为一周，称为“七曜”。 这种算法与西方历法暗合。公元400年 - 孙子算经的作者不详，估计是公元400年左右的数学著作。 它是一部直接涉及到乘除运算、求面积和体积、处理分数以及开平方和立方的著作。 对筹算的分数算法和筹算开平方法以及当时的度量衡体系，都作了描绘，其中有关数论上原一个“ 物不知数” 的计算问题，是世界上最早提出算法的，被誉为“ 孙子定理”公元500年 - 到了三国时代，出现两个数学家，一个叫刘徽，一个叫赵爽，对二次方程有了比较纯粹的解答。 到了公元五百年，进入南北朝时代，祖冲之考虑了三次方程。 五百年出了一个缉古算经，一个未知数的多项式方程的算法。公元600年 - 十进制系统，由印度发明于公元600年左右，它是定量推理的革命。 它仅仅使用了10个符号，甚至可以很简洁地写出很大的数字，它使得后面演示的算法基本步骤变得非常有效率。 尽管如此，由于传统语言的阻碍，在很长一段时间内它都不被人们所熟知。公元825年 - 注释添加必要的注释以说明程序过程和语句等的功能及注意事项代码规范的重要性81 算法公元825年,阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)撰写了著名的波斯教科书(Persian Textbook) 书中概括了进行四则算Textbook),书中概括了进行四则算术运算的法则. 算法(Algorithm) 一词就来源 .阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)撰写了著名的波斯教科书(Persian Textbook) 书中概括了进行四则算Textbook),书中概括了进行四则算术运算的法则. 算法(Algorithm) 一词就来源于这位数学家的名字1202年 - 公元1202年，斐波那契的传世之作算法之术出版。 在这部名著中，斐波那契提出了以下饶有趣味的问题：. 假定一对刚出生的小兔一个月后就能长成大兔，再过一个月便能生下一对小兔，并且此后每个月都生一对小兔。 一年内没有发生死亡。 问一对刚出生的兔子，一年内能繁殖成多少对兔子？1360年 - 约公元1360年法国奥雷姆著比例算法，引入分指数概念，又在论质量与运动的结构等著作中研究变化与变化率，用经、纬度（相当于横、纵坐标）表示点的位置并进而讨论函数图象。1478年 - 西方国家第一部印刷本的算术书于1478年诞生于意大利的特雷维索城，名为特雷维索算术，作者不详 这本书的内容多半是商业算术，包括印度阿拉伯数字的写法和算法，合股和换货的计算法以及一些数学游戏 在德国，最有影响的算术书是由著名计算师里泽( AdlamRiese，14921559 .西方国家第一部印刷本的算术书于1478年诞生于意大利的特雷维索城，名为特雷维索算术，作者不详 这本书的内容多半是商业算术，包括印度阿拉伯数字的写法和算法，合股和换货的计算法以及一些数学游戏 在德国，最有影响的算术书是由著名计算师里泽( AdlamRiese，14921559)编写的 他广招学生，写了一系列教材 有一本算术教材(1522 )共4篇：算盘计数，笔算，商业算术，测量面积和体积1484年 - 法国数学家许凯在1484年写成的算术三篇中，使用了一些编写符号，如用D表示加法， 用M表示减法 这两个符号最早出现在德国数学家维德曼写的商业速算法中，他用“” 表示超过,用“”表示不足1522年 - L帕奇欧里(Pacioli)的算术、几何及比例性质之摘要(Summadearithmetica，geometrica，proportionietproportionalita， 1494)是一本内容全面的数学书；J维德曼(Widman)的商业速算法(1489)中首次使用符号+和-表示加法和减法；A里泽(Riese)于1522年出版的算术书多 .印度阿拉伯数码的使用使算术运算日趋标准化。 L帕奇欧里(Pacioli)的算术、几何及比例性质之摘要(Summadearithmetica，geometrica，proportionietproportionalita， 1494)是一本内容全面的数学书；J维德曼(Widman)的商业速算法(1489)中首次使用符号+和-表示加法和减法；A里泽(Riese)于1522年出版的算术书多次再版，有广泛的影响；斯蒂文(SimonStevin)的论十进(1585)系统阐述了十进分数的理论。1533年5 月3日 - 他撰写的算法统宗是一部印量很大、传播很广的数学著作. 程大位，安徽人，1533年5 月3日出生在风景秀美的江南小城休宁（今属黄山市）的一个商人家庭. 他自幼聪明好学， 对书法、数学特别喜爱. 他对考取功名并不热衷，而把主要精力用于经世实用的学问，对数学的学习和研究特别下力气. 他 .他撰写的算法统宗是一部印量很大、传播很广的数学著作. 程大位，安徽人，1533年5 月3日出生在风景秀美的江南小城休宁（今属黄山市）的一个商人家庭. 他自幼聪明好学， 对书法、数学特别喜爱. 他对考取功名并不热衷，而把主要精力用于经世实用的学问，对数学的学习和研究特别下力气. 他想尽办法广泛搜求古今各种数学书籍，见到好的数学书籍，不惜重金购买，带回家去，不分昼夜地刻苦钻研.1545年G.Cardano（1501-1576）公布了由N.Fontana（1499 1557）发现了解一元三次方程的解，而一元四次方程的解由L.Ferrari（15221565）所解决。 于是当时大批的数学家致力于更高次方程的求根式解，即企图只对方程的系数作加、减、乘、除和求正整数次方根等运算来表达方程的解。1583年 - 同文算指是意大利耶稣会士利玛窦和李之藻根据利玛窦的老师克拉维斯（Christopher Clavius，15371612）在1583 年出版的实用算术概论（Epitome Arithmeticae Practicae）一书编译的，同时也参考了中国数学家程大位的算法统宗一书。 全书分 前编、通编和别编三部分。1593年 - 到了明代，珠算发展到了顶峰。 1593年，明代数学家程大位所著算法统宗面世。 算法统宗是一部以珠算应用为主的算书。 全书共17卷，载有算盘图式和珠算口诀，并首次提到了用算盘做开平方和开立方的运算。1607年 - 1607年，几何原本前六卷正式出版，马上引起巨大的反响，成了明末从事数学工作的人的一部必读书，对发展我国的近代数学起了很大的作用。 和当时一般文人官吏热衷于笔墨应酬不同，徐光启用较多的时间进行天文、算法、农学、水利等科学技术研究，从事了不少这方面的翻译和写作。1628年 - 筹算是罗雅谷于1628年写成的一本关于西方的(纳贝尔)筹及其算法的数学著作. 介绍了筹算在中国的流传和中国清代数学家对该算法的发展情况.1666年 - 1666年莱布尼兹所著组合学论文一书问世, 这是组合数学的第一部专著. 书中首次使用了组合论(Combinatorics)一词. 组合数学的蓬勃发展则是在计算机问世和普遍应用之后. 计算机促进组合数学的发展信息技术为组合数学提出大量研究问题计算机为解决组合数学问题提供一种手段设计算法需要组合 .1666年莱布尼兹所著组合学论文一书问世, 这是组合数学的第一部专著. 书中首次使用了组合论(Combinatorics)一词. 组合数学的蓬勃发展则是在计算机问世和普遍应用之后. 计算机促进组合数学的发展信息技术为组合数学提出大量研究问题计算机为解决组合数学问题提供一种手段设计算法需要组合数学基础,如算法的运行时间和存储需求估计组合数学应用与社会科学,生物学和信息论等其他领域.1686年 - 1686 年,莱布尼茨发表了他的第一篇积分学论文深奥的几何与不可分量及无限的分析, 这篇论文初步论述了积分或求积问题与微分或切线问题的互逆关系,文中莱布尼茨创造的微分符号dx , dy 及积分号 (表示的是sum的首字母s 的拉长)第一次出现于印刷出版物上,并一直沿用至今. 牛顿和莱布尼 .1686 年,莱布尼茨发表了他的第一篇积分学论文深奥的几何与不可分量及无限的分析, 这篇论文初步论述了积分或求积问题与微分或切线问题的互逆关系,文中莱布尼茨创造的微分符号dx , dy 及积分号 (表示的是sum的首字母s 的拉长)第一次出现于印刷出版物上,并一直沿用至今. 牛顿和莱布尼茨超越前人的贡献主要在于给出了一般无穷小算法,发现了微分和积分之间的互逆关系,这一深刻的数学思想已成为人类文明中的瑰宝.1687年 - 牛顿最伟大的著作是1687 年出版的巨著 自然哲学的数学原理，在这部著作中，牛顿以几何的语言介绍了“首末比方法”。 牛顿在数学上最卓越的贡献是微积分的创建。 他超越前人的功绩在于他能站在更高的角度，使以往分散的分别对微分、积分的研究加以综合，将自古希腊以来求解问题的各种特殊 .这一论著被看作是牛顿最成熟的微积分著述。 牛顿最伟大的著作是1687 年出版的巨著 自然哲学的数学原理，在这部著作中，牛顿以几何的语言介绍了“首末比方法”。 牛顿在数学上最卓越的贡献是微积分的创建。 他超越前人的功绩在于他能站在更高的角度，使以往分散的分别对微分、积分的研究加以综合，将自古希腊以来求解问题的各种特殊技巧统一为两类普遍的算法微分和积分，并确立了这两类运算的互逆关系，从而完成了微积分发明中最后的也是最关键的一步。1700年前后，德国伟大的科学家莱布尼茨提出了二进制算法，这可以说是为现代计算机奠定了算法基础。 同时，通过对中国古老“易经”的研究，莱布尼茨也在中国的传统文化中印证了二进制的思想。1722年 - 德国作曲家巴赫于1722年发表的谐和音律曲集（另或译为十二平均律曲集英文： The 48），有可能就是为十二平均律的键盘乐器所著。1735年 - 在计算机领域中广泛使用的RSA公钥密码算法也正是以欧拉函数为基础的。 在分析领域，是欧拉综合了莱布尼兹的微分与牛顿的流数。 他在1735年由于解决了长期悬而未决的贝塞尔问题而获得名声。 在1735年，他定义了微分方程中有用的欧拉-马歇罗尼常数。1759年 - 最早可以追溯到1759年Euler提出的骑士旅行问题。 TSP 问题是一个典型的、容易描述但是难以处理的NP完全问题，同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。 目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树 .引言第一章基本遗传算法货郎担问题(Traveling Salesman Problem ,TSP)，也称为巡回旅行商问题，是一个较古的问题。 最早可以追溯到1759年Euler提出的骑士旅行问题。 TSP 问题是一个典型的、容易描述但是难以处理的NP完全问题，同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。 目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。1815年 - 软件行业的奇人轶事Ada Lovelace(阿达奥古斯塔1815-1852) 1815年生于英国伦敦为巴贝奇分析机拟定了算法,然后写作了一份程序设计流程图. 这份珍贵的规划,被人们视为第一件计算机程序 世界上第一位软件工程师!1828年17岁的法国数学家伽罗华( EGalois 1811-1832) 写出了划时代的论文“关于五次方程的代数解法问题”，指出即使在公式中容许用n 次方根，并用类似算法求五次或更高次代数方程的根是不可能的文章呈交法兰西科学院后，因辈份太低遭到冷遇，且文稿丢失。1834 年：巴贝奇提出了分析机的概念，他设计的分析机共分为三个部分：堆栈，运算器， 控制器。 堆栈是保存数据的齿轮式寄存器。 运算器是对数据进行各种运算的装置。 控制器是对操作顺序进行控制，并对所要处理的数据及输出结果加以选择的装置。1843年 - 因此，对压缩算法的研究主要基于无损压缩的一类算法展开。 对于数据压缩的研究已有较长的时间，如1843年出现的Morse电报码是最原始的变长码数据压缩实例。 但是严格意义上的数据压缩应起源于人们对概率的认识。 当对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为 .因此，对压缩算法的研究主要基于无损压缩的一类算法展开。 对于数据压缩的研究已有较长的时间，如1843年出现的Morse电报码是最原始的变长码数据压缩实例。 但是严格意义上的数据压缩应起源于人们对概率的认识。1844 年，当加拉姆（G.Lame）用斐波纳契序列研究欧几里得算法的效率时，头一次指出了Fn与算法之间的密切关系。 这是斐波纳契序列的头一次实际应用。1847年 - 答: 布林体即是布尔运算, 是英国数学家George Boolean于1847年制定完成的一套逻辑数学计算方法, 用来表示两个数值相结合的所有结果. 后来人们以他的名字命名这套算法, 称为“Boolean”(布尔运算). 也就是在初学数学中的集合中的并集, 联集和交集都是布尔运算, JewelCAD中称为布林体, 但 .、布林体即是布尔运算, 是英国数学家George Boolean于1847年制定完成的一套逻辑数学计算方法, 用来表示两个数值相结合的所有结果. 后来人们以他的名字命名这套算法, 称为“Boolean”(布尔运算). 也就是在初学数学中的集合中的并集, 联集和交集都是布尔运算, JewelCAD中称为布林体, 但不支持曲线进行布尔体操作.1900年 - 龙格-库塔(Runge-Kutta)方法是一种在工程上应用广泛的高精度单步算法，常用于模拟常微分方程的解的重要的一类隐式或显式迭代法。 这些技术由数学家C. Runge和MW Kutta于1900年左右发明。 由于此算法精度高，采取措施对误差进行抑制，所以其实现原理也较复杂。 同前几种算法一样，该算法 .龙格-库塔(Runge-Kutta)方法是一种在工程上应用广泛的高精度单步算法，常用于模拟常微分方程的解的重要的一类隐式或显式迭代法。 这些技术由数学家C. Runge和MW Kutta于1900年左右发明。 由于此算法精度高，采取措施对误差进行抑制，所以其实现原理也较复杂。 同前几种算法一样，该算法也是构建在数学支持的基础之上的。1917年 - 讨论流密码(Stream Ciphers), 就要从一次一密系统说起. 一次一密算法, 是由Major Joseph Mauborgne 和AT&T 公司的Gilbert Vernam 在1917 年设计的一种加密算法3. 主要使用在高度机密的低带宽信道, 据传, 美国和前苏联之间的热线电话就是用这种加密算法加密. 一次一密系统加密体制 .讨论流密码(Stream Ciphers), 就要从一次一密系统说起. 一次一密算法, 是由Major Joseph Mauborgne 和AT&T 公司的Gilbert Vernam 在1917 年设计的一种加密算法3. 主要使用在高度机密的低带宽信道1930年 - Jarnk在1930年提出的算法，不过他的文章是用捷克语写的，光看标题就看不明白了。 有人也把这个算法就叫做Prim-Jarnik算法。 Prim算法简单有效，他从图的一个指定的顶点出发，用V表示树顶点集，初始只有那个指定的顶点；E表示最终最小生成树中有的边的集合，初始是空集。 从V中的顶点 .Jarnk在1930年提出的算法，不过他的文章是用捷克语写的，光看标题就看不明白了。 有人也把这个算法就叫做Prim-Jarnik算法。 Prim算法简单有效，他从图的一个指定的顶点出发，用V表示树顶点集，初始只有那个指定的顶点；E表示最终最小生成树中有的边的集合，初始是空集。 从V中的顶点出发，找到从这个顶点出发的权值最小的边，如果这条边不构成回边，那么选入最小生成树，并将这条边加到E集合中，边的另一端结点加入到V集合中。1934年 - 哥德尔在证明不完全性定理时使用了一组函数作为工具，即原始递归函数。 起初人们希望原始递归函数即算法可计算函数的数学定义，后来发现还有非原始递归函数也是算法可计算的：要在原始递归函数基础上推广函数类。 人们在历史上第一次给出算法的数学定义是哥德尔于1934年在普林斯顿高等研究 .哥德尔在证明不完全性定理时使用了一组函数作为工具，即原始递归函数。 起初人们希望原始递归函数即算法可计算函数的数学定义，后来发现还有非原始递归函数也是算法可计算的：要在原始递归函数基础上推广函数类。 人们在历史上第一次给出算法的数学定义是哥德尔于1934年在普林斯顿高等研究所报告的递归函数的定义。1943年，哥德尔用形式化演算系统的推理规则确定出可计算函数。 在波斯特和图灵的研究工作的基础上，就可以根据它们提出的算法概念的精确化方法来确定可计算函数。 可计算函数的确定依赖于算法的精确化，而算法的精确化又依赖于逻辑系统的形式化和精确化。1951年 - Booth 算法Booth 编码是ADBooth 在1951 年为了解决由符号乘法运算中复杂的符号修正问题而提出的一种乘数编码方法。 它是目前被广大设计者所普遍采用的乘法器编码算法之一，该算法原理如下所示。 如果直接考虑符号位，两个n 位补码表示的有符号数相乘AB， 那么乘数B可以表示为: B .Booth 算法Booth 编码是ADBooth 在1951 年为了解决由符号乘法运算中复杂的符号修正问题而提出的一种乘数编码方法。 它是目前被广大设计者所普遍采用的乘法器编码算法之一1958年 - 不久降生的另外一种高级语言是ALGOL,这个名称就是算法语言的简称,因此可以预料到这种语言具有与FORTRAN 非常不同的面貌,因为这种语言在设计初始,就不是计算机制造公司为某种特定机器设计的, 而是纯粹面向描述计算过程的, 也就是所谓面向算法描述的. ALGOL 最早是在1958 年由 .不久降生的另外一种高级语言是ALGOL,这个名称就是算法语言的简称,因此可以预料到这种语言具有与FORTRAN 非常不同的面貌,因为这种语言在设计初始,就不是计算机制造公司为某种特定机器设计的, 而是纯粹面向描述计算过程的, 也就是所谓面向算法描述的. ALGOL 最早是在1958 年由德意志联邦共和国应用数学与力学协会提出的. ALGOL 的设计目标显然比FORTRAN 要来得高远,它希望不仅能够用于人对机器转述计算过程,也希望能够直接用于人与人之间的对于算法的描述.1959年 - OSPF路由协议使用SPF（Shortest Path First）算法计算路由的最佳路径。 该算法是由一位荷兰的计算机科学家Dijkstra于1959年发现的，所以该算法也称为Dijkstra算法。 IS-IS 也使用这种算法。 该算法把网络考虑为一组点到点连接的节点，每条链路有一个开销值， 每个节点有它自己的 .OSPF路由协议使用SPF（Shortest Path First）算法计算路由的最佳路径。 该算法是由一位荷兰的计算机科学家Dijkstra于1959年发现的，所以该算法也称为Dijkstra算法。 IS-IS 也使用这种算法。 该算法把网络考虑为一组点到点连接的节点，每条链路有一个开销值， 每个节点有它自己的名称及一个包含已知物理拓扑的完整链路信息的数据库。1965年，库力和图基在计算数学杂志上发表机器计算傅立叶级数的一种算法，此文是最早提出FFT算法的。 此后关于DFT的快速算法称为人们研究的热点课题，也正是FFT算法的出现，才使得数字信号处理能够应用于实时场合并进一步推动数字信号处理的发展和应用。 大多数的FFT算法都是利用（3）式的周期性、共轭对称性、可压缩和扩展性的特点来压缩计算量1965年 - 一、二分图最大匹配二分图最大匹配的经典匈牙利算法是由Edmonds 在1965 年提出的， 算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。 匈牙利算法的本质实际上和基于增广路特性的最大流算法还是相似的，只需要注意两点： （一）每个X 节点都最多做一次增广路的起点 .一、二分图最大匹配二分图最大匹配的经典匈牙利算法是由Edmonds 在1965 年提出的， 算法的核心就是根据一个初始匹配不停的找增广路，直到没有增广路为止。 匈牙利算法的本质实际上和基于增广路特性的最大流算法还是相似的，只需要注意两点： （一）每个X 节点都最多做一次增广路的起点； （二）如果一个Y 节点已经匹配了，那么增广路到这儿的时候唯一的路径是走到Y 节点的匹配点（可以回忆最大流算法中的后向边，这个时候后向边是可以增流的）。1965年 - 银行家算法(Bankers Algorithm)银行家算法是避免死结(Deadlock)的一个著名的算法，是由艾兹格迪杰斯特拉在1965年为THE系统设计的一种避免死结产生的演算法。 它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。1965年 - LR算法LR algorithm 由克努特（Knuth）于1965年提出的一种自底向上分析方法。 根据分析栈的内容以及向前看k个输入串的符号决定分析动作的方法称为LR（k）算法。 LR算法是k取不同值时的LR（k）算法的总称。 靠左推导left most derivation 推导句子时，总是扩展重写规则右部（RHS）的 .LR算法LR algorithm 由克努特（Knuth）于1965年提出的一种自底向上分析方法。 根据分析栈的内容以及向前看k个输入串的符号决定分析动作的方法称为LR（k）算法。 LR算法是k取不同值时的LR（k）算法的总称。 靠左推导left most derivation 推导句子时，总是扩展重写规则右部（RHS）的第一个非终极符号的推导。 最左推导靠右推导right most derivation 推导句子时，总是扩展重写规则右部（RHS）的最后一个非终极符号的推导。复杂度的概念首先由Kolmogorov 8 于1965年提出来，后由Lempel和Ziv 9 及Kasper 和Schuster 10 给出了实现这种复杂性的具体算法。 这种算法可以给出时间序列的信息含量。 复杂度算法描述如下：. （1）首先将已知序列X 1 ，X 2 ，X n 重构，令大于数列平均值的X .复杂度的概念首先由Kolmogorov 8 于1965年提出来，后由Lempel和Ziv 9 及Kasper 和Schuster 10 给出了实现这种复杂性的具体算法。GMD算法由Forney于1966年提出。 GMD译码算法是一种简单优雅的软判决译码算法。 对于最小距离为dmin的(n, k)线性分组码，若2v+e=dmin-1，则错误-删除译码算法可以纠正v个错误和e个删除的所有组合。 GMD算法考虑e=dmin-1个删除出现在dmin-1个最不可靠的位置上的所有情况，因为这些位置是最可能出错的位置。 算法描述如下：. 根据接收序列r得到硬判决接收序列z，并对z的每一个符号分配一个可靠性值。Viterbi译码算法（简称VA算法）是由Viterbi在1967年首先提出的，它是一种针对卷积码的最大似然译码算法。 他不是在网格图上依次比较所有的可能路径，而是接受一段，计算、 比较一段，保留最有可能的路径，从而达到整个码序列是一个最大似然序列。 Viterbi译码算法优点是在码的约束比较 .Viterbi译码算法（简称VA算法）是由Viterbi在1967年首先提出的，它是一种针对卷积码的最大似然译码算法。 他不是在网格图上依次比较所有的可能路径，而是接受一段，计算、 比较一段，保留最有可能的路径，从而达到整个码序列是一个最大似然序列。 Viterbi译码算法优点是在码的约束比较小时，它比序列译码算法效率更高、速度更快，译码器也较简单。1969年 - 1969年Berliner提出了B*算法，用一个乐观值和一个悲观值来表示评价值。 算法从这点出发，用这两个界来证明哪个节点是最好的。 当根节点的一个孩子的悲观值不比所有其它节点的乐观值差的时候，B*算法就结束了。 算法的搜索控制就是尽可能快的得到终止条件。 B*算法的缺点是它对局面的乐观 .1969年Berliner提出了B*算法，用一个乐观值和一个悲观值来表示评价值。 算法从这点出发，用这两个界来证明哪个节点是最好的。 当根节点的一个孩子的悲观值不比所有其它节点的乐观值差的时候，B*算法就结束了。 算法的搜索控制就是尽可能快的得到终止条件。 B*算法的缺点是它对局面的乐观值和悲观值的估计得可信赖程度，它对这个估值的依赖性太强。1971年 - 随着计算机的量产，NAG所研发出来的第一版Fortran算法库于1971年上市，自此之后NAG 不断推陈出新，现在的NAG算法库已经演进到第22版。 NAG 算法库是以NAG 引擎为核心， 包含所有各种的数学、统计以及数据挖掘等函数，并将其编写成具有简洁、高精确度与高效能的各种计算机语言 .随着计算机的量产，NAG所研发出来的第一版Fortran算法库于1971年上市，自此之后NAG 不断推陈出新，现在的NAG算法库已经演进到第22版。 NAG 算法库是以NAG 引擎为核心， 包含所有各种的数学、统计以及数据挖掘等函数，并将其编写成具有简洁、高精确度与高效能的各种计算机语言算法函数，提供制造、金融、大气、航天、工程、医学以及军事等研究人员及编程人员使用。1973年5 月13日 - 数据加密标准（Data Encryption Standard）是迄今为止使用得最为广泛的加密算法。 1973年5月13日美国国家标准局公布了一项公告，征求国家密码标准方案。 IBM提交了他们研制的一种密码算法，该算法是由早期的LUCIFER密码改进而得的。