Tarjan, Robert

Robert Tarjan
engelsk  Robert E Tarjan
Fødselsdato 30. april 1948 (74 år)( 30-04-1948 )
Fødselssted Pomona ( Californien , USA )
Land
Videnskabelig sfære Informatik
Arbejdsplads Princeton
Hewlett-Packard University
Alma Mater Caltech ,
Stanford University
Akademisk grad PhD fra Stanford (1972)
videnskabelig rådgiver Robert Floyd [4]
Præmier og præmier Nevanlinna-prisen (1982)
Turing-prisen ( 1986 )
 Mediefiler på Wikimedia Commons

Robert Andre Tarjan ( eng.  Robert Endre Tarjan ; / ˈ r ɔː b ə t ˈ t ɑr dʒ æ n / [5] ; født 30. april 1948 , Pomona , USA ) er en amerikansk computerforsker.

Han er forfatter til mange algoritmer til løsning af problemer i grafteori og diskret matematik, herunder Tarjans off-line mindste almindelige forfædre-algoritme . Han er også medforfatter til Fibonacci Heap og Expanding Tree -datastrukturerne . Indførte begrebet afskrivningsanalyse .

PhD (1972), Distinguished University Professor i Princeton, hvor han har undervist siden 1985, Senior Fellow HP Labs . Medlem af American Philosophical Society (1990) [6] , National Academy of Sciences og US Academy of Engineering.

Tidlige år

Hans far, George Tarjan (1912-1991), indfødt i Zsolna og uddannet fra det medicinske fakultet ved universitetet i Budapest , emigrerede til USA i 1939, mens hans forældre og bror , som forblev i Tjekkoslovakiet , blev fængslet i en koncentrationslejr på grund af deres jødiske oprindelse [7] ; i USA blev han børnepsykiater og blev valgt til præsident for American Psychiatric Association [8] [9] . Bedstefar - politiker og politolog Odon Tarjan (Weiss, 1882-1946), grundlægger af det slovakiske ungarske parti , forfatter til bøger om regionalpolitik over for nationale mindretal [10] . Broder-skak-stormester James Tarjan .

Som barn læste han meget science fiction og ville være astronom. Robert blev interesseret i matematik efter at have læst Martin Gardners noter om matematikspil i Scientific American . En seriøs interesse for matematik indpodede ham i ottende klasse en "meget motiverende" lærer.

Mens han studerede i skolen, var Tarjan heldig at arbejde hos IBM med en sorterings- og sorteringsmaskine til hulkort. I 1964, på en sommerskole, fik han sin første seriøse oplevelse med rigtige computere [9] .

Tarjan modtog sin bachelorgrad i matematik fra California Institute of Technology i 1969. Han modtog en mastergrad i datalogi fra Stanford University (1971 ) og en Ph.D. [11] . Tarjan valgte datalogi som en vej, hvorigennem matematik kan bringe håndgribelige praktiske fordele [12] .

Karriere

Tarjan har undervist på Princeton University siden 1985 [12] , hvor han nu er James S. McDonnell Distinguished University Professor of Computer Science. Han havde også akademiske stillinger ved Cornell University (1972-1974), UC Berkeley (1973-1975), Stanford University (1974-1981), New York University (1981-1985). Han var også medlem af NEC Research Institute (1989-1997) og er gæsteforsker ved University of Massachusetts (1996).

Tarjan har arbejdet hos AT&T Bell Labs (1980-1989), InterTrust Technologies (1997-2001), Compaq (2002) og Hewlett Packard, hvor han har fortsat siden 2006. Han har fungeret som medlem af forskellige ACM- og IEEE-komiteer og fungeret som redaktør af flere refererede blade.

Algoritmer og datastrukturer

Tarjan kom med mange effektive algoritmer og datastrukturer til at løse forskellige anvendte problemer. Han har publiceret over 228 artikler i refererede tidsskrifter og monografier.

Tarjan er kendt for sit revolutionerende arbejde inden for grafalgoritmer. De mest bemærkelsesværdige af disse er Tarjans offline-nærmeste fælles forfader-findingsalgoritme til hurtig multiple-finding af den dybeste træknude, der er en fælles forfader til to givne knuder, og Tarjans stærkt forbundne komponentberegningsalgoritme . Hopcroft-Tarjan-algoritmen blev den første lineære algoritme til at bestemme planheden af ​​en graf [13] .

Tarjan udviklede en række vigtige datastrukturer såsom Fibonacci Heap , Disjoint Set System og Splay Tree (en type afbalanceret binært søgetræ; co-forfattet med Daniel Slitor).

I dag er Robert Tarjan James S. McDonnell Distinguished University Professor of Computer Science ved Princeton University og arbejder også hos Hewlett-Packard [14] .

Priser

Tarjan modtog Turing-prisen med John Hopcroft i 1986. Den medfølgende tekst til prisen lyder:

For grundlæggende resultater i udvikling og analyse af algoritmer og datastrukturer.

Tarjan blev også valgt til medlem af ACM (ACM Fellow) i 1994. I lykønskningsteksten [1] står der:

For frugtbart arbejde med udvikling og analyse af algoritmer og datastrukturer.

Andre Robert Tarjan-priser:

I slutningen af ​​februar 2009 rangerede Tarjan som nummer 39 på listen over mest citerede forfattere i CiteSeer- projektet [16] .

Noter

  1. ↑ http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations
  2. ↑ http://www.in.com/robert-tarjan/profile-238439.html
  3. ↑ http://link.springer.com/content/pdf/10.1007%2F978-3-642-15328-0_9.pdf
  4. ↑ Matematisk genealogi  (engelsk) - 1997.
  5. ↑ Udtale af Robert Tarjan: Hvordan man udtaler Robert Tarjan på engelsk . Hentet 7. august 2019. Arkiveret fra originalen 7. august 2019.
  6. ↑ APS medlemshistorie . Hentet 28. marts 2022. Arkiveret fra originalen 26. marts 2022.
  7. ↑ Mundtligt historieinterview med Peter Tarjan
  8. ↑ Til minde om George Tarjan, MD 1912-1991
  9. ↑ 1 2 Shasha, Dennis Elliott; Lazere, Cathy A. Robert E. Tarjan: På jagt efter god struktur // Out of their Minds: The Lives and Discoveries of 15 Great  Computer . - 1998. - S. 102-119. — ISBN 978-0387979922 .
  10. ↑ Ödön Tarján - Politiker, iværksætter og frimurer
  11. ↑ Robert Endre Tarjan . Matematik slægtsforskningsprojekt. Hentet 9. januar 2008. Arkiveret fra originalen 17. marts 2012.
  12. ↑ 1 2 Robert Endre Tarjan: Algoritmens kunst (interview  ) . Hewlett-Packard (september 2004). Hentet 9. januar 2008. Arkiveret fra originalen 17. marts 2012.
  13. ↑ Kocay, William; Kreher, Donald L. Planar Graphs // Grafer, algoritmer og optimering  (neopr.) . - Boca Raton, 2005. - S.  312 . — ISBN 978-1584883968 .
  14. ↑ HP Fellows: Robert Endre Tarjan  (engelsk)  (link ikke tilgængeligt) . Hewlett Packard. Hentet 9. januar 2008. Arkiveret fra originalen 17. marts 2012.
  15. ↑ Robert E. Tarjan  . John Simon Guggenheim Foundation . gf.org. Hentet 9. april 2019. Arkiveret fra originalen 26. januar 2020.
  16. ↑ Statistik - Mest citerede forfattere i datalogi . Hentet 27. februar 2009. Arkiveret fra originalen 1. maj 2012.

Bibliografiske referencer

Links

  Gå til Wikidata-elementet  Tematiske steder
Ordbøger og encyklopædier
 Turing prisvindere