Robert Tarjan | |
---|---|
engelsk Robert E Tarjan | |
Fødselsdato | 30. april 1948 (74 år) |
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.
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] .
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.
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] .
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] .
Tematiske steder | ||||
---|---|---|---|---|
Ordbøger og encyklopædier | ||||
|
Turing prisvindere | |
---|---|
|