约翰·霍普克洛夫特和罗伯特·塔扬——硕果累累的算法设计大师编辑本段回目录
1986年的图灵奖由康乃尔大学机器人实验室主任约翰·霍普克洛夫特(John Edward Hopcroft)和普林斯顿大学计算机科学系教授罗伯特·塔扬(Robert Endre Tarjan)共享，而塔扬曾是霍普克洛夫特的学生。这师生两人由于在数据结构和算法的设计和分析方面的众多创造性贡献而共同获此殊荣，在业界传为美谈。
Bob Tarjan 罗伯特·塔扬1948年4月30日生于加里福尼亚州的波莫纳(Pomona)。塔扬从小就是一个富于幻想、追求新鲜事物的人。他幼时对天文学很感兴趣，梦想成为第一个登上火星的人。小学七年级时他又开始读《科学美国人》 (《ScentificAmerican》，这是美国最著名的科普杂志之一)，尤其对著名数学家马丁·加德那(M.Gardner)开设的趣味数学专栏深感兴趣(马西·加德那所著的《啊哈!灵机一动》由上海科技出版社于1981年译成中文出版，被中国科学家评为“20世纪科普佳作”之一而进行推介)。
1964年，塔扬参加一个中学生科学夏令营，第一次接触计算机，立即被神奇的计算机所吸引。因此，当他上加州理工学院时，虽然学的专业是数学，但同时还辅修了当时学校开设的所有有关计算机的课程。1969年他取得学士学位以后，进入斯坦福大学研究生院，师从著名的计算机科学家、后来在1974年荣获图灵奖的克努特。
1970年，在克努特的有意安排下，他与到斯坦福来度学术假的康乃尔大学教师霍泼克洛夫特在一个办公室开始了对图论算法的共同研究。他们的这个课题实际上是在有“人工智能之父”之称的麦卡锡(J.McCarthy)的建议下进行的。当时塔扬正选修麦卡锡开设的“符号处理”(Symbolicprocessing)课程，学习由麦卡锡开发的第一个人工智能语言Lip。作为作业，麦卡锡让学生编写程序以验证给定的图是否是平面的，并建议学生们在程序中使用库拉托夫斯基条件。塔扬虽然一开始就意识到这样得出的算法效率太低，考虑“另起炉灶”，但不知从何入手。这时霍泼克洛夫特提出的新思路、新算法启发了他，他仔细考虑了它，并力图使霍泼克洛夫特的算法中的原则更加严密、更加完善，终于使深度优先搜索算法完美实现，取得成功。
 |
| 罗伯特·塔扬 |
 |
| 约翰·霍普克洛夫特 |
1992年，塔扬以平面图测试的高效算法为题完成了博士论文，以优异成绩通过论文答辩取得博士学位，这时离他取得硕士学位刚刚一年。学成以后，塔扬先是跟随霍泼克洛夫特去了康乃尔大学，以后又先后在加州大学伯克利分校、母校斯坦福大学以及贝尔实验室工作过，其主要兴趣和研究方向仍是和生产、生活有密切联系的一些算法问题和发现新的数据结构。塔扬到康乃尔大学后研究和解决的第一个问题是所谓“合并-搜索问题”。这也是图论算法中的一个问题。在许多图论算法中，要将图的结点分成若干不同的组，叫做“分区”(Partition)。在算法过程中，不同的分区有时需要合并成较大的分区，这是合并搜索问题中的“合并”操作。算法中也经常需要判断两个结点是否属于同一分区，这是合并搜索问题中的“搜索”操作。为了提高效率，搜索操作应尽可能地编短搜索路径，这叫“路径压缩”(Pathcompression)。这个问题看似简单，其实不然，包括一些知名学者在内的人在研究和分析这个问题的时候都犯了这样那样的错误。塔扬深入研究了这个问题，最后利用阿克曼函数(Ackermannfunction，这是数学家阿克曼在1928年找到的一个可计算、但不是原始递归的函数)成功地解决并分析了“合并-搜索问题”。
约翰·霍普克洛夫特在研究合并-搜索问题的过程中，塔扬还提出了所谓“分摊”算法的概念。分摊(amortization)这个词是塔扬从财会术语中借用过来的，因为塔扬发现，有时虽然单个操作可能很费时间，但通过路径压缩却可以大大减少以后查找操作所需的时间，这就是说，一个查找操作额外做的工作可以“分摊”给从中受益的多个查找操作，因此从整体上看是提高了效率。分摊的概念将对算法的注意力从关注单个操作的时间转向关注整个操作的平均时间，在算法设计与分析中引起了一场革命。
Bob Tarjan in the early 70s1975年，塔扬和他的学生在斯坦福研究对于天然气和石油管道运输这类问题有很大意义的最大网络流问题。这个问题由于对经济和交通、通信的巨大实际意义而吸引了许多学者。福特(L.Ford)和富尔克森(D.Falkerson)早在1956年就提出了解决这个问题的第一个计算机算法，但是某些情况下效率不高，甚至无法找到正确答案。十年后埃德蒙多(J.Edmcnds)和卡泼(R.Karp，1985年图灵奖获得者)改进了这个算法，使之有更高的效率。塔扬发现，最大网络流问题的关键不在乎算法本身而在于数据结构。经过艰苦探索，塔扬和他的学生终于发明了一种称为“动态树”(dynamictree)的新的数据结构，在此基础上他们开发成功了前所未有的最大网络流高效算法，获得了广泛采用。1980年，塔扬在贝尔实验室继续研究这一课题，将他以前提出的分摊的概念用于网络流问题，发现如果不集中于最坏情况，而去关注平均时间，也就是说不追求在最坏情况下的有效，而是追求在分摊的情况下有效，可以使最大网络流问题获得更好的结果。循着这一方向，塔扬和他的学生提出了“自调整”(self-adjusting)数据结构的概念，并发明了一种有着良好特性的新的数据结构——“八字形树”(splaytree)。目前，在算法设计中利用塔扬提出的分摊来提高效率已成为重要的方法之一。
Robert Tarjan80年代初，塔扬一方面在贝尔实验室工作，一方面在纽约大学当兼职教授。他和纽约大学的几个研究生开始了一项新的研究——研究能够长期保存信息的数据结构，即利用这种数据结构不但可以跟踪其最近的信息，还可以跟踪其过去的信息，塔扬称他们设计出来的这种数据结构为“持久性数据结构”(persistentdatastructure)。利用塔扬的持久性数据结构访问其当前信息的速度和通常的数据结构几乎一样快，而要获得过去的信息只需要程序付出一点点额外的代价。持久性数据结构已经在计算几何和并行处理中获得应用，但其更重要的应用领域是时态数据库(temporaldatabase)，尤其是历史性数据库(historicaldatabase)。
塔扬由于他的一系列创造性工作而获得许多荣誉。除了图灵奖以外，1983年他被国际数学会IMU授予以著名数学家内兰林那命名的信息科学奖(NeranlinnalprizeinInformationScience)，1984年美国科学院授予他研究创新奖(NationalAcademyofScienceAwardforInitiativesinResearch)。1987年和1988年他先后当选为美国科学院院士和美国工程院院士。
Robert Tarjan在接受图灵奖时，霍泼克洛夫特和塔扬分别发表了演说，前者的演说题为“计算机科学：作为一门学科的出现”(Computerscience：theEmergenceofaDiscipline)，后者的演说题为“算法设计”(AlgorithmDesign)。两人还联合接受了记者卡伦·弗兰克尔(KarenA.Frenkel)的采访。两篇演说及与记者的对话刊于《CommunicationsofACM》，1987.3.，197-222页。颁奖典礼是在德克萨斯州的达拉斯举行的1986年秋季联合计算机会议期间举行的。
塔扬目前还兼任总部在加州申尼维尔(Sunnyvale)的Inter Trust公司的首席科学家。
他的电子信箱为: ret@cs.Princeton.edu
Department of Computer Science
Princeton University
35 Olden Street, Room 324
Princeton, NJ 08544-2087
Phone: (609) 258-4797
FAX: (609) 258-1771
1986年图灵奖获得者Robert Tarjan更多资料编辑本段回目录
作者 陈怀临
Robert TarjanRobert Endre. Tarjan(04/30/1948–)
图灵奖获得时间： 1986年。第二十一位图灵奖 (1986年)获得者。
图灵奖引用(Turing Award Citation) ：
For fundamental achievements in the design and analysis of algorithms and data structures.
( 授予Robert E. Tarjan图灵奖以表彰其在) 数据结构和算法设计与分析领域的重要的基础性的贡献。
算法分析：
http://www.algorithmist.com/index.php/Main_Page
http://en.wikipedia.org/wiki/Analysis_of_algorithms
http://en.wikipedia.org/wiki/Algorithm
http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node8.html
Big-O Notation: http://en.wikipedia.org/wiki/Big_O_notation
Design and Analysis Algorithms: http://www.personal.kent.edu/~rmuhamma/Algorithms/algorithm.html
The Mathematics of Algorithm Design
Introduction to Algorithms: http://theory.lcs.mit.edu/classes/6.046/spring04/outcome.html
Turing Award Lecture(图灵奖演讲文章)：
Robert Tarjan早期照片Algorithmic Design. Commun. ACM 30(3): 204-212(1987)
Robert E. Tarjan简介:
http://www.cs.princeton.edu/~ret/
http://www.cs.princeton.edu/~ret/Vitae05.doc
http://en.wikipedia.org/wiki/Robert_Tarjan
Robert E. Tarjan出生于1948年4月30日，Pomona，美国加州。
Tarjan于1969年从加州理工学院(ww.catech.edu) 获得其数学学士学位。在斯坦福大学，Taran分别与1971年和1972年获得其计算机科学的硕士和博士学位，并获得其数学的双学位。
在斯坦福大学计算机系，Tarjan是著名的Robert Floyd(1978年图灵奖获得者)和Donald Knuth(1974年图灵奖获得者)的学生。
从斯坦福大学毕业后，Tarjan分别在 Cornell大学，UC Berkeley，斯坦福大学，AT&T实贝尔实验室，纽约大学，普林斯顿大学，NEC研发中心，MIT担任过教职和相关职务。
Tarjan是许多图论算法的发明者，比如Tarjan’s off-line least common ancestors algorithm
目前，Tarjan是普林斯顿大学计算机系(http://www.cs.princeton.edu/ )的教授。
Tarjan曾获得过许多荣誉，比如：
Robert Tarjan（前排）在斯坦福时期HONORS
Miller Research Fellowship, University of California, Berkeley, California, 1973-1975
Guggenheim Fellowship, 1978-1979
Nevanlinna Prize in Information Science, 1983
National Academy of Sciences Award for Initiatives in Research, 1984
Honorable Mention, Lanchester Prize of the Operations Research Society of America, 1984
Fellow, American Academy of Arts and Sciences, 1985
AT&T Bell Laboratories, Distinguished Member of Technical Staff, 1985
A. M. Turing Award of the Association for Computing Machinery, 1986
Member, National Academy of Sciences, 1987
Member, National Academy of Engineering, 1988
Robert TarjanFellow, American Association for the Advancement of Science, 1990
Member, American Philosophical Society, 1990
Foundation Fellow, Institute for Combinatorics and its Applications, 1991
Honorable Mention, Lanchester Prize of the Operations Research Society of America, 1993
Fellow, Association for Computing Machinery, 1994
Fellow, New York Academy of Sciences, 1994
Paris Kanellakis Award in Theory and Practice, Association for Computing Machinery, 1999
Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences, 2004.
相关介绍编辑本段回目录
同年获得图灵奖
霍泼克洛夫特1939年10月7日生于西雅图。1961年在西雅图大学获得电气工程学士学位以后，进入斯坦福大学研
究生院深造，1962年获得硕士学位，1964年获得博士学位，也就是说只用了3年时间他就拿下了2个学位，霍泼克洛夫特的勤奋和聪颖由此可见。学成以后，霍泼克洛夫特曾先后在普林斯顿大学、康乃尔大学、斯坦福大学等著名学府工作，也曾任职于NSF(美国科学基金会)和NRC(美国国家研究院)，从事对科学研究的规划和行政管理工作，但时间不长。
约翰·霍普克洛夫特霍泼克洛夫特成为著名的计算机科学家起源于一个十分偶然的机会。霍泼克洛夫特学习的专业是电气工程，原先对计算机科学没有多少知识，只学过一门“开关电路和逻辑设计”算多少有些关系。因此他原打算毕业后去西海岸的一所大学执教电气工程方面的课程。但就在毕业以前，有一次他偶然经过他的导师、研究神经网络的先驱和著名学者威德罗(BernardWidrow)办公室的门口，当时，普林斯顿大学的麦克卢斯基教授(EdwardMcCluskey，曾任IEEE计算机协会主席)正为筹建数字系统实验室打电话给威德罗，请他推荐博士生去那里工作。威德罗一眼瞥见从门口走过的霍泼克洛夫特，觉得勤奋好学，悟性又高的这位得意门生正是一个值得推荐的人才，当即把霍泼克洛夫特叫进办公室，并把电话听筒递给了他。霍泼克洛夫特在电话里听了麦克卢斯基对普林斯顿大学拟建数字系统实验室的情况介绍，以后又前去面谈了一次，实地了解一番以后，对这一新的学科产生了兴趣，欣然接受了普林斯顿的聘任，从而改变了他一生的道路。
图灵奖，是国际计算机协会（ACM）于1966年设立的，又叫“A.M.图灵奖”，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰·图灵，这个奖设立目的之一是纪念这位科学家。获奖者的贡献必须是在计算机领域具有持久而重大的技术先进性的。大多数获奖者是计算机科学家。
图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前
 |
| 罗伯特·塔扬 |
每年，美国计算机协会将要求提名人推荐本年度的图灵奖候选人，并附加一份200到500字的文章，说明被提名者为什么应获此奖。任何人都可成为提名人。美国计算机协会将组成评选委员会对被提名者进行严格的评审，并最终确定当年的获奖者。
截止至2005年，获此殊荣的华人仅有一位，他是2000年图灵奖得主姚期智。
图灵奖对获奖者的要求极高，评奖程序极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名在同一方向上做出贡献的科学家同时获奖。因此，尽管“图灵”的奖金数额不算高，但它却是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。
