Robert Andre Tarjan ; / ˈ r ɔː b ə t ˈ t ɑr dʒ æ n / [5] ; genus. April 30, 1948 , Pomona , USA ) - a famous American scientist in the field of theory of computer systems.
| Robert Andre Tarjan | |
|---|---|
| English Robert Endre Tarjan | |
 | |
| Date of Birth | April 30, 1948 (71 years old) |
| Place of Birth | Pomona ( California , USA ) |
| A country | |
| Scientific field | Computer science |
| Place of work | Princeton University Hewlett-packard |
| Alma mater | California Institute of Technology , Stanford University |
| supervisor | |
| Awards and prizes | Nevanlinna Prize (1982) Turing Award ( 1986 ) |
He is the author of many algorithms for solving problems in graph theory and discrete mathematics, including the Tarjan's off-line least common ancestors algorithm. He is also a co-author of the Fibonacci Heap and Expanding Tree data structures.
Content
Education
Robert Tarjan’s father was a pediatrician specializing in mental retardation and managed a state hospital [6] .
As a child, Taryan read a lot of science fiction and wanted to become an astronomer. He became interested in mathematics after reading Martin Gardner 's notes on mathematical games in Scientific American . A serious interest in mathematics was instilled in the eighth grade by a "very motivating" teacher.
While studying at school, Taryan was lucky to work at IBM with a sorting and sorting machine for punch cards. In 1964, at a summer school, he received his first serious experience working with real computers [6] .
Taryan received his bachelor's degree in mathematics from the California Institute of Technology in 1969 . At Stanford University, he received a master's degree in computer science ( 1971 ) and a Ph.D. (Doctor of Philosophy) in computer science - in 1972 , Robert Floyd and Donald Knut , his research supervisors at Stanford, called “An Effective Algorithm for Determining Graph Planarity” "(An Efficient Planarity Algorithm) [7] . Taryan chose computer science as the way in which mathematics can bring tangible practical benefits [8] .
Career
Tarjan has been a teacher at Princeton University since 1985. [8] He also had academic positions at Cornell University (1972-1973), the University of California at Berkeley (1973-1975), Stanford University (1974-1980), and New York University (1981-1985). He was also a member of the NEC Research Institute (1989-1997) and is listed (as Visiting Scientist) at the University of Massachusetts (1996).
Taryan worked at AT&T Bell Labs (1980–1989), InterTrust Technologies (1997–2001), Compaq (2002), and Hewlett Packard, where he continued to work since 2006. He was elected a member of various ACM and IEEE committees, and also worked as an editor of several refereed magazines.
Algorithms and data structures
Tarjan came up with many effective algorithms and data structures for solving various applied problems. He has published over 228 articles in refereed journals and monographs.
Tarjan is known for his revolutionary work in the field of graph algorithms. The most striking of them are the Taryan Offline Algorithm for finding the nearest common ancestor for multiple quick searches of the deepest tree node, which is the common ancestor of two given nodes, and the Taryan Algorithm for calculating strongly connected components . The Hopcroft – Taryan algorithm became the first linear algorithm for determining the planarity of a graph [9] .
Tarjan developed a number of critical data structures, such as the Fibonacci Heap , the System of Disjoint Sets , and the Splay Tree (a type of balanced binary search tree; co-authored by Daniel Slitor).
Today, Robert Tarjan is Emeritus Professor of Computer Science ( James S. McDonnell Distinguished University Professor of Computer Science) at Princeton University, and also works at Hewlett-Packard [10] .
Rewards
Taryan received the Turing Award with John Hopcroft in 1986. In the accompanying text for the award it says:
- For fundamental results in the development and analysis of algorithms and data structures.
Tarjan was also elected a member of ACM (ACM Fellow) in 1994. The congratulatory text [1] states:
- For fruitful work in the development and analysis of algorithms and data structures.
Other Robert Tarjan Awards:
- Guggenheim Scholarship (1978) [11]
- Nevanlinna Prize (1982) - First Prize Winner
- National Academy of Sciences Award for Initiatives in Research (1984)
- Paris Kanellakis Award in Theory and Practice, ACM (1999)
- Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences (2004)
At the end of February 2009, Taryan was ranked 39th in the list of most cited authors in the CiteSeer project [12] .
Notes
- ↑ http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations
- ↑ http://www.in.com/robert-tarjan/profile-238439.html
- ↑ http://link.springer.com/content/pdf/10.1007%2F978-3-642-15328-0_9.pdf
- ↑ Mathematical Genealogy - 1997.
- ↑ https://forvo.com/word/robert_tarjan/
- ↑ 1 2 Shasha, Dennis Elliott. Robert E. Tarjan: In Search of Good Structure // Out of Their Minds: The Lives and Discoveries of 15 Great Computer. - 1998 .-- P. 102-119. - ISBN 978-0387979922 .
- ↑ Robert Endre Tarjan . Mathematics Genealogy Project. Date of treatment January 9, 2008. Archived March 17, 2012.
- ↑ 1 2 Robert Endre Tarjan: The art of the algorithm (interview ) . Hewlett-Packard (September 2004). Date of treatment January 9, 2008. Archived March 17, 2012.
- ↑ Kocay, William. Planar Graphs // Graphs, algorithms, and optimization. - Boca Raton, 2005. - P. 312. - ISBN 978-1584883968 .
- ↑ HP Fellows: Robert Endre Tarjan (English) (link not available) . Hewlett-Packard. Date of treatment January 9, 2008. Archived March 17, 2012.
- ↑ Robert E. Tarjan . John Simon Guggenheim Foundation . gf.org. Date of treatment April 9, 2019.
- ↑ Statistics - Most Cited Authors in Computer Science
Bibliographic references
- Tarjan, Robert E. Data structures and network algorithms. - Philadelphia, 1983. - ISBN 978-0898711875 .
- Tarjan, Robert E. Notes on introductory combinatorics. - Boston, 1983. - ISBN 978-0817631703 .
- OCLC entries for Robert E Tarjan
- DBLP entry for Robert Endre Tarjan