编者按:作为惠普全球实验室高级院士,图灵奖获得者罗伯特•塔扬教授日前到访中国,做客“清华海外名师讲堂”,同日,在惠普中国研究院里与研究员们齐聚一堂,全面解释了他对算法的睿智见解,并用自己追求梦想的信念及刻苦研究的宝贵经验和经历,为惠普中国研究院中国的研发人员提出一些建议,希望大家能找到自己的研究课题,准备好要努力工作的方向,保持一种开放的态度,拥有持久的耐心,一步一步去实现长远的目标!
罗伯特•塔扬(Robert
Tarjan)教授是世界知名计算机学家,他的研究领域主要包括图论、算法和数据结构设计。罗伯特教授是许多图论算法的发明者,比如树中最近共同祖先离线算法、Splay
trees、Fibonacci heaps、平面性检测(Planarity testing)等。1986年,他与John
Hopcroft因为在算法及数据结构的设计和分析中所取得的成果而荣获图灵奖。他于1982年获得首届奈望林纳奖(Nevanlinna
Prize),现为美国科学院院士、美国计算机协会(ACM)院士、美国普林斯顿大学教授。
2012年4月12日,罗伯特•塔扬教授到访中国,会见了清华大学副校长袁驷教授,并做客“清华海外名师讲堂”第119讲,在清华大学信息技术大楼多功能厅,他讲述了《搜索树之谜》的特邀报告。同日,在惠普中国研究院里,罗伯特•塔扬教授与王敏院长和惠普中国研究院的研究员们齐聚一堂,全面解释了他对算法的睿智见解。
老骥伏枥 志在千里
Q:您的一生取得了非凡的成就,在您看来,这些成就是天赋还是机遇?
Robert:我还是先做个自我介绍吧。我在13岁读初中的时候,美国掀起了数学教学改革试验的浪潮,也就是以更加形式化的方式来传授数学这门课程。非常不幸的是,新运动失败了。但我恰恰成为新数学教学改革的受益者之一,也因此出现了一大批我这样的人。我对数学有很浓的兴趣,如果你们看过我的资料,会知道我经常读一些科幻小说。在孩童时期,我的梦想就是成为第一个登上火星的人。我当时非常喜欢读的一本杂志就是《SCIENTIFIC
AMERICAN(环球科学)》。此外,当时我对天文学也非常感兴趣,这也成为我日后非常重视数学学习的原因。读到高中的时候,我在暑假期间参加了某个研究中心的活动,有机会接触了当时最老式的计算机,那时的计算机还是打孔式的,后来又有机会使用IBM计算机,和最初的编程语言。所以在很小的时候,我就有机会和计算机打交道。当时我就已经对编程产生了浓厚的兴趣。到了大学本科的时候,我在加州理工大学学习。当时我主修数学,而我几乎选修了所有有关计算机科学方面的课程。读博士时,我去了斯坦福大学,选择的专业方向是计算机科学,也正是在那里,我遇见了我的导师Donald
Knuth。当我本科毕业时,我选择的研究方向其实是人工智能。但是,那时候的人工智能还处于早期阶段,整个研究领域都是非常模糊的状态。在Donald
Knuth的指导之下,我最后锁定了我的研究领域是计算机算法,主攻数据结构这一方向。从那个时候一直到现在,我都坚持了这个研究方向。
接下来回答你刚才提出的问题。天赋当然是重要的,但还有一个非常重要的成功元素,那就是你要在合适的时间,出现在合适的地方。回顾我的一生,我就是在合适的时机,选择了适合我的研究方向。对于计算机算法而言,我是把它作为数学对象来研究,来对待的。从这个角度出发,去开发计算机的算法,同时把它用于一些实际问题中。我有几位非常好的导师,他们给我提出了一些非常好的课题。还有一个成功的元素我认为应该是毅力,以及坚持不懈的学习和培训,不管你的天赋有多高,我认为还需要努力地工作、努力地学习。如果你研究的领域是和数学相关的,研究过程中失败是不可避免的,你可能会觉得懊恼,甚至会用头撞墙,但是你一定要坚持下去。如果一个问题总是找不到答案,你可以换一个课题去研究,然后过一段时间再来攻克这个难题。不管你有多么聪明,多么有天赋,我认为毅力,以及不断的学习都是非常重要的。谈到计算机科学,我认为计算机科学这个领域充满着机会。回顾计算机科学的历史,已经有75年了。这个领域让人非常的惊喜,因为它不断地给我们提供新的机会。今年是阿兰.麦席森.图灵诞辰百年,各地举行了盛大的庆典,大家以各种方式来纪念他。图灵是在20世纪30年代,也就是二战期间,提出了计算机的概念和想法,那时的计算机,还处于非常简单的阶段。
Q:您现在的梦想是什么呢?
Robert:非常感谢你这么问。我有幸来到中国惠普研究院,看到现在搞计算机科学的人都很年轻。而且我也去过很多创业型的公司,那里的人也都很年轻。计算机科学这个研究领域还很年轻,不过我已经老了。因此,我现在唯一的梦想,就是尽量多的去攻克那些现实的技术课题。我希望在我有生之年,只要还可以在智力上跟得上那些年轻人,我就一直持续的工作和研究下去。
算法是计算机领域的管道工
Q:1986年的时候,您跟您的合作者赢得了图灵奖,这是一个非常伟大的成就。对于这个成就,现在看来,它产生了很大的影响。那么,对人类的生产与生活带来了哪些改变?
Robert:当时之所以获得了图灵奖,是因为算法以及数据结构方面的成就。我认为谈到计算机算法和数据结构,它其实相当于计算机领域中“管道工”的角色。正是有了这些算法和数据结构,我们才可以把一些看似不可能找到解决方案的问题解决,而且能够让计算机的运转速度更快。如果说它对于人类的生产力、生活带来了怎样的影响,我无法具体的谈及某一个领域,它遍布了计算机行业整个领域。你看,不管是数据库还是电脑系统中,基本上都有算法以及数据结构的存在,它是一个很普遍的东西。谈到这个成就本身,我想再补充一点,它被很好地运用到了目前的教育体系中。为什么这么说呢?现在很多的理论都用到了课堂的教材中。学生们可以在课堂上学到这些,比如说对于一个课题,如何找到并研发出它的解决方案,然后又把它从一个学术的东西用到实践当中。我想这能帮助学生们学习到一些新的点子和思路。
Q:在大多数人眼里,您所从事的这项工作又枯燥又没有乐趣,但是您总能创造出新的办法或者发现新的结构,我不知道影响您的动力是什么?乐趣又是什么?
Robert:在我看来,数学是一件非常美丽的事物。数学可以运用到计算机科学中,而计算机科学又很好地帮助人们解决了现实生活的一些问题。Donald
Knuth的名著《计算机程序设计艺术》将程序设计称为艺术,算法实际上跟建筑的艺术是一样的,只不过它的这种结构是你看不见的,是存在于人们的头脑中的,是大脑编成的各种各样的美丽的建筑。这让我想起了我弟弟,非常有意思,他曾经是国际象棋大师。虽然他最后放弃了这个职业,但是我想说,可能在我的家族中,数学就是一种DNA,它真的是一件美丽的事物。我喜欢很多数学游戏。儿童时期,除了对天文学感兴趣之外,我还喜欢一些棋盘游戏,比如Martin
Gardner的游戏(《环球科学》中的数学游戏专栏),还有一些拼图游戏。
寻找课题的方向
Q:您是如何找到研究课题的方向的?
Robert:我的研究生涯非常长,我的建议是,你可以尝试去解决那些基础性的问题,而且是能够有一些具体应用的问题。大家可能先有一个具体的问题,然后要可以从中看到,或抽象出一个用数学这个工具能够解决的问题。所以我对一个课题的研究通常都要花很长时间,有的甚至几年。有时这个研究做几年,然后再隔一段时间,之后回头再去研究。这样,我们才可以把自己称为一个解决问题的人。通过解决一些基础性的问题,我从多年的科研中总结提炼出了一些理论和方法。所以,我积累了很多具体的计算机算法技巧,还有分析方面的一些技巧。在这里我必须说,和产业界保持联系是非常好的一件事情,因为如果你能够为他们具体的问题找到方案的话,回报也会很好。这也会是让你持续把这件事情做下去的原因。
Q:那么刚才谈到人工智能,上世纪不大成熟,但是到了这个世纪您还有兴趣再继续对人工智能进行研究吗?
Robert:我现在年纪太大了,没有足够的时间再去重新学习一个新的领域,但我还在持续关注人工智能这个领域。我有一些惠普的同事,他们正在试图找到一些计算数学方面的方法,还有统计学方面的方法,去更好的完善计算机学习的能力。我相信随着数学的进步,随着计算机本身技术的进步,人们在人工智能方面真正能够迈出有意义的一步。再补充一点,我还有一个梦想,如果有下辈子,我会研究人的意识,人的思想是怎么产生的。如果能够研究清楚这个课题的话,人工智能也就解决了。事实上我特别想研究人的意识、思维到底是怎么产生的。我觉得可能机器可以帮助人们解决某些问题,但是最根本的问题是,意识是怎么产生的。大家对这个问题好像比较有争议。研究这个问题我也是门外汉,因为我既不是神经学科方面的专家,也不是哲学家。
Q:我想问一下您和您的导师在相识之后,进行了一些共同的研究,那么在这个研究过程中,发生了哪些比较有趣的事?
Robert:我到斯坦福攻读博士学位的时候,第一年就全部修完了博士学位所需要的基本学分,通常这些学分需要两年才能赚到。当时我学的是图形算法,我和我的博士导师(Donald
Knuth)交换了很多观点。在我第一年学期结束的夏季,我遇见了跟我一起获奖的John
Hopcroft教授(康奈尔大学教授,当时在斯坦福进行学术休假)。所以你看,在合适的时间,出现在合适的地点是多么的关键,斯坦福的环境确实太棒了。当时我选择的一门叫做符号编程语言的课,我们要试图解决的一个问题是:如何把一个图形内嵌到一个平面中。这实际上是一个数学问题,让我举一个例子:上面的3个符号中,W代表水塔,G代表天然气塔,E就是电塔,下面是三所房子,我们现在要做的是:把水、电、气分别都接到这些房子里,但是你不能让这些线有任何交叉。这就是要解决的数学问题。这是小时候我们无法解决的数学难题,关键是图的可平面性检测。电路板布线有时也会遇到这样的问题。
在研究的过程中,我参考了很多的文献,我发现其中一个算法是可以解决这个问题的,就把它用到这儿了。但是,当时那个算法做起来比较慢,解决简单的问题可以,但是复杂的就不行了。最后我们终于想出了一个办法,能够在线性时间内,解决可平面性检测。正是因为这个研究成果,让我们获得了图灵奖。
Q:您刚才提到在研究过程中,也遇到很多挫折,有时候想用自己的头去撞墙,那么在这样一个过程中,您是怎么样鼓励自己坚持把这条路走下来的?
Robert:它总是先苦后甜的。道路越曲折,那你获得成功之后的喜悦就会越大,而且在失败的过程中能学到很多的东西。我经历了很多曲折的过程,也研究了各种各样的问题。尽管计算机科学是一个年轻的科学,有很多人在其中的时间并不长。但我发现计算机科学研究方面也需要存在系统性。要解决一个问题,就要找到一个比较容易的方式,也许这个方式是最容易的,但却并不是最好的,最简单的。所以有时候,对一些已经解决的问题,我们只要回头,就可以找到更加简单,而且更加行之有效的方案。因此,我认为关键点就是一定要坚持简单、高效。因为如果你的方法不够简单的话,大家就不会想去用了。我的建议就是,千万不要害羞,一定要大胆地尝试。科研是没有边界的,要勇于去打破常规旧俗,而且我想再一次强调,一定要有毅力,而且要努力,勤奋地工作。
用算法提高业务效率
Q:您现在在惠普研究院从事哪些领域的研究?有没有一些可以介绍的成果?
Robert:我在惠普担任的高级院士是研究方面最高的头衔,我并不做任何管理的工作,惠普交给我做的唯一工作就是算法研究,我可以自由选择我的具体研究问题。
目前我们在做的一项工作是,利用算法提高业务流程的效率。现在人们经常谈到业务流程的自动化,而我现在就在与惠普负责运营方面的人员合作,希望借由算法来提高惠普内部的流程效率,从而帮助惠普内部提高效率,降低成本。如果能够在惠普内部用好的话,也许可以把它商品化成为一种产品或者一种服务。
我举个例子,一个具体在做的项目叫做人力优化。惠普收购了一家服务公司叫EDS,经常会承接很多项目。对于一个项目来说,需要有各种技能的人,而每个人又有不同的技能。已存在标准算法是:每个技能我们可以用数学的方法给它一个量化,根据这些量化数字,再做人员和项目的匹配。但是我们发现它的效果并不是很好,我们希望能够改善这个算法,能够得到更好的匹配,这样的话,就可以实现人力的优化。
我再举一个我和惠普中国研究院的例子。王敏院长以及这里的同事在研究的一个课题是网络。你们也知道,惠普收购了3COM,其中的H3C在中国是一家做得比较大的网络公司。我们正在一起合作,关注如何把算法运用于网络技术。
作为惠普的资深科学家,我也会经常去指导各地惠普研究院的技术研究方向;同时我也辅导一些年轻的研究员,担当团队技术领袖的角色。
Q:随着IT行业的发展,是否意味着企业的研究工作也要产生变化,未来的研究趋势是怎样的?此外在教育方面,您觉得应该如何培养孩子对数学着迷?
Robert:作为个人来说,时间是有限的,不可能去研究所有时髦的东西。我是做基础研究的,不管IT界怎么发展,摩尔定律仍然在发挥作用:计算机的速度、芯片的速度,仍然是每18个月要翻一翻;那么存储也要不断的增加,还有网络通讯的力量也会不断加大。所以你会看到IT的趋势和方向并没有放缓,而是在加速在往前走。但是对于研究来说,计算机本身运转的速度并不是最重要的,随着移动设备越来越多的出现,还有更多的空间,开发更有趣的应用。想想我那个时代,用的计算机像冰箱那么大,还是打孔式的,所以你就会看到这样的一种发展的空间。我相信,很快电脑设备将能够模拟人工智能。但是它底层的技术是不变的;所以我这样做基础研究的人的优势在于,这份工作是不变的。
我觉得如果你对小孩进行填鸭式的教育,他们肯定会反抗的。我个人更倾向于把孩子放在充满丰富的选择和丰富信息的环境下,让他们自己去选择。其实你看这个世界上,真正杰出的数学家是非常少的,而且世界上并不需要那么多杰出的数学家。但是这个世界正在变得越来越技术性;我们确实需要大量的能够懂数学,能够运用数学做编程的人,所以我觉得教育的方法还是应该因材施教。
Q:刚才提到遇到挫折就会撞墙,会经常这样吗?
Robert:这是一种修辞用法!否则脑袋早撞扁了。
Q:遇到的挫折多不多?
Robert:事实上,我的博士论文花了1年多的时间才找到答案。其实在一年多的时间里,研究是断断续续的。很可能会进入死角,那就搁置一会儿,再回头研究。还有一些课题,我甚至研究了10年之久。
Q:我不知道您来的2天时间里,见到的中国年轻人给你的印象如何?能不能给这些在计算机领域有天赋的年轻人一些建议,怎样才能成为像您这样大师级的人物?
Robert:惠普中国研究院的孩子们都是很好,而且都很聪明,工作非常努力,我对他们的印象非常好。我对这些年轻的有天赋的年轻人的建议是:一定要找到自己想要研究的课题,不要盲目听从别人的话依照去做。我跟这些年轻人说:不要总跟着业务部门的人做事。事实上,研究员的眼界应该比他们放得更广,要看到五年甚至以后更长久的方向。
我觉得,象惠普研究院这样做基础性研究的机构在整个产业界并不多。我们看到的互联网公司,他们做一些非常先进的编程,做一些产品或者技术的开发工作;但是基础性研究他们不做。他们觉得基础性研究应该由大学院校去做。所以,我觉得惠普研究院的机制确实很少见。因此,我最后还是回到给他们建议上:要找到自己的课题,准备好要努力工作的方向。还有一点,你要愿意和你的同事和朋友一起工作,有了成果愿意和别人分享,而且也要和别人去交流,要保持一种开放的态度!而且要有持久的耐心,设立一个长远的目标,要一步一步去实现!感谢你们花时间聆听,希望我的分享对你们有用!
加载中,请稍候......