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