罗伯特·塔扬：高效算法的语法
让任何计算机科学专业的学生用深度优先搜索来遍历图，无论他们是否意识到，他们都在执行一种由罗伯特·塔扬从一种好奇心转变为一门学科的技术。他1972年的论文《深度优先搜索与线性图算法》（Depth-first search and linear graph algorithms）读起来就像一本基础语法书——这种工作已经如此彻底地融入了该领域，以至于作者的名字几乎从人们谈论它的方式中消失了，尽管他的名字与他们每天使用的半打结构联系在一起。
一位数学家通往机器的道路
罗伯特·恩德雷·塔扬（Robert Endre Tarjan）于1948年4月30日出生在加利福尼亚州波莫纳，父亲乔治·塔扬是一位专门研究智力障碍的儿童精神科医生；他的弟弟詹姆斯后来成为了一名国际象棋特级大师。塔扬小时候想成为一名天文学家，直到《科学美国人》杂志上马丁·加德纳的谜题专栏和一位鼓舞人心的八年级老师将他引向了数学。他于1969年在加州理工学院获得数学学士学位，随后于1971年在斯坦福大学获得计算机科学硕士学位，并于1972年获得博士学位，论文是在罗伯特·弗洛伊德和唐纳德·克努特的指导下关于平面性算法的研究。他后来简单地描述了他对领域的选择：计算机科学是一种可以产生实际影响的数学研究方式——这句话也同样可以作为他全部工作的描述。
构建工具包
塔扬的职业生涯跨越了康奈尔大学、加州大学伯克利分校、斯坦福大学、AT&T贝尔实验室、纽约大学、NEC研究所、微软研究院、康柏、惠普和Intertrust Technologies，并于1985年在普林斯顿大学担任詹姆斯·S·麦克唐纳杰出大学教授。他产生了一系列算法和数据结构，其不同寻常之处在于其中许多成为了承重基础设施，而非理论上的好奇心。他的名字与用于查找图中强连通分量的塔扬算法、用于计算最小公共祖先的离线算法以及用于查找桥的线性时间算法联系在一起——所有这些技术都建立在他形式化的深度优先搜索框架之上。1975年，他给出了结合路径压缩的并查集数据结构的第一次精确分析，利用逆阿克曼函数证明了其近乎恒定的摊销运行时间，这一结果与现实世界的性能紧密相关，以至于现在它构成了从克鲁斯卡尔最小生成树算法到编译器优化的所有基础。在贝尔实验室，他与丹尼尔·斯莱托共同发明了伸展树，这是一种通过使用而非携带显式平衡元数据来重新平衡的自调整二叉搜索树，并以此开创了竞争分析，这是一个用于在全知对手面前评判在线算法的框架。1985年，他与迈克尔·弗雷德曼共同开发了斐波那契堆，这是一种优先级队列结构，使得迪杰斯特拉最短路径算法和网络优化算法在渐近速度上比以往任何时候都快。他的教科书《数据结构与网络算法》（Data Structures and Network Algorithms）赢得了弗雷德里克·W·兰开斯特奖，并成为该领域的标准读物。
与霍普克罗夫特在平面性上的突破
在他的图灵奖引文中被最明确提及的单一成就是与约翰·霍普克罗夫特共同完成的工作：1974年发表的用于测试图是否可以在平面上绘制且没有任何边交叉的第一个线性时间算法。在他们的算法将其简化为仔细的深度优先遍历问题之前，平面性测试一直是一个缓慢且笨拙的问题——这种技术对他们的解决方案至关重要，以至于塔扬之前对深度优先搜索的形式化，回想起来，成为了使霍普克罗夫特-塔扬结果成为可能的工具。两人共同获得了1986年ACM图灵奖，“以表彰他们在算法和数据结构设计与分析方面的根本性成就”，这一引文肯定的是共同和并行的工作成果，而非任何单一论文。
四十年的认可
塔扬是1983年第一届内万林纳信息科学奖的获得者，以表彰其对计算机科学数学方面的杰出贡献。他于1986年获得图灵奖，1985年当选为美国艺术与科学院院士，1987年当选为美国国家科学院院士，1988年当选为美国国家工程院院士。他于1999年获得巴黎·卡内拉基斯理论与实践奖，并于2010年获得加州理工学院杰出校友奖。他的出版记录超过250篇论文，引用次数达数万次，并拥有十几项关于数据结构和安全性的美国专利，反映了他职业生涯在普林斯顿的学术理论与贝尔实验室、NEC和微软等工业实验室的应用研究之间流畅转换。
为什么罗伯特被称为天才
塔扬被称为天才的理由基于具体的事实：他不仅解决了单个难题，他还识别出了底层的组合机制——深度优先搜索、摊销分析、自调整——这些机制使得整类以前缓慢的算法变得快速，而且他不是只做了一次，而是在四十年里反复这样做。并查集分析和霍普克罗夫特-塔扬平面性算法之所以仍然是教科书材料，正是因为它们不是巧妙的技巧，而是其他研究人员可以重用的通用技术；这种可重用性，比任何单一结果都更重要，正是内万林纳奖和图灵奖委员会所奖励的内容。诚实的复杂之处在于，他最著名的结果，即线性时间平面性算法，明确是与约翰·霍普克罗夫特共同完成的工作，图灵奖的引文共同肯定了两人，而不是将其中任何一人加冕为孤独的天才——奖项本身就是该领域将其视为协作成就而非单一发明的证明。塔扬的其他里程碑式结果同样是与署名的合著者共同构建的：伸展树与丹尼尔·斯莱托，斐波那契堆与迈克尔·弗雷德曼。无可争议的是，以他的名字命名的基础性、至今仍在教授的成果密度之高，这是该领域极少数人能与之匹敌的记录。
遗产
每一位学习深度优先搜索、并查集、伸展树或斐波那契堆的计算机科学学生，实际上仍然在接受塔扬论文的教导，尽管这些论文写于几十年前。他的工作位于编译器、网络路由和地理信息系统之下，而大多数用户甚至不知道他的名字——这是基础设施级数学完全成功后的安静命运。他一直到七十多岁还在产生新的成果，在普林斯顿教职与Intertrust Technologies首席科学家以及微软和惠普的研究员角色之间转换，这种职业形态本身就反对将他视为纯粹的学术人物：他许多被引用最多的工作是在工业研究实验室中完成、测试和应用的，而不是在大学的真空中。这种双重生活，在发表严谨数学的同时申请实用系统的专利，是他与那些思想仅限于期刊的理论家区别开来的部分原因。
