1986 罗伯特·塔扬

shiyi18

Robert E Tarjan

PHOTOGRAPHS
BIRTH:
April 30, 1948, Pomona, California

EDUCATION:
B.S., California Institute of Technology (1969, Mathematics); MS Stanford University (1971, Computer Science); Ph.D., Stanford University (1972, Computer Science with minor in Mathematics).

EXPERIENCE:
Assistant Professor of Computer Science, Cornell University (1972 – 1973); Miller Research Fellow, University of California, Berkeley, California (1973 – 1975); Stanford University Assistant Professor of Computer Science (1974 – 1977), Associate Professor of Computer Science (1977 – 1980); Member of Technical Staff, AT&T Bell Laboratories, Murray Hill, New Jersey (1980 – 1989); Adjunct Professor of Computer Science, New York University (l98l – 1985); James S. McDonnell Distinguished University Professor of Computer Science, Princeton University (from 1985); Co-Director, National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) (1989-1994, 2001 -); Fellow, NEC Research Institute, Princeton, New Jersey (1989 – 1997); Visiting Scientist, Massachusetts Institute of Technology (1996); Chief Scientist, InterTrust, and Senior Research Fellow, STAR Labs, InterTrust Technologies Corporation, Sunnyvale, CA (1997 – 2001); Corporate Fellow, Compaq Computer Corporation, Houston, TX (2002), Chief Scientist (2002-2003); Senior Fellow (from 2003), Hewlett Packard Corporation, Palo Alto, CA

HONORS AND AWARDS:
Miller Research Fellowship, University of California, Berkeley,
California (1973-1975); Guggenheim Fellowship (1978-1979); Nevanlinna Prize in Information Science (1983); National Academy of Sciences Award for Initiatives in Research (1984); Honorable Mention, Lanchester Prize of the Operations Research Society of America (1984); Fellow, American Academy of Arts and Sciences (1985); AT&T Bell Laboratories, Distinguished Member of Technical Staff (1985); A. M. Turing Award of the Association for Computing Machinery (1986); Member, National Academy of Sciences (1987); Member, National Academy of Engineering (1988); Fellow, American Association for the Advancement of Science (1990); Member, American Philosophical Society (1990); Foundation Fellow, Institute for Combinatorics and its Applications (1991); Honorable Mention, Lanchester Prize of the Operations Research Society of America (1993); Fellow, Association for Computing Machinery (1994); Fellow, New York Academy of Sciences (1994); Paris Kanellakis Award in Theory and Practice, Association for Computing Machinery (1999); Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences (2004); Fellow, Society for Industrial and Applied Mathematics (2009); Edelman Award, INFORMS, member of winning HP team (2009); Caltech Distinguished Alumni Award, California Institute of Technology (2010).


ROBERT (BOB) ENDRE TARJAN DL Author Profile link
United States – 1986
CITATION
With John E Hopcroft, for fundamental achievements in the design and analysis of algorithms and data structures.

SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
ADDITIONAL
MATERIALS
VIDEO INTERVIEW
Bob Tarjan was born on April 30, 1948 in Pomona, California. He received a B.S. in mathematics from Caltech in 1969, and was determined to do a Ph.D. but was undecided between mathematics and computer science. He finally chose computer science as a way to use his mathematical skills to solve problems of more practical interest. He entered Stanford to study artificial intelligence, but, guided by his course advisor Don Knuth, he was soon reading Volume 1 of Knuth’s The Art of Programming and studying the analysis of algorithms.

At Stanford Tarjan began a collaboration with John Hopcroft on developing efficient algorithms for graph problems. At the time there was no commonly used model for measuring efficiency analytically. Hopcroft and Tarjan decided that the model of computation would be a hypothetical computer in which the goal of the algorithm design was to minimize the worst case running time. Constant factors in the running time were ignored, so as to be machine independent. Their example problem was testing the planarity of a graph, that is, whether it can be drawn in a plane so that no edges cross.

Tarjan recalls his collaboration with John Hopcroft, begun as a Stanford graduate student, to develop efficient graph algorithms.       
This work led to the first linear time algorithm for planarity, which was the subject of Tarjan's Ph.D. thesis completed under the supervision of Robert W. Floyd in 1972. It emphasized depth-first search as an important algorithmic technique and advocated the use of an adjacency-list representation for sparse graphs, rather than an adjacency matrix. Other applications of the depth-first search method followed shortly, including Tarjan's linear time algorithm for finding strongly connected components. These techniques are now covered in most undergraduate courses in algorithm design. Tarjan and Hopcroft jointly received the Turing award for this and related work in 1986.

Also now part of the algorithmic canon is Tarjan's work on data structures. Tarjan realized that designing a data structure to minimize the worst case running time for each operation was unnecessarily limiting; what mattered was the total running time of the sequence of operations. Alternatively, from the point of view of the data structure, one could study the algorithm’s amortized running time, that is, its average running time per operation over a long enough sequence of inputs.

An early and well-known example of this work is Tarjan's analysis of the “union-find” data structure. [3]  The union-find problem is to maintain a collection of disjoint sets so as to efficiently perform two operations: union, which joins two sets into a single set, and find, which returns the set containing a specified element. Representing each set as a tree, two simple methods were used to give improved performance: union by weight and path compression, but their impact was not completely understood. In 1975, Tarjan was the first to analyze their combined performance exactly, showing an almost constant time per operation over long enough sequences.  This nontrivial analysis gives a time which was proportional to inverse Ackermann's function of the number of operations and elements. This was later shown to be optimal.

Tarjan summarizes his analysis of the “union-find” data structure.       
Tarjan held academic positions at Cornell University and then at the University of California in Berkeley before returning to Stanford University in 1974. At Stanford, Tarjan and his student Danny Sleator worked on obtaining faster solutions for the maximum flow problem by efficiently maintaining information about residual flow. They also devised the dynamic tree structure, a forest of disjoint trees in an edge-weighted graph, where trees can be split into two or linked together, and, for any path in a tree, the minimum weight edge in the path can be retrieved. Each operation runs in time which is logarithmic in the size of the tree. Underlying this data structure is a balanced ordered binary tree.

After Tarjan and Sleator moved to AT&T Bell Laboratories in 1980, they discovered a simpler means to maintain balanced binary trees, and created the “self-adjusting” binary search tree known as a splay tree. At the time, many kinds of balanced binary search trees were known which would enable lookups, inserts, deletes and other operations to be done in a worst case time which is logarithmic in the size of the tree. However maintaining these balanced trees required extra space for balance information, and complicated algorithms. The splay tree is simpler and requires no extra balance information, but has amortized running time (rather than worst case running time) which is logarithmic in the size of the tree. Whether splay trees perform as well as any binary search trees up to a constant factor is a question still unresolved. Known as the dynamic optimality conjecture, this open problem continues to inspire new research.

Tarjan explains the concept of probabilistic automata and his work with Danny Sleator on the maximum flow problem, which led to the development of splay trees.       
Tarjan's book Data Structures and Network Algorithms [6] beautifully presents his work on disjoint sets, tree data structures, minimum spanning trees, matching, and maximum flow problems. Regarded as a ``model of precision and clarity", it received the Frederick W. Lancester Prize in 1984.

Again exploiting the fact that data structures with good amortized performance would suffice, Tarjan and Michael Fredman devised the Fibonacci heap, a priority queue which implements all standard heap operations except deletion in constant amortized time. Appearing in 1985, this data structure provided significant speed-ups to several important combinatorial problems including minimum spanning tree, shortest paths, and the assignment problem.

In a seminal paper [7] in 1985, Tarjan and Sleator studied the performance of “online algorithms”, which process inputs as they happen without seeing them all at the same time, and compared them to “offline algorithms” that get to see the whole input stream at once. They introduced the notion of “competitive analysis” to rate online algorithms compared to the optimal offline algorithm, where worst-case data is imagined to be generated by an “adversary”.

They used two example problems, the list update problem and the paging problem. The list update problem is as follows: given a list of items where the cost of accessing an item is its distance from the front of the list, come up with a strategy of reordering the list so that the total cost for a sequence of access requests is minimized. Their paper shows that if each requested item is moved to the front (at constant cost) then the cost of servicing any online sequence of requests is no more than twice the cost of the optimal offline strategy that knows all future requests. The paging problem is to determine a strategy for moving pages out of cache so as to minimize the number of cache faults.

Tarjan remained at AT&T until 1989, while also serving as an adjunct professor at New York University from 1981-85. At NYU, Tarjan and his student Neal Sarnak began the first systematic study of persistent data structures—data structures which preserve the previous version of themselves when modified. This initial work resulted in a publication [11] with Jim Driscoll, Danny Sleator, and later several others with Tarjan's student Haim Kaplan at Princeton.

In 1985 Tarjan joined the faculty at Princeton University, where he is currently the James S. McDonnell Distinguished University Professor. He remained actively involved in industry at NEC Research Institute, Intertrust and the Compaq/HP Research Labs.

Tarjan returned several times to work on maximum flow and other network flow problems, with Andrew Goldberg and others. In 1995, Tarjan, with David Karger and Phil Klein, published the first linear expected time algorithm for the minimum spanning tree problem [12].

Tarjan describes his work with Karger and Klein to create a linear expected time minimum spanning tree algorithm.       
Tarjan has written over 250 papers with over 190 co-authors, and holds 15 patents. He continues to work in the area of combinatorial algorithms and data structures. In the spirit of Paul Erdös, he searches and inspires others to search for algorithms from “The Book" that records God’s best and most elegant mathematical proofs and algorithms.

Author: V. King



Robert E Tarjan

照片
诞生。
1948年4月30日，加利福尼亚，波莫纳

学历
加州理工学院学士（1969年，数学）；斯坦福大学硕士（1971年，计算机科学）；斯坦福大学博士（1972年，计算机科学，副修数学）。

工作经验。
康奈尔大学计算机科学助理教授（1972-1973）；加州大学伯克利分校米勒研究员（1973-1975）；斯坦福大学计算机科学助理教授（1974-1977），计算机科学副教授（1977-1980）；AT&T贝尔实验室技术工作人员，新泽西州默里山（1980-1989）；纽约大学计算机科学兼职教授（1998l-1985）；詹姆斯．McDonnell 特聘大学计算机科学教授，普林斯顿大学（1985年起）；国家科学基金会离散数学和理论计算机科学中心（DIMACS）联合主任（1989-1994，2001-）；NEC研究所研究员，普林斯顿，新泽西（1989-1997）。麻省理工学院访问科学家（1996年）；InterTrust首席科学家和STAR实验室高级研究员，InterTrust技术公司，加州桑尼维尔（1997-2001年）；康柏电脑公司企业研究员，德州休斯顿（2002年），首席科学家（2002-2003年）；惠普公司高级研究员（2003年起），加州帕洛阿尔托市

荣誉和奖项。
米勒研究奖学金，加州大学伯克利分校。
加州大学伯克利分校米勒研究奖学金（1973-1975）；古根海姆奖学金（1978-1979）；Nevanlinna信息科学奖（1983）；国家科学院研究倡议奖（1984）；美国运筹学会兰彻斯特奖荣誉奖（1984）；美国艺术与科学学院院士（1985）；AT&T贝尔实验室杰出技术员（1985）；A. M．图灵奖（1986）；国家科学院院士（1987）；国家工程院院士（1988）；美国科学促进会研究员（1990）；美国哲学学会会员（1990）；组合学及其应用研究所基金会研究员（1991）；美国运筹学会兰彻斯特奖荣誉奖（1993）。计算机械协会研究员（1994年）；纽约科学院研究员（1994年）；计算机械协会巴黎卡内拉基斯理论与实践奖（1999年）；欧洲科学院布莱斯-帕斯卡尔数学与计算机科学奖（2004年）；工业与应用数学学会研究员（2009年）；INFORMS爱德曼奖，惠普获奖团队成员（2009年）；加州理工学院杰出校友奖（2010年）。


ROBERT (BOB) ENDRE TARJAN DL作者简介链接
美国 - 1986年
参考文献
与John E Hopcroft一起，在算法和数据结构的设计和分析方面取得了基本成就。

短篇注释
书目
亚马逊图灵奖
讲座
研究
主题
额外的
材料
采访视频
Bob Tarjan于1948年4月30日出生在加利福尼亚的波莫纳。他于1969年获得加州理工学院的数学学士学位，并决心攻读博士学位，但在数学和计算机科学之间犹豫不决。他最终选择了计算机科学，因为这是用他的数学技能来解决更多实际问题的一种方式。他进入斯坦福大学学习人工智能，但在他的课程顾问Don Knuth的指导下，他很快就阅读了Knuth的《编程的艺术》第一卷，并研究算法的分析。

在斯坦福大学，塔尔扬开始与约翰-霍普克罗夫特合作，为图形问题开发有效的算法。当时还没有一个常用的模型来分析测量效率。霍普克罗夫特和塔尔扬决定，计算的模型将是一台假设的计算机，其中算法设计的目标是使最坏情况下的运行时间最小。运行时间中的恒定因素被忽略了，以便与机器无关。他们的例子是测试一个图形的平面性，也就是说，它是否可以被画在一个平面上，以便没有边缘交叉。

Tarjan回忆起他与John Hopcroft的合作，从斯坦福大学的研究生开始，开发高效的图形算法。       
这项工作导致了第一个关于平面性的线性时间算法，这是1972年在Robert W. Floyd指导下完成的Tarjan的博士论文的主题。该论文强调深度优先搜索是一项重要的算法技术，并主张对稀疏图使用邻接列表表示，而不是邻接矩阵。深度优先搜索方法的其他应用很快就出现了，包括Tarjan的寻找强连接组件的线性时间算法。这些技术现在在大多数算法设计的本科课程中都有涉及。1986年，Tarjan和Hopcroft因这项工作和相关工作共同获得了图灵奖。

现在，塔扬在数据结构方面的工作也是算法大全的一部分。Tarjan意识到，设计一个数据结构以最小化每个操作的最坏情况的运行时间是不必要的限制；重要的是操作序列的总运行时间。另外，从数据结构的角度来看，我们可以研究算法的摊销运行时间，也就是说，在足够长的输入序列中，每个操作的平均运行时间。

这项工作的一个早期和著名的例子是Tarjan对 "联合查找 "数据结构的分析。[3] Union-find问题是维护一个互不相干的集合，以便有效地执行两个操作：union和find，前者将两个集合连接成一个单一的集合，后者则返回包含指定元素的集合。将每个集合表示为一棵树，有两种简单的方法被用来提高性能：按重量联合和路径压缩，但它们的影响并没有被完全理解。1975年，Tarjan是第一个精确分析它们的组合性能的人，显示在足够长的序列上每个操作的时间几乎是恒定的。 这个非微不足道的分析给出了一个时间，它与操作和元素数量的逆阿克曼函数成正比。这后来被证明是最佳的。

Tarjan总结了他对 "union-find "数据结构的分析。       
Tarjan在康奈尔大学担任学术职务，然后在加州大学伯克利分校任职，1974年回到斯坦福大学。在斯坦福大学，Tarjan和他的学生Danny Sleator致力于通过有效地维护剩余流量的信息来获得最大流量问题的快速解决方案。他们还设计了动态树结构，这是一个边缘加权图中不相交的树的森林，树可以被分割成两个或连接在一起，对于树中的任何路径，可以检索到路径中的最小权重边缘。每个操作的运行时间都与树的大小成对数关系。这个数据结构的基础是一个平衡的有序二叉树。

1980年Tarjan和Sleator转到AT&T贝尔实验室后，他们发现了一种更简单的维护平衡二进制树的方法，并创造了被称为splay树的 "自我调整 "二进制搜索树。当时，许多种类的平衡二进制搜索树是已知的，它们可以在最坏的情况下完成查找、插入、删除和其他操作，其时间是树的大小的对数。然而，维护这些平衡树需要额外的空间来存放平衡信息，并且需要复杂的算法。splay树更简单，不需要额外的平衡信息，但有摊销的运行时间（而不是最坏情况下的运行时间），这与树的大小成对数关系。splay树的性能是否与任何二进制搜索树一样好，直到一个恒定的因素，这是一个仍未解决的问题。这个问题被称为动态最优性猜想，这个开放的问题继续激励着新的研究。

Tarjan解释了概率自动机的概念以及他与Danny Sleator在最大流量问题上的工作，这导致了splay树的发展。       
Tarjan的书《数据结构和网络算法》[6]漂亮地介绍了他在离散集、树数据结构、最小生成树、匹配和最大流量问题上的工作。该书被认为是 "精确和清晰的典范"，在1984年获得了弗雷德里克-W-兰塞特奖。

Tarjan和Michael Fredman再次利用具有良好摊销性能的数据结构这一事实，设计了Fibonacci堆，这是一个优先级队列，实现了除删除之外的所有标准堆操作的恒定摊销时间。这种数据结构出现在1985年，为几个重要的组合问题提供了显著的速度，包括最小生成树、最短路径和分配问题。

在1985年的一篇开创性的论文[7]中，Tarjan和Sleator研究了 "在线算法 "的性能，这些算法在输入发生时进行处理，而不是同时看到所有的输入，并将它们与能够一次看到整个输入流的 "离线算法 "进行比较。他们引入了 "竞争分析 "的概念，将在线算法与最佳离线算法进行比较，其中最坏情况下的数据被想象为由 "对手 "产生。

他们使用了两个实例问题，即列表更新问题和分页问题。列表更新问题如下：给定一个项目列表，访问一个项目的成本是它与列表前面的距离，想出一个重新排列列表的策略，使一连串访问请求的总成本最小。他们的论文表明，如果每个被请求的项目都被移到前面（成本不变），那么服务任何在线请求序列的成本不超过知道所有未来请求的最佳离线策略的两倍。分页问题是确定一个将页面从缓存中移出的策略，以使缓存故障的数量最小化。

Tarjan一直在AT&T工作到1989年，同时还在1981-85年期间担任纽约大学的兼职教授。在纽约大学，Tarjan和他的学生Neal Sarnak开始了对持久性数据结构的首次系统研究--这些数据结构在被修改后会保留其先前的版本。这项最初的工作导致了与Jim Driscoll、Danny Sleator，以及后来与Tarjan的学生Haim Kaplan在普林斯顿发表了一篇出版物[11]。

1985年，Tarjan加入了普林斯顿大学的教师队伍，目前他是James S. McDonnell的杰出大学教授。他在NEC研究所、Intertrust和Compaq/HP研究实验室仍然积极参与工业界的工作。

Tarjan多次返回，与Andrew Goldberg等人一起研究最大流量和其他网络流量问题。1995年，Tarjan与David Karger和Phil Klein合作，发表了第一个最小生成树问题的线性预期时间算法[12]。

Tarjan描述了他与Karger和Klein一起创建一个线性预期时间最小生成树算法的工作。       
Tarjan已经写了250多篇论文，有190多个合著者，并拥有15项专利。他继续在组合算法和数据结构领域工作。本着保罗-埃尔德斯的精神，他从记录了上帝最好和最优雅的数学证明和算法的 "书 "中寻找并激励其他人寻找算法。

作者。V. 金