Robert Tarjan | |
---|---|
Engleză Robert E Tarjan | |
Data nașterii | 30 aprilie 1948 (74 de ani) |
Locul nașterii | Pomona ( California , SUA ) |
Țară |
|
Sfera științifică | Informatica |
Loc de munca |
Universitatea Princeton Hewlett-Packard |
Alma Mater |
Caltech , Universitatea Stanford |
Grad academic | doctorat de la Stanford (1972) |
consilier științific | Robert Floyd [4] |
Premii și premii |
Premiul Nevanlinna (1982) Premiul Turing ( 1986 ) |
Fișiere media la Wikimedia Commons |
Robert Andre Tarjan ( ing. Robert Endre Tarjan ; / ˈ r ɔː b ə t ˈ t ɑr dʒ æ n / [5] ; născut la 30 aprilie 1948 , Pomona , SUA ) este un informatician american.
El este autorul multor algoritmi pentru rezolvarea problemelor în teoria grafurilor și matematica discretă, inclusiv algoritmul off-line al lui Tarjan, cel mai puțin comun strămoși . El este, de asemenea, co-autor al structurilor de date Fibonacci Heap și Expanding Tree . A introdus termenul de analiză a deprecierii .
PhD (1972), Distinguished University Professor la Princeton, unde predă din 1985, Senior Fellow HP Labs . Membru al Societății Americane de Filosofie (1990) [6] , al Academiei Naționale de Științe și al Academiei de Inginerie din SUA.
Tatăl său, George Tarjan (1912-1991), originar din Zsolna și absolvent al facultății de medicină a Universității din Budapesta , a emigrat în Statele Unite în 1939, în timp ce părinții și fratele său , care au rămas în Cehoslovacia , au fost închiși în un lagăr de concentrare datorită originii lor evreiești [7] ; în SUA a devenit psihiatru de copii și a fost ales președinte al Asociației Americane de Psihiatrie [8] [9] . Bunicul - politician și politolog Odon Tarjan (Weiss, 1882-1946), fondator al Partidului Slovac Ungar , autor de cărți despre politica regională față de minoritățile naționale [10] . Frate - marele maestru de șah James Tarjan .
În copilărie, a citit multă ficțiune științifico-fantastică și și-a dorit să devină astronom. Robert a devenit interesat de matematică după ce a citit notițele lui Martin Gardner despre jocurile de matematică din Scientific American . Un interes serios pentru matematică i-a insuflat în clasa a VIII-a un profesor „foarte motivant”.
În timp ce studia la școală, Tarjan a avut norocul să lucreze la IBM cu o mașină de sortat și sortat pentru cărți perforate. În 1964, la o școală de vară, a primit prima experiență serioasă cu computere reale [9] .
Tarjan a primit diploma de licență în matematică de la Institutul de Tehnologie din California în 1969. A obținut un master în informatică la Universitatea Stanford (1971 ) și un doctorat [11] . Tarjan a ales informatica ca o cale prin care matematica poate aduce beneficii practice tangibile [12] .
Tarjan predă la Universitatea Princeton din 1985 [12] , unde acum este profesor distins de informatică James S. McDonnell. De asemenea, a deținut funcții academice la Universitatea Cornell (1972-1974), UC Berkeley (1973-1975), Universitatea Stanford (1974-1981), Universitatea New York (1981-1985). De asemenea, a fost membru al Institutului de Cercetare NEC (1989-1997) și este cercetător vizitator la Universitatea din Massachusetts (1996).
Tarjan a lucrat la AT&T Bell Labs (1980-1989), InterTrust Technologies (1997-2001), Compaq (2002) și Hewlett Packard, unde a continuat din 2006. A fost membru al diferitelor comitete ACM și IEEE și a servit ca redactor la mai multe reviste arbitrate.
Tarjan a venit cu mulți algoritmi și structuri de date eficiente pentru rezolvarea diferitelor probleme aplicate. A publicat peste 228 de articole în reviste și monografii arbitrate.
Tarjan este cunoscut pentru munca sa revoluționară în domeniul algoritmilor grafici. Cele mai notabile dintre acestea sunt Algoritmul de găsire a celui mai apropiat strămoș comun offline al lui Tarjan pentru găsirea rapidă a mai multor noduri a celui mai adânc arbore care este un strămoș comun a două noduri date și algoritmul de calcul al componentelor puternic conectate al lui Tarjan . Algoritmul Hopcroft-Tarjan a devenit primul algoritm liniar pentru determinarea planarității unui graf [13] .
Tarjan a dezvoltat o serie de structuri de date importante, cum ar fi Fibonacci Heap , Disjoint Set System și Splay Tree (un tip de arbore de căutare binar echilibrat; în colaborare cu Daniel Slitor).
Astăzi, Robert Tarjan este James S. McDonnell Distinguished University Professor of Computer Science la Universitatea Princeton și lucrează și la Hewlett-Packard [14] .
Tarjan a primit Premiul Turing cu John Hopcroft în 1986. Textul însoțitor al premiului spune:
Pentru rezultate fundamentale în dezvoltarea și analiza algoritmilor și structurilor de date.De asemenea, Tarjan a fost ales membru al ACM (ACM Fellow) în 1994. Textul de felicitare [1] spune:
Pentru munca fructuoasă în dezvoltarea și analiza algoritmilor și structurilor de date.Alte premii Robert Tarjan:
La sfârșitul lunii februarie 2009, Tarjan ocupa locul 39 în lista celor mai citați autori în proiectul CiteSeer [16] .
![]() | ||||
---|---|---|---|---|
Dicționare și enciclopedii | ||||
|
ai premiului Turing | Câștigători|
---|---|
|