Tarjan, Robert

Robert Tarjan
Engleză  Robert E Tarjan
Data nașterii 30 aprilie 1948 (74 de ani)( 30.04.1948 )
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.

Primii ani

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] .

Cariera

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.

Algoritmi și structuri de date

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] .

Premii

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] .

Note

  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. ↑ Genealogia matematică  (engleză) - 1997.
  5. ↑ pronunția cuvântului Robert Tarjan: Cum se pronunță Robert Tarjan în Engleză . Preluat la 7 august 2019. Arhivat din original pe 7 august 2019.
  6. ↑ Istoricul membrilor APS . Preluat la 28 martie 2022. Arhivat din original la 26 martie 2022.
  7. ↑ Interviu de istorie orală cu Peter Tarjan
  8. ↑ In memoriam George Tarjan, MD 1912-1991
  9. ↑ 1 2 Shasha, Dennis Elliott; Lazere, Cathy A. Robert E. Tarjan: În căutarea unei structuri bune // Out of Their Minds: The Lives and Discoveries of 15 Great  Computer . - 1998. - P. 102-119. — ISBN 978-0387979922 .
  10. ↑ Ödön Tarján - om politic, antreprenor și francmason
  11. ↑ Robert Endre Tarjan . Proiect Genealogie Matematică. Consultat la 9 ianuarie 2008. Arhivat din original pe 17 martie 2012.
  12. ↑ 1 2 Robert Endre Tarjan: Arta algoritmului (interviu  ) . Hewlett-Packard (septembrie 2004). Consultat la 9 ianuarie 2008. Arhivat din original pe 17 martie 2012.
  13. ↑ Kocay, William; Kreher, Donald L. Grafice plane // Grafice, algoritmi și optimizare  (neopr.) . - Boca Raton, 2005. - S.  312 . — ISBN 978-1584883968 .
  14. ↑ HP Fellows: Robert Endre Tarjan  (engleză)  (link nu este disponibil) . Hewlett Packard. Consultat la 9 ianuarie 2008. Arhivat din original pe 17 martie 2012.
  15. ↑ Robert E. Tarjan  . Fundația John Simon Guggenheim . gf.org. Preluat la 9 aprilie 2019. Arhivat din original la 26 ianuarie 2020.
  16. ↑ Statistici - Cei mai citați autori în informatică . Consultat la 27 februarie 2009. Arhivat din original la 1 mai 2012.

Referințe bibliografice

Link -uri

  Accesați articolul Wikidata  Site-uri tematice
Dicționare și enciclopedii
 Câștigători ai premiului Turing