Robert Tarjan
Robert "Bob" Endre Tarjan (born April 30, 1948 in Pomona , California ) is an American computer scientist . In 1986 he and John E. Hopcroft received the Turing Award for the design and analysis of algorithms and data structures .
He is a professor at Princeton University and works for the American company Hewlett-Packard .
Various algorithms are named after him:
- Tarjan's algorithm for determining strongly connected components
- Tarjan algorithm for the determination of a minimal spanning tree
- Hopcroft and Tarjan algorithms
- Goldberg-Tarjan algorithm for determining a maximum st-flow
He also introduced the data structures Fibonacci heap and Splay tree .
Life
Tarjan studied mathematics at Caltech in Pasadena, California, and completed his bachelor's degree in 1969. He moved to Stanford University , where he received his Masters in Computer Science in 1971 and his Ph.D. in 1972. in computer science with a minor in mathematics. His thesis on Efficient Planarity Algorithm was supervised by Robert Floyd , the lectures by Donald Ervin Knuth .
He was then a research fellow at Cornell University for a year , then a Miller Research Fellow for two years at the University of California, Berkeley , and a research fellow from 1974 to 1977 and then until 1980 associate professor of computer science at Stanford University. 1981 to 1985 he was an adjunct professor at New York University . Since 1985 he has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. From 1989 to 1994, and again since 2001, he is also Co-Director of the National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science . In 1996 he was visiting professor at MIT .
At the same time, he began a career in industry in 1980, initially being a Member of Technical Staff at AT&T Bell Laboratories until 1989 , then a Fellow of the NEC Research Institute until 1997 , and then Chief Scientist of InterTrust Technologies until 2001 . In 2002 he was a brief Corporate Fellow of Compaq , and when it was taken over by Hewlett-Packard, he became Chief Scientist there, and from 2003 a Senior Fellow.
Among Tarjan's 25 doctoral students are the Germans Thomas Lengauer and Monika Henzinger .
Awards
- 1978–1979: Guggenheim grant
- 1983: Nevanlinna Prize ( Prize lecture at the ICM in Warsaw: Efficient algorithms for network optimization )
- 1984: NAS Award for Initiatives in Research ; Frederick W. Lanchester Prize
- 1985: Fellow of the American Academy of Arts and Sciences
- 1986: Turing Award
- 1987: Member of the National Academy of Sciences
- 1988: Member of the National Academy of Engineering
- 1990: Fellow of the American Association for the Advancement of Science and Member of the American Philosophical Society
- 1994: Fellow of the ACM and the New York Academy of Sciences
- 1999: Paris Kanellakis Award
- 2004: Blaise Pascal Medal
- 2009: Fellow of the Society for Industrial and Applied Mathematics
Fonts
- Data Structures and Network Algorithms, CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983, ISBN 0-89871-187-8 .
- with G. Polya , DR Woods: Notes on Introductory Combinatorics. Birkhauser, Boston, MA, 1983.
Web links
- Website at Princeton University (English)
Individual evidence
- ^ Frederick W. Lanchester Prize. informs.org ( Institute for Operations Research and the Management Sciences ), archived from the original on October 2, 2015 ; accessed on February 16, 2016 .
| personal data | |
|---|---|
| SURNAME | Tarjan, Robert |
| ALTERNATIVE NAMES | Tarjan, Robert Endre (full name); Tarjan, Bob (nickname) |
| BRIEF DESCRIPTION | American computer scientist |
| DATE OF BIRTH | April 30, 1948 |
| PLACE OF BIRTH | Pomona , California |