罗伯特·塔扬 Robert Tarjan

罗伯特·塔扬（Robert Tarjan），别名罗伯特·恩德雷·塔扬（Robert Endre Tarjan），1948年4月30日出生于美国加利福尼亚州的波莫纳，美国普林斯顿大学教授，美国计算机科学家、数学家，美国科学院院士、美国工程院院士、美国人文科学院院士，图灵奖、基础科学终身成就奖获得者。 罗伯特·塔扬从小富于幻想，喜欢追求新鲜事物，幼时对天文学感兴趣，梦想成为第一个登上火星的人。1964 年，罗伯特·塔扬第一次接触到计算机，便产生兴趣。他在加州理工学院时不仅学习的是数学，还辅修了计算机。1969年，罗伯特·塔扬进入斯坦福大学研究生院学习，师从计算机科学家唐纳德·克努特。1970年，罗伯特·塔扬和约翰·霍普克罗夫特在一个办公室开始了对图论算法的共同研究。1972年，罗伯特·塔扬以平面图测试的高效算法为题完成了博士论文，获博士学位。学成以后，罗伯特·塔扬先是跟随约翰·霍普克罗夫特去了康奈尔大学，以后又先后在加州大学伯克利分校、母校斯坦福大学以及贝尔实验室工作过。1980年，罗伯特·塔扬在纽约大学当兼职教授。1987年，罗伯特·塔扬当选美国科学院院士。次年，他当选美国工程院院士。2012年4月，罗伯特·塔扬到访中国，接受了《中国科学报》的采访。2025年7月25日，罗伯特·塔扬参加在北京雁栖湖应用数学研究院举行的2025国际基础科学大会，在大会上他表示不要过度依赖AI，拥有思考能力才不会被AI取代。

主要成就

1986年，罗伯特·塔扬与约翰·霍普克罗夫特共同获得图灵奖，以表彰其在算法和数据结构的设计与分析领域做出的基础性贡献。

塔扬发明或合作发明了多个著名算法，包括用于解决最近公共祖先问题的Tarjan离线LCA算法、寻找有向图中强连通分量的Tarjan强连通分量算法，以及与霍普克罗夫特合作提出的首个线性时间平面图算法——Hopcroft-Tarjan平面嵌入算法。

在数据结构方面，塔扬开发或深入分析了斐波那契堆、与Daniel Sleator合作提出的伸展树，以及用于网络流算法的动态树。

他对并查集进行了开创性分析，首次证明了其反阿克曼函数的乐观时间复杂度。此外，塔扬提出了“分摊”算法的概念，将算法分析的重点从单个操作的最坏情况时间转向整个操作序列的平均时间，对算法设计与分析领域产生了深远影响。

塔扬还发明了“持久性数据结构”，该结构可用于高效访问数据的当前和历史状态，在计算几何和时态数据库中有重要应用。

主要作品

1983年，出版专著《Data structures and network algorithms》（数据结构和网络算法）。1972年，完成博士毕业论文《An Efficient Planarity Algorithm》。

荣誉奖项

罗伯特·塔扬因其在计算机科学领域的贡献获得了众多荣誉。1983年，他获得首届Rolf Nevanlinna奖（信息科学奖）。1984年，获得美国科学院研究创新奖。1986年，与约翰·霍普克罗夫特（John Hopcroft）共同获得图灵奖，以表彰其在数据结构和算法设计与分析领域的基础性贡献，获奖时年仅38岁，是最年轻的图灵奖得主之一。1987年，当选美国国家科学院院士。1988年，入选美国国家工程院院士。

1994年，当选为美国计算机协会（ACM）院士。2004年，获得欧洲科学院颁发的Blaise Pascal数学和计算机科学奖章。他至少拥有18项美国专利。2025年7月，在中国北京召开的2025国际基础科学大会上，获颁“基础科学终身成就奖”。

个人生活

罗伯特·塔扬1948年4月30日生于美国加利福尼亚州的波莫纳，从小就是一个富于幻想、追求新鲜事物的人。塔扬幼时对天文学很感兴趣，曾梦想成为第一个登上火星的人。

塔扬的母亲带他去图书馆，激发了他对科幻小说的浓厚兴趣，这些科幻小说点燃了他对科学的兴趣。八年级数学老师沃尔先生真正激发了他对数学的浓厚兴趣。塔扬读过中国科幻小说《三体》，三卷都读了，觉得它引人入胜，并称其“非常迷人”。

塔扬认为除了天赋，成功还需要“选择合适的时机”和“选择合适的地点”。在他看来，数学是一门“非常美丽”的艺术，被运用到计算机科学中以解决现实问题。面对研究中的失败，塔扬强调坚持，遇到难题时会暂缓并转换课题，之后再回头解决。他的科研信条包括恪守高标准、多角度审视问题、保持批判性思维，并认为最具价值的研究课题源于自主发现。

塔扬认为学校应该给学生提供探索不同学科的机会，不应过分关注分数，而应基于好奇心进行探索。高中时期，塔扬曾尝试用计算机证明四色定理。

个人经历

1964年，塔扬参加一个中学生科学夏令营，第一次接触计算机，立即被神奇的计算机所吸引。

1969年他取得学士学位以后，进入斯坦福大学研究生院，师从著名计算机科学家罗伯特·弗洛伊德（Robert Floyd），其博士论文委员会成员包括后来在1974年荣获图灵奖的唐纳德·克努特，以及当时正在斯坦福大学访学的约翰·霍普克罗夫特（John Hopcroft）。最初，塔扬选择的研究方向是人工智能。但那时，人工智能还处于早期阶段，整个研究领域都处于非常模糊的状态。在弗洛伊德、克努特等人的指导之下，塔扬最后锁定计算机算法为自己的研究领域，主攻算法和数据结构。1972年，塔扬以平面图测试的高效算法为题完成了博士论文，以优异成绩通过论文答辩取得博士学位，这时离他取得硕士学位（1971年）刚刚一年。

学成以后，塔扬先是跟随霍普克罗夫特去了康奈尔大学。其职业生涯中曾在康奈尔大学（1972-1973）、加州大学伯克利分校（1973-1975）、斯坦福大学（1974-1980）、纽约大学（1981-1985）等机构任职。曾工作于AT&T贝尔实验室（1980-1989）、NEC研究所（1989-1997）、InterTrust Technologies（1997-2001，2014至今）、康柏（2002）、惠普（2006-2013）等公司和研究机构。他自1985年起任教于普林斯顿大学。2013年4月加入微软硅谷研究院，并保留普林斯顿大学教职。2014年重新加入InterTrust Technologies（富信科技）担任首席科学家。

相关作品

2025年7月25日，罗伯特·塔扬接受中国中央广播电视总台《高端访谈》栏目专访。塔扬表示跨学科交流蕴藏着可能性，并认为人工智能取得了飞速发展但不具备人类的好奇心与探索欲，同时表示基础科学终身成就奖是对终身成就的褒奖。

2025年7月，罗伯特·塔扬接受CGTN（中国国际电视台）英语及西班牙语频道专访。塔扬谈及中国在人工智能领域的崛起、全球科学合作的重要性，并表达了对中国科幻小说《三体》的喜爱。

2020年11月14日，罗伯特·塔扬接受《中国科学报》采访，回顾了自己的成功之路、研究历程以及对数学与计算机科学关系的看法。

2012年，罗伯特·塔扬接受《中国计算机学会通讯》采访，访谈内容《用算法解决现实问题——访图灵奖获得者罗伯特·塔扬教授》发表于该刊2012年第5期。

2012年4月28日，《科学网》等媒体发表人物报道《图灵奖得主塔扬:在自己喜欢的领域坚持》，详细介绍了其早年经历、学术生涯与科研理念。

社会生活

2025年7月，塔扬出席在北京举办的2025国际基础科学大会，并获颁基础科学终身成就奖。会议期间及会后，他接受了中国国际电视台（CGTN）等媒体的专访。在专访中，塔扬谈及中国对基础科学和人工智能的长期投入，强调了中国的STEM教育体系、学生能力以及国际合作在推动科学发展中的价值。他表示，人工智能取得了快速发展，但不具备人类的好奇心与探索欲，并对“奇点”论持谨慎态度。同年4月，他曾做客清华大学海外名师讲堂，作题为《搜索树之谜》的特邀报告。在大会期间，塔扬提醒年轻人不要过度依赖AI，强调独立思考能力的重要性。塔扬在采访中还表示对中国科幻小说《三体》感兴趣，认为其引人入胜。

轶事趣闻

约翰·霍普克罗夫特是罗伯特·塔扬在斯坦福大学期间的博士生导师之一。

2025年，在2025国际基础科学大会上，中学生周子皓为基础科学终身成就奖得主罗伯特·塔扬绘制了肖像画，并在开幕式上亲手将作品献给塔扬。

塔扬曾表示读过中国科幻小说《三体》，并认为其引人入胜。在2025年基础科学终身成就奖颁奖典礼上，塔扬从上衣口袋里掏出折好的手写获奖致辞，并特别感谢已故父母。