约翰·霍泼克洛夫特-电脑界人物- 科技百科 -互联网博物馆，你我的知识加油站

AlfredV.Aho博士，是哥伦比亚大学计算机科学系主管本科生教学的副主任，IEEEFellow，美国科学与艺术学院及国家工程学院院士，曾获得IEEE的冯·诺伊曼奖。他是《编译原理》（Compiler:Principles,Techniques,andTools）的第一作者。他目前的研究方向为量子计算、程式设计语言、编译器和算法等。

[显示部分][显示全部]

简介编辑本段 回目录

霍泼克洛夫特1939年10月7日生于西雅图。1961年在西雅图大学获得电气工程学士学位以后，进入斯坦福大学研究生院深造，1962年获得硕士学位，1964年获得博士学位，也就是说只用了3年时间他就拿下了2个学位，霍泼克洛夫特的勤奋和聪颖由此可见。学成以后，霍泼克洛夫特曾先后在普林斯顿大学、康乃尔大学、斯坦福大学著名学府工作，也曾任职于NSF(美国科学基金会)和NRC(美国国家研究院)，从事对科学研究的规划和行政管理工作，但时间不长。

霍泼克洛夫特成为著名的计算机科学家起源于一个十分偶然的机会。霍泼克洛夫特学习的专业是电气工程，原先对计算机科学没有多少知识，只学过一门“开关电路和逻辑设计”算多少有些关系。因此他原打算毕业后去西海岸的一所大学执教电气工程方面的课程。但就在毕业以前，有一次他偶然经过他的导师、研究神经网络的先驱和著名学者威德罗(BernardWidrow)办公室的门口，当时，普林斯顿大学的麦克卢斯基教授(EdwardMcCluskey，曾任IEEE计算机协会主席)正为筹建数字系统实验室打电话给威德罗，请他推荐博士生去那里工作。威德罗一眼瞥见从门口走过的霍泼克洛夫特，觉得勤奋好学，悟性又高的这位得意门生正是一个值得推荐的人才，当即把霍泼克洛夫特叫进办公室，并把电话听筒递给了他。霍泼克洛夫特在电话里听了麦克卢斯基对普林斯顿大学拟建数字系统实验室的情况

约翰·霍泼克洛夫特

介绍，以后又前去面谈了一次，实地了解一番以后，对这一新的学科产生了兴趣，欣然接受了普林斯顿的聘任，从而改变了他一生的道路。

年青的霍泼克洛夫特来到普林斯顿之后接受的第一项任务是开设一门新课：自动机理论。这对他来说是富有挑战性的，因为他之前并未接触过这个课题。面对挑战，他以极大的热情收集、钻研和消化了大量有关材料，加以分析、综合和比较。这样，在霍泼克洛夫特的努力下，有关自动机理论的一些分散、复杂的材料第一次被全面地条理化、系统化，因此他的讲课理所当然地受到了学生极大的欢迎。后来，霍泼克洛夫特和厄尔曼(J.D.Ullman)又合作编写了《形式语言及其与自动机的关系》 (《FormalLanguageandTheirRelationtoAutomata》，Addison-Wesley,1969)一书，这本书被认为是自动机理论中有代表性的一部著作。

约翰·霍泼克洛夫特

然而，霍泼克洛夫特更感兴趣的课题是算法。当时，算法复杂性理论虽已由哈特马尼斯(J.Hartmanis)、斯坦恩斯(R.Stearns,这两人是1993年图灵奖获得者)和布鲁姆(M.Blam，1995年图灵奖获得者)等人奠定了基础，但对具体算法的效率和优劣的判断尚未建立起客观和明确的准则，因此，往往出现下述情况：有人公布了一个算法，给出对若干样本问题的执行时间；过了一段时间，另外一个人发布“改进算法”，给出对相同样本问题的执行时间(当然比前者少)。而实际上，这很可能是由于机器性能提高或(和)语言改进所致，所谓“改进算法”其实不见得比原算法高明。霍泼克洛夫特对这种情况很不满意，决心加以解决。经过反复研究，他终于提出了一种称为“最坏情况渐近分析法”(Worst-caseasymptoticanalysisofalgorithm)，这种方法先确定问题和大小尺度，然后把计算时间当作问题大小尺度的一个函数去算出计算时间的增长率，以此衡量算法的效率和优劣。这个方法由于与机器性能及所用语言无关，成为测量算法好坏的数学准则，被学界所广泛认同和接受。

约翰·霍泼克洛夫特

但是导致他和塔扬共同获得图灵奖的最主要贡献则是他们解决了图论算法中的一些难题。1970年，霍泼克洛夫特在康乃尔大学获得一年休假(他是1967年被另一图灵奖获得者哈特马尼斯招至麾下的)。他决定回母校斯坦福大学到克努特(D.Knuth)教授名下做研究，因为克努特虽然只比他年长一岁，但因在1967年和1968年连出两卷《计算机程序设计的艺术》 (《TheArtofComputerProgramming》)而已名满天下，成为算法领域的权威。克努特知道霍泼克洛夫特对算法感兴趣并有独到见解，就把他和自己的得意门生、研究方向也是算法的塔扬安排在一个办公室，为他们的合作创造了条件。他们选择了图论中与实际应用有很大关系的图的连通性和平面性测试难题进行攻关。拿平面图来说，它对印刷电路板设计这样一类问题有十分重要的意义。学过图论的人都知道，平面图的判断问题，在数学上已由波兰数学家库拉托夫斯基(Kuratowski)于1930年解决。库拉托夫斯基的判据原理看似简单，但实现起来很难。对于有100个顶点的图，用普通的算法，计算机需要1万亿步才能确定其是否为平面图!因此，寻找高效的平面图测试算法成为摆在当时计算机科学家面前的一大难题。霍泼克洛夫特和塔扬都是富有创造性的人，又都善于合作共事，因此当两朵智慧的火花碰在一起时，就很快迸发出耀眼的光芒!在解决这个难题的过程中，霍泼克洛夫特首先提出了一种新的思路、新的算法，经过塔扬的反复推敲和完善，一种适于解这类问题的新的算法终于诞生了，这就是“深度优先搜索算法”(depth-firstsearchalgorithm)。利用这种算法对图进行搜索时，结点扩展的次序是向某一个分枝纵深推进，到底后再回溯，这样就能保证所有的边在搜索过程中都经过一次，并且只经过一次，从而大大提高了效率。新算法的运行时间是线性的，也就是说时间与图的大小成正比关系，大小翻一倍，解问题所需的时间也只翻一倍。相比之下，若用库拉托夫斯基判断的老算

约翰·霍泼克洛夫特

法，那么当图的大小翻一倍时，所需时间要增加60倍以上。利用他们创造的新算法，塔扬用Algolw为一个包含900个结点和2694条边的图编制了一个测试其平面性的程序，程序只有500行，在IBM360/67上运行，只用了12秒就得到了结果。霍泼克洛夫特和塔扬把他们的研究成果写成论文在《JournaloftheACM》上发表，引起学术界很大的轰动。而他们创造的深度优先算法则被推广到信息检索、国际象棋比赛程序、专家系统中的冲突消解策略等许多方面。在霍泼克洛夫特和塔扬获得图灵奖的授奖仪式上，当年的计算机象棋程序比赛的优胜者就说，他的程序中使用了霍泼克洛夫特和塔扬所发明的深度优先搜索算法，这是他的程序所以能出奇制胜的关键。

在取得辉煌成功之后，霍泼克洛夫特和塔扬并不满足，他们致力于开发效率更高的算法。不久，他们又提出了一种新的数据结构叫“双堆栈叠”（pileoftwinstacks），这种新的数据结构被深度优先搜索算法的优点更加发扬光大。塔扬的一个学生用这种新的数据结构和算法编写了一个Algolw程序，只有250行，在IBM370/168上测试有8000个结点的图的平面性只用了8秒钟。

霍泼克洛夫特除了和塔扬合作取得上述成果外，在数据结构和算法方面还有其他一系列创造。比如常用于索引组织的著名数据结构B树(B-tree)是一种平衡的多分树，由于对查找、插入、删除等操作能始终保持动态平衡，具有高效的特性。霍泼克洛夫特在对B树进行深入研究以后，为了进一步提高其操作效率和空间利用率，提出了它的一种变形叫2-3树，这种树的每个结点有2个键，每个键都有2-3个儿子。