John E. Hopcroft and Robert Tarjan
Citation
For fundamental achievements in the design and analysis of algorithms and data structures.
———————————————————————-
1986年的图灵奖由康乃尔大学机器人实验室主任约翰·霍普克洛夫特（John Edward Hopcroft）和普林斯顿大学计算机科学系教授罗伯特·陶尔扬（Robert Endre Tarjan）共享，而陶尔扬曾是霍普克洛夫特的学生。这师生两人由于在数据结构和算法的设计和分析方面的众多创造性贡献而共同获此殊荣，在业界传为美谈。
霍普克洛夫特1939年10月7日生于西雅图。1961年在西雅图大学获得电气工程学土学位以后，进入斯坦福大学研究生院深造，师从著名的学者威德罗（Bernard Widrow）。威德罗是研究自适应信号处理和神经元网络的鼻祖。霍普克洛夫特1962年获得硕士学位，1964年获得博士学位，也就是说只用了3年时间就拿下了硕士、博士2个学位，其勤奋和聪颖由此可见。学成以后，霍普克洛夫特曾先后在普林斯顿大学、康乃尔大学、斯坦福大学等著名高等学府工作，也曾任职于一些科学研究机构如 NSF（美国科学基金会）和 NRC（美国国家研究院），从事对科学研究的规划和行政管理工作，但时间不长。
霍普克洛夫特成为著名的计算机科学家起源于一个十分偶然的机会。他学习的专业是电气工程，对计算机科学原本没有多少知识，只学过一门“开关电路和逻辑设计”算是多少有些关系的。因此他原打算毕业后去西海岸的一所大学执教电气工程方面的课程。但就在毕业以前，有一次他偶然经过他的导师威德罗办公室的门口，当时，普林斯顿大学的麦克卢斯基教授（Edward McCluskey，他也是一位著名的学者，是研究数理逻辑的专家，他和奎因（Quine）共同创造的化简开关函数的一种方法就被叫做奎因一麦克卢斯基法（Quine-Mc－Cluskey method）。他还曾出任 IEEE计算机协会的主席。）正为筹建“数字系统实验室”打电话给威德罗，请他推荐毕业博士生去那里工作。威德罗一眼瞥见从门口走过的霍普克洛夫特，觉得勤奋好学、悟性又高的这位得意门生正是一个值得推荐的人才，当即把他叫进办公室，并把电话听筒递给了他。霍普克洛夫特在电话里听了麦克卢斯基对普林斯顿大学拟建数字系统实验室的考虑和打算，以后又前去面谈了一次，实地了解一番以后，一则普林斯顿大学作为美国一流大学的名望吸引着他，二则对数字系统这一全新的学科领域产生了强烈的兴趣，霍普克洛夫特欣然放弃了原先的计划，接受了普林斯顿的聘任，从而改变了他一生的道路。
年青的霍普克洛夫特来到普林斯顿之后接受的第一项任务是开设一门新课：自动机理论。这对他来说是富有挑战性的，因为他之前并未接触过这个课题。面对挑战，他虚心地请麦克卢斯基推荐有关参考资料。由于当时没有任何一所学校开过自动机理论的课程，也没有一本自动机理论的书籍，对自动机理论这门课到底应该包含哪些内容，麦克卢斯基本人心里也没有底。但凭着他对计算机科学的深刻理解和对文献的广泛了解，他为霍普克洛夫特开列了包括图灵、麦柯劳赫（Warren McCulloch）和皮茨（Walter Pitts）、拉宾（M． Rabin）和斯科特（D. Scott，这两人是1976年图灵奖获得者）、巴克斯（J．Backus，1977年图灵奖获得者）和诺尔（P．Naur）、哈特马尼斯（J．Hartmanis）和斯特恩斯（R．Stearns，这两人是1993年图灵奖获得者）以及乔姆斯基（N．Chomsky）等人所写的6篇论文。基于这些论文，霍普克洛夫特对图灵的计算模型（也就是图灵机），麦柯劳赫和皮茨在研究神经网络中用0和1的串描述神经元所产生和传递的电脉冲，从而导出的正规表达式概念（regular expression），拉宾和斯科特的有限状态自动机理论，巴克斯和诺尔描述程序设计语言语法的BNF范式，乔姆斯基的上下文无关文法（context－free grammar）等等进行了深入钻研和消化，并加以分析、综合和比较，逐渐理出了头绪。他把有关自动机理论的上述分散而零星的材料全面地条理化、系统化，有机地联系在一起，成功地开出了新课，并为这门计算机科学中的基础性课程建立起了框架。后来，霍普克洛夫特和著名的计算机科学家。教育家厄尔曼（J．D．Ullman，1997年ACM优秀计算机教育奖获得者）合作编写了《形式语言及其与自动机的关系》（Formal Language and Their Relation to Automata，Addison－Wesley， 1969），这本书是学术界公认的在自动机理论方面有代表性的一部成功之作（此书中译本由莫绍授等译，科学出版社出版）。
然而，霍普克洛夫特更感兴趣的课题是与实际应用有密切联系的“算法”。当时，算法复杂性理论虽已由哈特马尼斯、斯特恩斯和布卢姆（M．Blum，1995年图灵奖获得者）等人奠定了基础，但对具体算法的优劣和效率的判断尚未建立起客观和明确的准则，因此，往往出现这样的情况：有人公布了解某类问题的一种算法，给出对若干样本问题进行测试的执行时间；过了一段时间，另外一个人发布对它的“改进算法”，给出对相同样本问题进行测试的执行时间（当然比前者少，所以宣称算法获得了“改进”）。而实际上，执行时间的减少很可能是由于所用机器性能提高了，或者是所用语言比前者效率高所致，所谓“改进算法”实际上不见得比原算法高明。霍普克洛夫特对这种情况很不满意，决心加以解决。经过反复研究，他终于提出了一种“算法的最坏情况渐近分析法”（worst-case asymptotic analysis of algorithms），这种方法先确定问题的大小尺度，然后把计算时间当作问题大小尺度的一个函数去算出计算时间的增长率，以此衡量算法的效率和优劣。这个方法由于与机器性能及所用语言无关，成为测量算法好坏的数学准则，被学界所广泛认同和接受。
[ 相约加拿大:枫下论坛 rolia.net/forum ]
但是导致他和陶尔扬共同获得图灵奖的最主要原因则是他们解决了图论算法中的一些难题，创造了新的、重要的数据结构和影响深远的算法。1970年，霍普克洛夫特在康乃尔大学获得一年学术休假(他是1967年被哈特马尼斯招至麾下的人他决定回母校斯坦福大学到克努特教授名下做研究，因为克努特虽然只比他年长一岁，但因在 1968年和 1969年连出两卷《计算机程序设计的艺术》（The Art of Computer Programming）而已名满天下，成为算法领域的权威。克努特知道霍普克洛夫特对算法有兴趣并有独到见解，就把他和自己的得意门生、研究方向也是算法的陶尔扬安排在一个办公室（也有资料说是相邻办公室），为他们的合作创造了条件。他们选择了图论中与实际应用有很大关系的图的连通性(connectivity，也就是图中任意两个结点是否都是相互可达的)和平面性（planarity，也就是图中所有的边是否都可以安排得互不交叉）的测试难题进行攻关。拿如下所示的平面图来说，它对印刷电路板设计这样一类问题有十分重要的意义。学过图论的人都知道，平面图判断问题的研究可以上溯到18世纪，伟大的数学家欧拉早就证明，若结点数为n，则当n等于大于3时，所有边数等于大于（3－6）的图都
不是平面图。但过数小于（3n－6）的
图是否是平面图呢？欧拉没有给予说明。
1930年，波兰数学家库拉托夫斯基
（Kuratowski）解决了这个问题，他给
出了如下的判断法则：如果一个图既
不包括5个结点的完全图（叫K5）
作子图，也不包括6个结点的偶图（叫K3，3）作子图，则该图是平面图，否则为非平面图。所谓完全图（complete graph）就是任意 2个结点之间都有边的图，见图（a）；所谓偶图（bipartite graph）就是可以把全部结点分成两个不相交的集合，所有边的
两个端点分属于这两个集合的图，见图（b）。这个判据看似简单，但实现起来很难。对于有100个结点的图，用普通的算法，计算机需要1万亿步才能确定它是否是平面图。因此，寻找高效的平面图测试算法成为摆在当时计算机科学家面前的一大难题。霍普克洛夫特和陶尔扬都是富有创造性的人，又都善于合作共事，因此当两朵智慧的火花碰在一起时，就很快进发出耀眼的光芒！在解决这个难题的过程中，霍普克洛夫特首先提出了一种新的思路，经过陶尔扬的反复推敲和完善，一种适于解这类问题的新的算法终于诞生了，这就是著名的“深度优先搜索算法”（depth－first search algorithm）。利用这种算法对图进行搜索时，结点扩展的次序是向某一个分枝纵深推进，到底后再回溯，这样就能保证所有的边在搜索过程中都经过一次，但也只经过一次，从而大大提高了效率。新算法的运行时间是线性的，也就是说时间与图的大小成正比关系，大小翻一倍，解问题所需的时间也只翻一倍，不像用库拉托夫斯基判断的老算法那样，所需时间要增加60倍以上。利用他们创造的新算法，陶尔扬用 Algol W为一个包含900个结点和 2 694条边的图编制了一个测试其平面性的程序，程序只有 500行，在 IBM 360／67上运行，只用了 12 s就得到了结果。霍普克洛夫特和陶尔扬的研究成果在《ACM学报》（Journal of ACM）上公布以后，引起学术界很大的轰动，而他们创造的深度优先算法则被推广到信息检索、人工智能等方面成功地得到应用。在向霍普克洛夫特和陶尔扬授予图灵奖的仪式上，当年的国际象棋程序比赛的优胜者就说，他的程序在搜索可能的棋步时用的就是深度优先算法，这是他的程序所以能出奇制胜的关键。
＜ r o l i a. n e t ＞
在取得辉煌成功之后，霍普克洛夫特和陶尔扬并不满足，继续致力于开发效率更高的算法。不久，他们又发明了一种新的数据结构叫“双雄栈叠”（pilee of twin stacks），这种数据结构使深度优先搜索算法的优点更加发扬光大。陶尔扬的一个学生用这种新的数据结构和深度优先算法编写了一个Algol W程序，只有250行，在IBM 370／168上测试有8000个结点的图的平面性，只用了8S。
霍普克洛夫特除了和陶尔扬合作取得上述成果外，在数据结构和算法方面还有其他一系列创造。比如常用于索引组织的著名数据结构B树，是一种平衡的多分树，对查找、插入、删除等操作能始终保持动态平衡，具有很高的效率。霍普克洛夫特在对B树进行深入研究以后，为了进一步提高其操作效率和空间利用率，创造了它的一种变形叫“2－3树”，这种树的每个结点有2个键，每个键都有2－3个儿子。
霍普克洛夫特著述颇丰，除前面已经提到过的他的处女作以外，还有以下多部著作问世。
《计算机算法的设计与分析》（The Design and Analysis of Computer Algorithms，Addison-Wesley，1974）
《数据结构和算法》（Data Structures and Algorithms，Addison-Wesley,1982,1983,1987）
《自动机理论，语言和计算导论》（Introduction to Automata Theory, Languages, and Computation, Addison-Wesley,1979。本书有中译本，徐美瑞译，科学出版社出版）
《计算机科学：成就和计算导论》（Computer Science： Achievements and Opportunities，SIAM，1989）
霍普克洛夫特近期的研究兴趣集中在机器人学方面，这从他现任康乃尔大学机器人实验室主任这一点上可以看出。
罗伯特·陶尔扬1948年4月30日生于加利福尼亚州的波莫纳（Pomona）。陶尔扬从小就是一个富于幻想、追求新鲜事物的人，幼时对天文学很感兴趣，梦想成为第一个登上火星的人。小学七年级时他开始看《科学美国人》杂志，尤其对著名数学家马丁·加德那（Marin Gardner）开设的趣味数学专栏深感兴趣（加德那是世界著名的科普作家，上海科技出版社1981年翻译出版了他著的《啊哈！灵机一动》，被中国科学家评为“20世纪科普佳作”之一而向读者进行推介）。1964年，陶尔扬参加一个中学生科学夏令营，第一次接触计算机，立即被神奇的计算机所吸引。因此，当他上加州理工学院时，虽然学的专业是数学，但同时还辅修了当时学校开设的所有有关计算机的课程。1969年他取得学士学位以后，进入斯坦福大学研究生院，师从著名的计算机科学家、1974年图灵奖获得者克努特。1970年，在克努特的有意安排下，他与到斯坦福来度学术作假的康乃尔大学教师霍普克洛夫特开始了对图论算法的共同研究。他们的这个课题实际上是在“人工智能之父”麦卡锡（J．McCarthy）的建议下进行的。当时陶尔扬正选修麦卡锡开设的符号处理课程，学习由麦卡锡开发的第一个人工智能语言Lisp。作为作业，麦卡锡让学生编写程序以验证给定的图是否是平面图，并建议学生们在程序中使用库拉托夫斯基条件。陶尔扬虽然一开始就意识到这样的算法效率太低，考虑另起炉灶，但不知从何人手。这时霍普克洛夫特提出的新思路启发了他，他经过仔细考虑和研究，对霍普克洛夫特的方案进行了细化与完善，终于使深度优先搜索算法完美实现，取得成功。 { 枫下论坛 rolia.net/forum }
1972年，陶尔扬以平面图测试算法为题完成了博士论文，以优异成绩通过论文答辩取得博士学位，这时离开他取得硕士学位刚刚一年。学成以后，陶尔扬先是跟随霍普克洛夫特去了康乃尔大学，以后又先后在加州大学伯克利分校、母校斯坦福大学和贝尔实验室工作过，其主要兴趣和研究方向仍是和生产、生活有密切联系的一些算法问题和发现新的数据结构。陶尔扬到康乃尔大学后研究和解决的第一个问题是所谓“合并- 搜索问题”，也是图论算法中的一个问题。在许多图论算法中，要将图的结点分成若干不同的组，叫做“分区”（Partition）。在算法过程中，不同的分区有时需要合并成较大的分区，这就是合并-搜索问题中的“合并”操作。算法中也经常需要判断两个结点是否属于同一分区，这就是合并-搜索问题中的“搜索”操作。为了提高效率，搜索操作应尽可能缩短搜索路径，这叫“路径压缩”。这个问题看似简单，其实不然，包括一些知名学者在内的人在研究和分析这个问题的时候都犯了这样那样的错误。陶尔扬深入研究这个问题，最后利用阿克曼函数（Ackermann function，这是数学家阿克曼在1928年找到的一个可计算、但不是原始递归的函数）成功地解决与分析了“合并- 搜索问题”。
在研究合并- 搜索问题的过程中，陶尔扬还提出了“分摊”算法的概念。分摊（amortization）这个术语是陶尔扬从财会术语中借用过来的。陶尔扬发现，有时虽然单个查找操作可能很费时间，但通过路径压缩却可以大大减少以后的一些查找操作所需的时间，也就是说，一个查找操作额外做的工作可以“分摊”给从中受益的多个查找操作，因此从整体上看是提高了效率。分摊的概念将程序员的注意力从关注单个操作的时间引导到转而关注所有操作的平均时间，在算法设计与分析中引起了一场革命。
1975年，陶尔扬和他的学生在斯坦福研究最大网络流问题。这个问题由于对天然气和石油管道、公路网、铁路网和通信网的设计有巨大意义而吸引了许多学者。福特（L．Foul）和福格申（D．Fulkerson）早在1956年就提出了解决这个问题的第一个计算机算法，但某些情况下效率不高，甚至无法找到正确答案。十年后埃德蒙多（J．Edmonds）和卡普（R．Karp，1985年图灵奖获得者）改进了这个算法，使之有更高的效率。陶尔扬发现，最大网络流问题的关键不在于算法本身而在于数据结构。经过艰苦探索，陶尔扬和他的学生终于发明了一种称为“动态树”（dynamic tree）的新的数据结构，在此基础上他们开发成功了前所未有的最大网络流高效算法，获得了广泛应用。1980年，陶尔扬在贝尔实验室继续研究这一课题，将他以前提出的分摊的概念用于网络流问题，发现如果不集中于最坏情况，而去关注平均时间，也就是说不谋求在最坏情况下有效，而谋求在分摊情况下有效，可以使最大网络流问题获得更好的结果。循着这一方向，陶尔扬和他的学生提出了“自调整”（Self-adjusting）数据结构的概念，并发明了一种有着良好特性的新的数据结构——“八字形树”（splay tree）。目前，在算法设计中利用陶尔扬提出的分摊概念以提高效率已成为重要的方法之一。
2O世纪80年代初，陶尔扬一方面在贝尔实验室工作，一方面在纽约大学当兼职教授。他和纽约大学的几个研究生开始了一项新的研究——研究能长期保存信息的数据结构，即利用这种数据结构不但可以跟踪其最近的信息，还可以跟踪其过去的信息，陶尔扬称他们设计出来的这种数据结构为“持久性数据结构”(persistent data structure) 利用陶尔扬的持久性数据结构访问其当前信息的速度和通常的数据结构几乎一样快，要获得过去的信息也只需要程序付出一点点额外的代价。持久性数据结构已经在计算几何和并行处理中获得成功应用，但是它的更加重要的应用领域是时态数据库（temporal database），尤其是历史性数据库（historical database），随着这类数据库的发展，持久性数据结构将会大放异彩。
陶尔扬由于一系列创造性工作而获得许多荣誉。除了图灵奖以外，1983年他被国际数学联合会授予以著名数学家内兰林那命名的信息科学奖（Neranlinna prize in information science）,1984年美国科学院授予他研究创新奖（National Academy 0f Science Award for Initiatives in Research）。 1987年和 1988年他先后当选为美国科学院院士和美国工程院院士。
在接受图灵奖时，霍普克洛夫特和陶尔扬分别发表了演说，前者的演说题为“计算机科学：作为一门学科的出现”（ Computer Science：the Emergence of a Discipline），后者的演说题为“算法设计”（Algorithm Design）。两人还一起接受了记者卡伦·弗兰克尔（Karen A．Frenkel）的采访。两篇演说及与记者的对话刊于 Communications of ACM， 1987年3月，197－222页。颁奖典礼是在德克萨斯州的达拉斯召开的1986年秋季联合计算机会议期间举行的。
陶尔扬目前还兼任总部在加州申尼维尔（Sunnyvale）的InterTrust公司的首席科学家。
他的电子信箱为:
＜ 相约加拿大 ROLIA.NET ＞
ret＠cs．princeton．edu