图灵奖:罗伯特·塔扬(1986)

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

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

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

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 共同发明)。 另一个重要贡献是对不相交集数据结构的分析; 他是第一个证明涉及逆阿克曼函数的最佳运行时间的人。

~~

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

至少点个赞再走吧~

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

图灵奖:罗伯特·塔扬(1986)

https://xlindo.com/kewenlu2023/posts/a724ce79/

Author

xlindo

Posted on

2023-11-14

Updated on

2024-01-16

Licensed under

Comments