Algorithm 版 (精华区)

发信人: ssos (存在与虚无·戒酒戒网), 信区: Algorithm
标  题: 1999年度图灵奖得主──约翰·霍泼克洛夫特和罗伯特�
发信站: 哈工大紫丁香 (2001年08月23日17:04:03 星期四), 站内信件

---- 1999年图灵奖由康乃尔大学机器人实验室主任约翰·霍泼克洛夫特(John Edward 
Hopcroft) 和普林斯顿大学计算机科学系教授罗伯特·塔扬(Robert Endre Tarjan)共享
，而塔扬曾是霍泼克洛夫特的学生。这师生两人由于在数据结构和算法的分析和设计方
面的许多创造性贡献而共同获此殊荣，在业界传为美谈。
----霍泼克洛夫特1939年10月7日生于西雅图。1961 年在西雅图大学获得电气工程学士
学位以后，进入斯坦福大学研究生院深造，1962年获得硕士学位，1964年获得博士学位
，也就是说只用了3年时间他就拿下了2个学位，霍泼克洛夫特的勤奋和聪颖由此可见。
学成以后，霍泼克洛夫特曾先后在普林斯顿大学、康乃尔大学、斯坦福大学等著名学府
工作，也曾任职于NSF(美国科学基金会)和NRC(美国国家研究院)，从事对科学研究的规
划和行政管理工作，但时间不长。
----霍泼克洛夫特成为著名的计算机科学家起源于一个十分偶然的机会。霍泼克洛夫特
学习的专业是电气工程，原先对计算机科学没有多少知识，只学过一门“开关电路和逻
辑设计”算多少有些关系。因此他原打算毕业后去西海岸的一所大学执教电气工程方面
的课程。但就在毕业以前，有一次他偶然经过他的导师、研究神经网络的先驱和著名学
者威德罗(Bernard Widrow)办公室的门口，当时，普林斯顿大学的麦克卢斯基教授(Edw
ard McCluskey，曾任IEEE计算机协会主席)正为筹建数字系统实验室打电话给威德罗，
请他推荐博士生去那里工作。威德罗一眼瞥见从门口走过的霍泼克洛夫特，觉得勤奋好
学，悟性又高的这位得意门生正是一个值得推荐的人才，当即把霍泼克洛夫特叫进办公
室，并把电话听筒递给了他。霍泼克洛夫特在电话里听了麦克卢斯基对普林斯顿大学拟
建数字系统实验室的情况介绍，以后又前去面谈了一次，实地了解一番以后，对这一新
的学科产生了兴趣，欣然接受了普林斯顿的聘任，从而改变了他一生的道路。
----年青的霍泼克洛夫特来到普林斯顿之后接受的第一项任务是开设一门新课：自动机
理论。这对他来说是富有挑战性的，因为他之前并未接触过这个课题。面对挑战，他以
极大的热情收集、钻研和消化了大量有关材料，加以分析、综合和比较。这样，在霍泼
克洛夫特的努力下，有关自动机理论的一些分散、复杂的材料第一次被全面地条理化、
系统化，因此他的讲课理所当然地受到了学生极大的欢迎。后来，霍泼克洛夫特和厄尔
曼(J.D.Ullman)又合作编写了《形式语言及其与自动机的关系》(《Formal Language a
nd Their Relation to Automata》，Addison-Wesley,1969)一书，这本书被认为是自动
机理论中有代表性的一部著作。
----然而，霍泼克洛夫特更感兴趣的课题是算法。当时，算法复杂性理论虽已由哈特马
尼斯(J.Hartmanis)、斯坦恩斯(R.Stearns,这两人是1993年图灵奖获得者)和布鲁姆(M.
Blam，1995年图灵奖获得者)等人奠定了基础，但对具体算法的效率和优劣的判断尚未建
立起客观和明确的准则，因此，往往出现下述情况：有人公布了一个算法，给出对若干
样本问题的执行时间；过了一段时间，另外一个人发布“改进算法”，给出对相同样本
问题的执行时间(当然比前者少)。而实际上，这很可能是由于机器性能提高或(和)语言
改进所致，所谓“改进算法”其实不见得比原算法高明。霍泼克洛夫特对这种情况很不
满意，决心加以解决。经过反复研究，他终于提出了一种称为“最坏情况渐近分析法”
(Worst-case asymptotic analysis of algorithm)，这种方法先确定问题和大小尺度，
然后把计算时间当作问题大小尺度的一个函数去算出计算时间的增长率，以此衡量算法
的效率和优劣。这个方法由于与机器性能及所用语言无关，成为测量算法好坏的数学准
则，被学界所广泛认同和接受。
----但是导致他和塔扬共同获得图灵奖的最主要贡献则是他们解决了图论算法中的一些
难题。1970年，霍泼克洛夫特在康乃尔大学获得一年休假(他是1967年被另一图灵奖获得
者哈特马尼斯招至麾下的)。他决定回母校斯坦福大学到克努特(D.Knuth)教授名下做研
究，因为克努特虽然只比他年长一岁，但因在1967年和 1968年连出两卷《计算机程序设
计的艺术》(《The Art of Computer Programming》)而已名满天下，成为算法领域的权
威。克努特知道霍泼克洛夫特对算法感兴趣并有独到见解，就把他和自己的得意门生、
研究方向也是算法的塔扬安排在一个办公室，为他们的合作创造了条件。他们选择了图
论中与实际应用有很大关系的图的连通性和平面性测试难题进行攻关。拿平面图来说，
它对印刷电路板设计这样一类问题有十分重要的意义。学过图论的人都知道，平面图的
判断问题，在数学上已由波兰数学家库拉托夫斯基(Kuratowski) 于1930年解决。库拉托
夫斯基的判据原理看似简单，但实现起来很难。对于有100个顶点的图，用普通的算法，
计算机需要1万亿步才能确定其是否为平面图!因此，寻找高效的平面图测试算法成为摆
在当时计算机科学家面前的一大难题。霍泼克洛夫特和塔扬都是富有创造性的人，又都
善于合作共事，因此当两朵智慧的火花碰在一起时，就很快迸发出耀眼的光芒!在解决这
个难题的过程中，霍泼克洛夫特首先提出了一种新的思路、新的算法，经过塔扬的反复
推敲和完善，一种适于解这类问题的新的算法终于诞生了，这就是“深度优先搜索算法
”(depth-first search algorithm)。利用这种算法对图进行搜索时，结点扩展的次序
是向某一个分枝纵深推进，到底后再回溯，这样就能保证所有的边在搜索过程中都经过
一次，并且只经过一次，从而大大提高了效率。新算法的运行时间是线性的，也就是说
时间与图的大小成正比关系，大小翻一倍，解问题所需的时间也只翻一倍。相比之下，
若用库拉托夫斯基判断的老算法，那么当图的大小翻一倍时，所需时间要增加60倍以上
。利用他们创造的新算法，塔扬用Algolw为一个包含900个结点和2694 条边的图编制了
一个测试其平面性的程序，程序只有500行，在IBM 360/67上运行，只用了12秒就得到了
结果。霍泼克洛夫特和塔扬把他们的研究成果写成论文在《Journal of the ACM》上发
表，引起学术界很大的轰动。而他们创造的深度优先算法则被推广到信息检索、国际象
棋比赛程序、专家系统中的冲突消解策略等许多方面。在霍泼克洛夫特和塔扬获得图灵
奖的授奖仪式上，当年的计算机象棋程序比赛的优胜者就说，他的程序中使用了霍泼克
洛夫特和塔扬所发明的深度优先搜索算法，这是他的程序所以能出奇制胜的关键。
----在取得辉煌成功之后，霍泼克洛夫特和塔扬并不满足，他们致力于开发效率更高的
算法。不久，他们又提出了一种新的数据结构叫“双堆栈叠”（pile of twin stacks）
，这种新的数据结构被深度优先搜索算法的优点更加发扬光大。塔扬的一个学生用这种
新的数据结构和算法编写了一个Algolw程序，只有250行，在IBM 370/168上测试有8000
个结点的图的平面性只用了8秒钟。
----霍泼克洛夫特除了和塔扬合作取得上述成果外，在数据结构和算法方面还有其他一
系列创造。比如常用于索引组织的著名数据结构B树(B-tree) 是一种平衡的多分树，由
于对查找、插入、删除等操作能始终保持动态平衡，具有高效的特性。霍泼克洛夫特在
对B树进行深入研究以后，为了进一步提高其操作效率和空间利用率，提出了它的一种变
形叫2-3树，这种树的每个结点有2个键，每个键都有2-3个儿子。
----霍泼克洛夫特著述颇丰，除前面已经提到过的他的处女作以外，还有以下多部著作
问世：
----《计算机算法的设计与分析》、《数据结构和算法》 、《自动机理论，语言和计算
的导论》和《计算机科学 ：成就与机遇》。
----霍泼克洛夫特最近的兴趣集中在机器人学方面，这从他现任康乃尔大学机器人实验
室主任这一点上可以看出。
---- ★☆★☆★☆★☆★☆★☆★☆★☆★
----罗伯特·塔扬1948年4月30日生于加里福尼亚州的波莫纳(Pomona)。塔扬从小就是一
个富于幻想、追求新鲜事物的人。他幼时对天文学很感兴趣，梦想成为第一个登上火星
的人。小学七年级时他又开始读《科学美国人》(《Scentific American》，这是美国最
著名的科普杂志之一)，尤其对著名数学家马丁·加德那(M.Gardner) 开设的趣味数学专
栏深感兴趣(马西·加德那所著的《啊哈!灵机一动》由上海科技出版社于1981年译成中
文出版，被中国科学家评为“20世纪科普佳作”之一而进行推介)。1964 年，塔扬参加
一个中学生科学夏令营，第一次接触计算机，立即被神奇的计算机所吸引。因此，当他
上加州理工学院时，虽然学的专业是数学，但同时还辅修了当时学校开设的所有有关计
算机的课程。1969年他取得学士学位以后，进入斯坦福大学研究生院，师从著名的计算
机科学家、后来在1974年荣获图灵奖的克努特。1970年，在克努特的有意安排下，他与
到斯坦福来度学术假的康乃尔大学教师霍泼克洛夫特在一个办公室开始了对图论算法的
共同研究。他们的这个课题实际上是在有“人工智能之父”之称的麦卡锡 (J.McCarthy
)的建议下进行的。当时塔扬正选修麦卡锡开设的“符号处理”(Symbolic processing)
课程，学习由麦卡锡开发的第一个人工智能语言Lip。作为作业，麦卡锡让学生编写程序
以验证给定的图是否是平面的，并建议学生们在程序中使用库拉托夫斯基条件。塔扬虽
然一开始就意识到这样得出的算法效率太低，考虑“另起炉灶”，但不知从何入手。这
时霍泼克洛夫特提出的新思路、新算法启发了他，他仔细考虑了它，并力图使霍泼克洛
夫特的算法中的原则更加严密、更加完善，终于使深度优先搜索算法完美实现，取得成
功。
----1992年，塔扬以平面图测试的高效算法为题完成了博士论文，以优异成绩通过论文
答辩取得博士学位，这时离他取得硕士学位刚刚一年。学成以后，塔扬先是跟随霍泼克
洛夫特去了康乃尔大学，以后又先后在加州大学伯克利分校、母校斯坦福大学以及贝尔
实验室工作过，其主要兴趣和研究方向仍是和生产、生活有密切联系的一些算法问题和
发现新的数据结构。塔扬到康乃尔大学后研究和解决的第一个问题是所谓“合并-搜索问
题”。这也是图论算法中的一个问题。在许多图论算法中，要将图的结点分成若干不同
的组，叫做“分区”(Partition)。在算法过程中，不同的分区有时需要合并成较大的分
区，这是合并搜索问题中的“合并”操作。算法中也经常需要判断两个结点是否属于同
一分区，这是合并搜索问题中的“搜索”操作。为了提高效率，搜索操作应尽可能地编
短搜索路径，这叫“路径压缩”(Path compression)。这个问题看似简单，其实不然，
包括一些知名学者在内的人在研究和分析这个问题的时候都犯了这样那样的错误。塔扬
深入研究了这个问题，最后利用阿克曼函数(Ackermann function，这是数学家阿克曼在
1928年找到的一个可计算、但不是原始递归的函数)成功地解决并分析了“合并-搜索问
题”。
----在研究合并-搜索问题的过程中，塔扬还提出了所谓 “分摊”算法的概念。分摊(a
mortization)这个词是塔扬从财会术语中借用过来的，因为塔扬发现，有时虽然单个操
作可能很费时间，但通过路径压缩却可以大大减少以后查找操作所需的时间，这就是说
，一个查找操作额外做的工作可以“分摊”给从中受益的多个查找操作，因此从整体上
看是提高了效率。分摊的概念将对算法的注意力从关注单个操作的时间转向关注整个操
作的平均时间，在算法设计与分析中引起了一场革命。
----1975年，塔扬和他的学生在斯坦福研究对于天然气和石油管道运输这类问题有很大
意义的最大网络流问题。这个问题由于对经济和交通、通信的巨大实际意义而吸引了许
多学者。福特(L.Ford)和富尔克森(D.Falkerson)早在1956 年就提出了解决这个问题的
第一个计算机算法，但是某些情况下效率不高，甚至无法找到正确答案。十年后埃德蒙
多(J.Edmcnds)和卡泼(R.Karp，1985年图灵奖获得者)改进了这个算法，使之有更高的效
率。塔扬发现，最大网络流问题的关键不在乎算法本身而在于数据结构。经过艰苦探索
，塔扬和他的学生终于发明了一种称为“动态树”(dynamic tree) 的新的数据结构，在
此基础上他们开发成功了前所未有的最大网络流高效算法，获得了广泛采用。1980年，
塔扬在贝尔实验室继续研究这一课题，将他以前提出的分摊的概念用于网络流问题，发
现如果不集中于最坏情况，而去关注平均时间，也就是说不追求在最坏情况下的有效，
而是追求在分摊的情况下有效，可以使最大网络流问题获得更好的结果。循着这一方向
，塔扬和他的学生提出了“自调整”(self-adjusting)数据结构的概念，并发明了一种
有着良好特性的新的数据结构——“八字形树”(splay tree)。目前，在算法设计中利
用塔扬提出的分摊来提高效率已成为重要的方法之一。
----80年代初，塔扬一方面在贝尔实验室工作，一方面在纽约大学当兼职教授。他和纽
约大学的几个研究生开始了一项新的研究——研究能够长期保存信息的数据结构，即利
用这种数据结构不但可以跟踪其最近的信息，还可以跟踪其过去的信息，塔扬称他们设
计出来的这种数据结构为“持久性数据结构”(persistent data structure)。利用塔扬
的持久性数据结构访问其当前信息的速度和通常的数据结构几乎一样快，而要获得过去
的信息只需要程序付出一点点额外的代价。持久性数据结构已经在计算几何和并行处理
中获得应用，但其更重要的应用领域是时态数据库(temporal database)，尤其是历史性
数据库(historical database)。
----塔扬由于他的一系列创造性工作而获得许多荣誉。除了图灵奖以外，1983年他被国
际数学会IMU授予以著名数学家内兰林那命名的信息科学奖(Neranlinnal prize in Inf
ormation Science)，1984年美国科学院授予他研究创新奖(National Academy of Scie
nce Award for Initiatives in Research)。1987年和1988年他先后当选为美国科学院
院士和美国工程院院士。
----在接受图灵奖时，霍泼克洛夫特和塔扬分别发表了演说，前者的演说题为“计算机
科学：作为一门学科的出现”(Computer science：the Emergence of a Discipline)，
后者的演说题为“算法设计”(Algorithm Design)。两人还联合接受了记者卡伦·弗兰
克尔(Karen A.Frenkel)的采访。两篇演说及与记者的对话刊于《Communications of A
CM》，1987.3.，197-222页。颁奖典礼是在德克萨斯州的达拉斯举行的1999年秋季联合
计算机会议期间举行的。

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]