罗伯特·塔扬

　　1964年，塔扬参加一个中学生科学夏令营，第一次接触计算机，立即被神奇的计算机所吸引。因此，当他上加州理工学院时，虽然学的专业是数学，但同时还辅修了当时学校开设的所有有关计算机的课程。1969年他取得学士学位以后，进入斯坦福大学研究生院，师从著名的计算机科学家、后来在1974年荣获图灵奖的克努特。1970 年，在克努特的有意安排下，他与到斯坦福来度学术假的康乃尔大学教师霍泼克洛夫特在一个办公室开始了对图论算法的共同研究。他们的这个课题实际上是在有 “人工智能之父”之称的麦卡锡(J.McCarthy)的建议下进行的。当时塔扬正选修麦卡锡开设的“符号处理”(Symbolicprocessing)课程，学习由麦卡锡开发的第一个人工智能语言Lip。作为作业，麦卡锡让学生编写程序以验证给定的图是否是平面的，并建议学生们在程序中使用库拉托夫斯基条件。塔扬虽然一开始就意识到这样得出的算法效率太低，考虑“另起炉灶”，但不知从何入手。这时霍泼克洛夫特提出的新思路、新算法启发了他，他仔细考虑了它，并力图使霍泼克洛夫特的算法中的原则更加严密、更加完善，终于使深度优先搜索算法完美实现，取得成功。

　　1992年，塔扬以平面图测试的高效算法为题完成了博士论文，以优异成绩通过 论文答辩取得博士学位，这时离他取得硕士学位刚刚一年。学成以后，塔扬先是跟随霍泼克洛夫特去了康乃尔大学，以后又先后在加州大学伯克利分校、母校斯坦福大学以及贝尔实验室工作过，其主要兴趣和研究方向仍是和生产、生活有密切联系的一些算法问题和发现新的数据结构。塔扬到康乃尔大学后研究和解决的第一个问题是所谓“合并-搜索问题”。这也是图论算法中的一个问题。在许多图论算法中，要将图的结点分成若干不同的组，叫做“分区”(Partition)。在算法过程中，不同的分区有时需要合并成较大的分区，这是合并搜索问题中的“合并”操作。算法中也经常需要判断两个结点是否属于同一分区，这是合并搜索问题中的“搜索”操作。为了提高效率，搜索操作应尽可能地编短搜索路径，这叫“路径压缩”(Pathcompression)。这个问题看似简单，其实不然，包括一些知名学者在内的人在研究和分析这个问题的时候都犯了这样那样的错误。塔扬深入研究了这个问题，最后利用阿克曼函数(Ackermannfunction，这是数学家阿克曼在1928年找到的一个可计算、但不是原始递归的函数)成功地解决并分析了“合并-搜索问题”。 在研究合并-搜索问题的过程中，塔扬还提出了所谓“分摊”算法的概念。分摊(amortization)这个词是塔扬从财会术语中借用过来的，因为塔扬发现，有时虽然单个操作可能很费时间，但通过路径压缩却可以大大减少以后查找操作所需的时间，这就是说，一个查找操作额外做的工作可以“分摊”给从中受益的多个查找操作，因此从整体上看是提高了效率。分摊的概念将对算法的注意力从关注单个操作的时间转向关注整个操作的平均时间，在算法设计与分析中引起了一场革命。 1975年，塔扬和他的学生在斯坦福研究对于天然气和石油管道运输这类问题有很大意义的最大网络流问题。这个问题由于对经济和交通、通信的巨大实际意义而吸引了许多学者。福特(L.Ford)和富尔克森(D.Falkerson)早在1956年就提出了解决这个问题的第一个计算机算法，但是某些情况下效率不高，甚至无法找到正确答案。十年后埃德蒙多(J.Edmcnds)和卡泼(R.Karp，1985年图灵奖获得者)改进了这个算法，使之有更高的效率。塔扬发现，最大网络流问题的关键不在乎算法本身而在于数据结构。经过艰苦探索，塔扬和他的学生终于发明了一种称为“动态树”(dynamictree)的新的数据结构，在此基础上他们开发成功了前所未有的最大网络流高效算法，获得了广泛采用。1980年，塔扬在贝尔实验室继续研究这一课题，将他以前提出的分摊的概念用于网络流问题，发现如果不集中于最坏情况，而去关注平均时间，也就是说不追求在最坏情况下的有效，而是追求在分摊的情况下有效，可以使最大网络流问题获得更好的结果。循着这一方向，塔扬和他的学生提出了“自调整”(self-adjusting)数据结构的概念，并发明了一种有着良好特性的新的数据结构——“八字形树”(splaytree)。目前，在算法设计中利用塔

　　扬提出的分摊来提高效率已成为重要的方法之一。80年代初，塔扬一方面在贝尔实验室工作，一方面在纽约大学当兼职教授。他和纽约大学的几个研究生开始了一项新的研究——研究能够长期保存信息的数据结构，即利用这种数据结构不但可以跟踪其最近的信息，还可以跟踪其过去的信息，塔扬称他们设计出来的这种数据结构为“持久性数据结构”(persistentdatastructure)。利用塔扬的持久性数据结构访问其当前信息的速度和通常的数据结构几乎一样快，而要获得过去的信息只需要程序付出一点点额外的代价。持久性数据结构已经在计算几何和并行处理中获得应用，但其更重要的应用领域是时态数据库(temporaldatabase)，尤其是历史性数据库(historicaldatabase)。 塔扬由于他的一系列创造而获得许多荣誉。除了图灵奖以外，1983年他被国际数学会IMU授予以著名数学家内兰林那命名的信息科学奖(NeranlinnalprizeinInformationScience)，1984年美国科学院授予他研究创新奖(NationalAcademyofScienceAwardforInitiativesinResearch)。1987年和1988年他先后当选为美国科学院院士和美国工程院院士。

　　在接受图灵奖时，霍泼克洛夫特和塔扬分别发表了演说，前者的演说题为“计算机科学：作为一门学科的出现”(Computerscience：theEmergenceofaDiscipline)，后者的演说题为“算法设计”(AlgorithmDesign)。两人还联合接受了记者卡伦·弗兰克尔(KarenA.Frenkel)的采访。两篇演说及与记者的对话刊于《CommunicationsofACM》，1987.3.，197-222页。颁奖典礼是在德克萨斯州的达拉斯举行的1986年秋季联合计算机会议期间举行的。

　　霍泼克洛夫特1939年10月7日生于西雅图。1961年在西雅图大学获得电气工程学士学位以后，进入斯坦福大学研究生院深造，1962年获得硕士学位，1964年获得博士学位，也就是说

　　只用了3年时间他就拿下了2个学位，霍泼克洛夫特的勤奋和聪颖由此可见。学成以后，霍泼克洛夫特曾先后在普林斯顿大学、康乃尔大学、斯坦福大学等著名学府工作，也曾任职于NSF(美国科学基金会)和NRC(美国国家研究院)，从事对科学研究的规划和行政管理工作，但时间不长。霍泼克洛夫特成为著名的计算机科学家起源于一个十分偶然的机会。霍泼克洛夫特学习的专业是电气工程，原先对计算机科学没有多少知识，只学过一门“开关电路和逻辑设计”算多少有些关系。因此他原打算毕业后去西海岸的一所大学执教电气工程方面的课程。但就在毕业以前，有一次他偶然经过他的导师、研究神经网络的先驱和著名学者威德罗(BernardWidrow)办公室的门口，当时，普林斯顿大学的麦克卢斯基教授(EdwardMcCluskey，曾任IEEE计算机协会主席)正为筹建数字系统实验室打电话给威德罗，请他推荐博士生去那里工作。威德罗一眼瞥见从门口走过的霍泼克洛夫特，觉得勤奋好学，悟性又高的这位得意门生正是一个值得推荐的人才，当即把霍泼克洛夫特叫进办公室，并把电话听筒递给了他。霍泼克洛夫特在电话里听了麦克卢斯基对普林斯顿大学拟建数字系统实验室的情况介绍，以后又前去面谈了一次，实地了解一番以后，对这一新的学科产生了兴趣，欣然接受了普林斯顿的聘任，从而改变了他一生的道路。

　　图灵奖，是国际计算机协会（ACM）于1966年设立的，又叫“A.M.图灵奖”，专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰·图灵，这个奖设立目的之一是纪念这位科学家。获奖者的贡献必须是在计算机领域具有持久而重大的技术先进性的。大多数获奖者是计算机科学家。

　　图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名以上在同一

　　方向上做出贡献的科学家同时获奖。目前 图灵奖由英特尔公司赞助，奖金为100,000美元。 每年，美国计算机协会将要求提名人推荐本年度的图灵奖候选人，并附加一份200到500字的文章，说明被提名者为什么应获此奖。任何人都可成为提名人。美国计算机协会将组成评选委员会对被提名者进行严格的评审，并最终确定当年的获奖者。

　　截止至2005年，获此殊荣的华人仅有一位，他是2000年图灵奖得主姚期智。

　　图灵奖对获奖者的要求极高，评奖程序极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名在同一方向上做出贡献的科学家同时获奖。因此，尽管“图灵”的奖金数额不算高，但它却是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。