Robert Tarjan | |
---|---|
engelsk Robert E Tarjan | |
Födelsedatum | 30 april 1948 (74 år) |
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.
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] .
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.
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] .
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] .
![]() | ||||
---|---|---|---|---|
Ordböcker och uppslagsverk | ||||
|
av Turingpriset | Vinnare|
---|---|
|