罗伯特·塔扬 |
简介回目录
1964年,塔扬参加一个中学生科学夏令营,第一次接触计算机,立即被神奇的计算机所吸引。因此,当他上加州理工学院时,虽然学的专业是数学,但同时还辅修了当时学校开设的所有有关计算机的课程。1969年他取得学士学位以后,进入斯坦福大学研究生院,师从著名的计算机科学家、后来在1974年荣获图灵奖的克努特。1970年,在克努特的有意安排下,他与到斯坦福来度学术假的康乃尔大学教师霍泼克洛夫特在一个办公室开始了对图论算法的共同研究。他们的这个课题实际上是在有“人工智能之父”之称的麦卡锡(J.McCarthy)的建议下进行的。当时塔扬正选修麦卡锡开设的“符号处理”(Symbolicprocessing)课程,学习由麦卡锡开发的第一个人工智能语言Lip。作为作业,麦卡锡让学生编写程序以验证给定的图是否是平面的,并建议学生们在程序中使用库拉托夫斯基条件。塔扬虽然一开始就意识到这样得出的算法效率太低,考虑“另起炉灶”,但不知从何入手。这时霍泼克洛夫特提出的新思路、新算法启发了他,他仔细考虑了它,并力图使霍泼克洛夫特的算法中的原则更加严密、更加完善,终于使深度优先搜索算法完美实现,取得成功。
罗伯特·塔扬 |
罗伯特·塔扬 |
1975年,塔扬和他的学生在斯坦福研究对于天然气和石油管道运输这类问题有很大意义的最大网络流问题。这个问题由于对经济和交通、通信的巨大实际意义而吸引了许多学者。福特(L.Ford)和富尔克森(D.Falkerson)早在1956年就提出了解决这个问题的第一个计算机算法,但是某些情况下效率不高,甚至无法找到正确答案。十年后埃德蒙多(J.Edmcnds)和卡泼(R.Karp,1985年图灵奖获得者)改进了这个算法,使之有更高的效率。塔扬发现,最大网络流问题的关键不在乎算法本身而在于数据结构。经过艰苦探索,塔扬和他的学生终于发明了一种称为“动态树”(dynamictree)的新的数据结构,在此基础上他们开发成功了前所未有的最大网络流高效算法,获得了广泛采用。1980年,塔扬在贝尔实验室继续研究这一课题,将他以前提出的分摊的概念用于网络流问题,发现如果不集中于最坏情况,而去关注平均时间,也就是说不追求在最坏情况下的有效,而是追求在分摊的情况下有效,可以使最大网络流问题获得更好的结果。循着这一方向,塔扬和他的学生提出了“自调整”(self-adjusting)数据结构的概念,并发明了一种有着良好特性的新的数据结构——“八字形树”(splaytree)。目前,在算法设计中利用塔扬提出的分摊来提高效率已成为重要的方法之一。
罗伯特·塔扬 |
塔扬由于他的一系列创造性工作而获得许多荣誉。除了图灵奖以外,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.图灵奖”,专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家阿兰·图灵,这个奖设立目的之一是纪念这位科学家。获奖者的贡献必须是在计算机领域具有持久而重大的技术先进性的。大多数获奖者是计算机科学家。
图灵奖是计算机界最负盛名的奖项,有“计算机界诺贝尔奖”之称。图灵奖对获奖者的要求极高,评奖程序也极严,一般每年只奖励一名计算机科学家,只有极少数年度有两名以上在同一方向上做出贡献的科学家同时获奖。目前
罗伯特·塔扬 |
每年,美国计算机协会将要求提名人推荐本年度的图灵奖候选人,并附加一份200到500字的文章,说明被提名者为什么应获此奖。任何人都可成为提名人。美国计算机协会将组成评选委员会对被提名者进行严格的评审,并最终确定当年的获奖者。
截止至2005年,获此殊荣的华人仅有一位,他是2000年图灵奖得主姚期智。
图灵奖对获奖者的要求极高,评奖程序极严,一般每年只奖励一名计算机科学家,只有极少数年度有两名在同一方向上做出贡献的科学家同时获奖。因此,尽管“图灵”的奖金数额不算高,但它却是计算机界最负盛名的奖项,有“计算机界诺贝尔奖”之称。
参考资料回目录
IT世界网:http://www.it.com.cn/
中国IT实验室:http://www.chinaitlab.com/
IT商网:http://www.it365.com/
和讯IT:http://it.hexun.com/