算法发展史时间轴：从公元前4000年谈起（2）

weixin

1965年 - LR算法LR algorithm由克努特(Knuth)于1965年提出的一种自底向上分析方法。根据分析栈的内容以及向前看k个输入串的符号决定分析动作的方法称为LR(k)算法。LR算法是k取不同值时的LR(k)算法的总称。靠左推导left most derivation推导句子时，总是扩展重写规则右部(RHS)的第一个非终极符号的推导。最左推导靠右推导right mostderivation推导句子时，总是扩展重写规则右部(RHS)的最后一个非终极符号的推导。

　　复杂度的概念首先由Kolmogorov于1965年提出来，后由Lempel和Ziv及Kasper 和Schuster给出了实现这种复杂性的具体算法。

　　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译码算法优点是在码的约束比较小时，它比序列译码算法效率更高、速度更快，译码器也较简单。

　　1969年 - 1969年Berliner提出了B*算法，用一个乐观值和一个悲观值来表示评价值。算法从这点出发，用这两个界来证明哪个节点是最好的。当根节点的一个孩子的悲观值不比所有其它节点的乐观值差的时候，B*算法就结束了。算法的搜索控制就是尽可能快的得到终止条件。B*算法的缺点是它对局面的乐观值和悲观值的估计得可信赖程度，它对这个估值的依赖性太强。

　　1971年 - 随着计算机的量产，NAG所研发出来的第一版Fortran算法库于1971年上市，自此之后NAG不断推陈出新，现在的NAG算法库已经演进到第22版。 NAG算法库是以NAG引擎为核心，包含所有各种的数学、统计以及数据挖掘等函数，并将其编写成具有简洁、高精确度与高效能的各种计算机语言算法函数，提供制造、金融、大气、航天、工程、医学以及军事等研究人员及编程人员使用。

　　1973年5月13日 - 数据加密标准(Data Encryption Standard)是迄今为止使用得最为广泛的加密算法。1973年5月13日美国国家标准局公布了一项公告，征求国家密码标准方案。IBM提交了他们研制的一种密码算法，该算法是由早期的LUCIFER密码改进而得的。

　　1974年8月27日 - 1974年8月27日，NBS开始第二次征集，IBM提交了算法LUCIFER，该算法由Feistel领导的团队研究开发，采用64位分组以及128位密钥。IBM用改版的Lucifer算法参加竞争，最后获胜，成为数据加密标准(DataEncryptionStandard，DES)。

　　1975年 - 1975年Holland出版了遗传算法历史上的经典著作《自然和人工系统中的适应性》，系统阐述了遗传算法的基本理论和方法，并提出了模式定理(schemata theorem)，证明在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长，这里的模式是某一类字符串，其某些位置有相似性。

　　1975年 - 首先简要介绍一下AC自动机：Aho-Corasick automation，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。

　　1976年 - 1976年出现的随机算法拓宽了算法的概念，开拓了算法设计的新领域。目前研究比较多的随机类有ZPP、BPP、PP等。这些类与其他一些重要的复杂性类之间存在着深刻联系，因而P=BPP在计算复杂性研究中也是吸引人的问题。软件开发自动化是提高软件生产率，保证软件产品可靠性的途径之一。算法设计是软件开发中最困难的也是最富创造性的活动，因而算法设计自动化的研究构成了软件开发自动化研究的核心内容。

　　1977年 - 由于RSA算法发展至今，在实现技术上已经相当成熟，因此本课题算法的实现在许多方面都可以利用己有的技术，这对增强算法的实用性是非常有益的。RSA算法的历史RSA算法的历史著名的RSA公钥密码体制是在1977年由RLRivest，A。Shamir和L。Adleman三人共同提出。RSA是最具代表性的公钥密码体制。由于算法完善(既可用于数据加密，又可用于数字签名)，安全性良好，易于实现和理解，RSA已成为一种应用极广的公钥密码体制，也是目前世界上唯一被广泛使用的公钥密码。

　　1977年 - BrighamYoung大学的HelamanFerguson和RodneyForcade提出了整数关系侦查算法。这是一个古老的问题：给定—组实数，例如说x(1)，x(2)，...，x(n)，是否存在整数a(1)，a(2)，...，a(n)(不全为零)，使得a(1)x(1)+a(2)x(2)+...+a(n)x(n)=0对于n=2，历史悠久的欧几里得算法能做这项工作、计算x(1)/x(2)的连分数展开中的各项。如果x(1)/x(2)是有理数，展开会终止，在适当展开后就给出了最小的整数a(1)和a(2)。

　　1977年 - Robert Boyer和L。Moore发表了BM算法，这种算法在逻辑上相对于之前的算法有了很大的超越，它对要搜索的字符串实施逆序字符比较，而且有一种找到了不匹配就不需要对整个字符串进行搜索的方法。脆弱性vulnerability：导致破坏系统安全策略的系统安全规程、系统设计、实现、内部控制等方面的弱点。串道cross-talk：能量从一信道到另一信道的无意的传输。

　　EM算法由Dempster，Laird和Rudin于1977年提出用于极大似然估计的迭代计算，同时为缺失数据情况下迭代求取似然函数极大值提供了一个统一的框架。鉴于EM算法所具有的单调增加似然函数值和对于任意初试条件都稳定收敛的良好性质，该算法很快受到广大学者的关注和研究。但由于EM算法收敛速度缓慢的原因很大程度上制约了他在实际中的应用，为了克服这个收敛缓慢的困难随后提出了多种改进。

　　Lawson算法逐点插入的Lawson算法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：首先建立一个大的三角形或多边形，把所有数据点包围起来，向其中插入一点，该点与包含它的三角形三个顶点相连，形成三个新的三角形，然后逐个对它们进行空外接圆检测，同时用Lawson设计的局部优化过程LOP进行优化，即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。

　　Tabu Search是由美国科罗拉多州大学的Fred Glover教授在1977年左右提出来的，是一个用来跳出局部最优的搜寻方法。在解决最优问题上，一般区分为两种方式，一种是传统的方法，就是穷举法、贪婪法、分治法、动态规划等等;而另一种方法则是一些启发式搜索算法。而这两种方法最大的不同点就在于使用传统的方法，我们必须对每一个问题都去设计一套算法，一旦我们遇到一个新的问题，整个算法就得重新设计，所以相当不方便，也缺乏广泛性。

　　1977年1月15日 - AES取代DES和3DES以增强安全性和效率已是大势所趋。 其中，DES(Data Encryption Standard)是1977年1月15日美国正式公布实施的数据加密标准，由于密钥长度太短，导致数据加密的安全性达不到目前人们的要求，所以被AES所取代。AES算法现在在国内外，有很多的研究，并有相应的产品。以下介绍AES算法的部分应用：(1)直接将算法用于软件设计中，对存储数据进行加密和保护：朗科密钥U盘、移动硬盘，内置高强度AES算法保护数据。

　　1977年7月15日 - IBM提交了一个候选算法，它是IBM内部开发的，名为LUCIFER。在美国国家安全局(NSA)的指导下完成了算法评估之后，在1977年7月15 日，NBS采纳了LUCIFER算法的修正版作为新的数据加密标准。这导致了联邦信息处理标准(FIPS)46(以后更新成FIPS46-3)的产生(请参阅参考资料)，它描述了DES和当前DES3标准的用法。

　　1979年 - 一位名不见经传的苏联数学家哈奇扬，发明了一种新算法来解决线性划问题。他从理论上证明这种称这椭球法的算法，是一种好算法。这使得一件拖了八年之久的公案，即线性规划到底有没有好算法的问题，彻底解决了。

　　1982年 - 模拟退火算法(Simulated Annealing，SA)又称模拟冷却法、概率爬山法等，于1982年由Kirpatrick提出的另一种启发式的、随机优化算法。模拟退火算法的基本思想由一个初始的解出发，不断重复产生迭代解，逐步判定、舍弃，最终取得满意解的过程。模拟退火算法不但可以往好的方向发展，也可以往差的方向发展，从而使算法跳出局部最优解，达到全局最优解。

　　1983年 - KirkpatrickS，GelattJ C D和Vecchi M P首先注意到固体退火过程与组合优化问题的相似性，提出了模拟退火算法，并成功应用于求解TSP。 随后，几乎所有的启发式算法都以TSP作为测试算法性能的平台。这其中包括禁忌搜索{121、遗传算法㈣I、Hopfield神经网络算法和ACO算法。

　　1984年 - Narendra Karmarkar(卡马卡)提出了投影尺度法。这是第一个在理论上和实际上都表现良好的算法：它的最坏情况仅为多项式时间，且在实际问题中它比单纯形算法有显著的效率提升。自此之后，很多内点算法被提出来并进行分析。一个常见的内点算法为Mehrotra predictor-corrector method。尽管在理论上对它所知甚少，在实际应用中它却表现出色。

　　1985年 - Neal Koblitz和VSMiller把椭圆曲线的研究成果应用到密码学中，分别独立提出在公钥密码系统中使用椭圆曲线的思想。他们虽没有发明出一种新的公钥密码算法，但他们采用椭圆曲线技术实现了已存在的密码算法如Diffie-Hellman算法等，这就是椭圆曲线密码学的开端。此后，由于椭圆曲线密码系统所具有的安全性高、算法效率好的特点，使得它得到了人们的广泛关注和研究。

　　1986年 - Rumelhart等人提出了一种前馈型神经计算模型和用手调节该模型神经元联结强度的误差往回传播学习算法，即著名的BP网络和BP算法，引起学术界极大的反响。BP算法解决了感知器存在的问题，使人工神经网络有了强大的计算能力，可实现各种复杂映射，BP网络目而迅速成为最流行的神经计算模型，并得到极其广泛的应用。

　　1987年 - Mallat在多尺度分析的基础上提出了小波分解和重构的快速算法，称为Mallat算法。由此算法可以有效的进行图象的分解和重构。Mallat算法不需要知道小波函数的具体结构，由一组滤波器的系数即可对信号进行分解和重构。

　　1991年 - 提出的DSA算法也是一种公共密钥算法，在数字签名方面有较大的应用优势。目前，国际上在智能IC卡上应用得较多的加密解密算法是DES算法、RSA算法及DSA算法。

　　1996年 - Zhan和Noon使用实际交通网络测试了17种算法中的15种，测试结果表明计算一点到所有其它点的最短路径最快的算法是Dijkstra算法。

　　2003年11月15日 - 这些查询条件的集合就是SEO一族所收集并称之为的商业词名单。这一效果无意中却提供了一个强有力的证据，表明Google确是采用了Hilltop算法。2003年11月15号，Google基于新算法的更新之后，某分析家就指出：在进行查询时，若对某一查询条件加上一些不包含的无意义字符，如carrental–ghjkl，则Google将会显示以往(算法变化前)的搜索结果，而绕过所谓的商业词过滤名单。

本文根据百度文库《算法的发展史》一文编辑而成