图灵奖：罗伯特·塔扬（1986）

图灵奖是计算机界最负盛名的奖项，有“计算机界诺贝尔奖”之称。”图灵奖”系列将介绍历届获奖者。每周二更新，本文为第 25 期。图灵奖：罗伯特·塔扬（1986）

文章来自微信公众号“科文路”，欢迎关注、互动。转发须注明出处。

本文来自 wiki:Robert Tarjan，翻译基于 谷歌翻译.

中国的老朋友，上过《开讲啦》

罗伯特·恩德烈·塔扬（Robert Endre Tarjan，1948 年 4 月 30 日出生）是一位美国计算机科学家和数学家。 他是多个图论算法的发现者，包括强连通分量算法，也是展开树和斐波那契堆的共同发明者。 Tarjan 目前是普林斯顿大学计算机科学系 James S. McDonnell 杰出教授。

他于 1986 年获得图灵奖。

其图灵奖颁奖词为“与 John E Hopcroft 一起，在算法和数据结构的设计和分析方面取得了基础性成就”。（With John E Hopcroft, for fundamental achievements in the design and analysis of algorithms and data structures.）

生平

塔扬出生于加利福尼亚州波莫纳。小时候，塔扬读了很多科幻小说，并想成为一名天文学家。在阅读《科学美国人》上马丁·加德纳的数学游戏专栏后，他对数学产生了兴趣。

塔扬于 1969 年获得加州理工学院数学学士学位。1971 年在斯坦福大学获得计算机科学硕士学位，1972 年获得计算机科学博士学位（辅修数学），他的博士论文是一种高效的平面算法（An Efficient Planarity Algorithm）

在斯坦福大学，他的导师是 Robert Floyd 和 Donald Knuth。 。

算法和数据结构

塔扬以其在图论算法和数据结构方面的开创性工作而闻名。 他的一些著名算法包括 Tarjan 的离线最小公共祖先算法和 Tarjan 的强连通分量算法，他是中位数线性时间选择算法的五位合著者之一。 Hopcroft-Tarjan 平面度测试算法是第一个用于平面度测试的线性时间算法。

塔扬还开发了重要的数据结构，例如斐波那契堆（一种由树木组成的堆数据结构）和展开树（一种自我调整的二叉搜索树；由 Tarjan 和 Daniel Sleator 共同发明）。 另一个重要贡献是对不相交集数据结构的分析； 他是第一个证明涉及逆阿克曼函数的最佳运行时间的人。

~~

都看到这儿了，不如关注每日推送的“科文路”、互动起来~

至少点个赞再走吧~

觉得还不错？可以在公众号菜单栏找到“赞赏”入口~