Tarjan, Robert

Robert Tarjan
engelsk  Robert E Tarjan
Födelsedatum 30 april 1948 (74 år)( 1948-04-30 )
Födelseort Pomona ( Kalifornien , USA )
Land
Vetenskaplig sfär Informatik
Arbetsplats Princeton
Hewlett-Packard University
Alma mater Caltech ,
Stanford University
Akademisk examen PhD från Stanford (1972)
vetenskaplig rådgivare Robert Floyd [4]
Utmärkelser och priser Nevanlinna-priset (1982)
Turing-priset ( 1986 )
 Mediafiler på Wikimedia Commons

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

Han är författare till många algoritmer för att lösa problem inom grafteori och diskret matematik, inklusive Tarjans off-line algoritm för minst gemensamma förfäder . Han är också medförfattare till Fibonacci Heap och Expanding Tree datastrukturer . Införde begreppet avskrivningsanalys .

PhD (1972), Distinguished University Professor i Princeton, där han har undervisat sedan 1985, Senior Fellow HP Labs . Medlem av American Philosophical Society (1990) [6] , National Academy of Sciences och US Academy of Engineering.

Tidiga år

Hans far, George Tarjan (1912-1991), född i Zsolna och examen från medicinska fakulteten vid universitetet i Budapest , emigrerade till USA 1939, medan hans föräldrar och bror , som stannade kvar i Tjeckoslovakien , fängslades i ett koncentrationsläger på grund av deras judiska ursprung [7] ; i USA blev han barnpsykiater och valdes till president för American Psychiatric Association [8] [9] . Farfar - politiker och statsvetare Odon Tarjan (Weiss, 1882-1946), grundare av det slovakiska ungerska partiet , författare till böcker om regionalpolitik gentemot nationella minoriteter [10] . Broder-schackstormästaren James Tarjan .

Som barn läste han mycket science fiction och ville bli astronom. Robert blev intresserad av matematik efter att ha läst Martin Gardners anteckningar om matematikspel i Scientific American . Ett seriöst intresse för matematik ingav honom i åttan en "mycket motiverande" lärare.

När han studerade i skolan hade Tarjan turen att arbeta på IBM med en sorterings- och sorteringsmaskin för hålkort. 1964, på en sommarskola, fick han sin första seriösa erfarenhet av riktiga datorer [9] .

Tarjan tog sin kandidatexamen i matematik från California Institute of Technology 1969. Han fick en magisterexamen i datavetenskap från Stanford University (1971 ) och en doktorsexamen [11] . Tarjan valde datavetenskap som en väg genom vilken matematik kan ge påtagliga praktiska fördelar [12] .

Karriär

Tarjan har undervisat vid Princeton University sedan 1985 [12] , där han nu är James S. McDonnell Distinguished University Professor of Computer Science. Han hade också akademiska positioner vid Cornell University (1972-1974), UC Berkeley (1973-1975), Stanford University (1974-1981), New York University (1981-1985). Han var också medlem av NEC Research Institute (1989-1997) och är gästforskare vid University of Massachusetts (1996).

Tarjan har arbetat på AT&T Bell Labs (1980-1989), InterTrust Technologies (1997-2001), Compaq (2002) och Hewlett Packard, där han har fortsatt sedan 2006. Han har varit medlem i olika ACM- och IEEE-kommittéer och tjänstgjorde som redaktör för flera refererade tidskrifter.

Algoritmer och datastrukturer

Tarjan kom med många effektiva algoritmer och datastrukturer för att lösa olika tillämpade problem. Han har publicerat över 228 artiklar i refererade tidskrifter och monografier.

Tarjan är känd för sitt revolutionerande arbete inom grafalgoritmer. De mest anmärkningsvärda av dessa är Tarjans offline-algoritm för att hitta närmaste gemensamma förfäder för att snabbt hitta den djupaste trädnoden som är en gemensam förfader till två givna noder, och Tarjans beräkningsalgoritm för starkt anslutna komponenter . Hopcroft-Tarjan-algoritmen blev den första linjära algoritmen för att bestämma planariteten för en graf [13] .

Tarjan utvecklade ett antal viktiga datastrukturer som Fibonacci Heap , Disjoint Set System och Splay Tree (en typ av balanserat binärt sökträd; co-författare med Daniel Slitor).

Idag är Robert Tarjan James S. McDonnell Distinguished University Professor of Computer Science vid Princeton University och arbetar även på Hewlett-Packard [14] .

Utmärkelser

Tarjan fick Turing Award med John Hopcroft 1986. Den medföljande texten till priset lyder:

För grundläggande resultat i utveckling och analys av algoritmer och datastrukturer.

Tarjan valdes också till medlem av ACM (ACM Fellow) 1994. I gratulationstexten [1] står det:

För fruktbart arbete med utveckling och analys av algoritmer och datastrukturer.

Andra Robert Tarjan-priser:

I slutet av februari 2009 rankades Tarjan på 39:e plats i listan över mest citerade författare i CiteSeer- projektet [16] .

Anteckningar

  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. ↑ Mathematical Genealogy  (engelska) - 1997.
  5. ↑ Uttal av Robert Tarjan: Hur man uttalar Robert Tarjan på engelska . Hämtad 7 augusti 2019. Arkiverad från originalet 7 augusti 2019.
  6. ↑ APS-medlemshistorik . Hämtad 28 mars 2022. Arkiverad från originalet 26 mars 2022.
  7. ↑ Muntlig historieintervju med Peter Tarjan
  8. ↑ Till minne av George Tarjan, MD 1912-1991
  9. ↑ 1 2 Shasha, Dennis Elliott; Lazere, Cathy A. Robert E. Tarjan: In Search of Good Structure // Out of They Minds: The Lives and Discoveries of 15 Great  Computer . - 1998. - S. 102-119. — ISBN 978-0387979922 .
  10. ↑ Ödön Tarján - Politiker, entreprenör och frimurare
  11. ↑ Robert Endre Tarjan . Matematik släktforskningsprojekt. Hämtad 9 januari 2008. Arkiverad från originalet 17 mars 2012.
  12. ↑ 1 2 Robert Endre Tarjan: Algoritmens konst (intervju  ) . Hewlett-Packard (september 2004). Hämtad 9 januari 2008. Arkiverad från originalet 17 mars 2012.
  13. ↑ Kocay, William; Kreher, Donald L. Planar Graphs // Grafer, algoritmer och optimering  (neopr.) . - Boca Raton, 2005. - S.  312 . — ISBN 978-1584883968 .
  14. ↑ HP Fellows: Robert Endre Tarjan  (engelska)  (länk ej tillgänglig) . Hewlett Packard. Hämtad 9 januari 2008. Arkiverad från originalet 17 mars 2012.
  15. ↑ Robert E. Tarjan  . John Simon Guggenheim Foundation . gf.org. Hämtad 9 april 2019. Arkiverad från originalet 26 januari 2020.
  16. ↑ Statistik - Mest citerade författare i datavetenskap . Hämtad 27 februari 2009. Arkiverad från originalet 1 maj 2012.

Bibliografiska referenser

Länkar

  Gå till Wikidata-objektet  Tematiska platser
Ordböcker och uppslagsverk
 Vinnare av Turingpriset