Tarjan, Robert

Robert Tarjan
Englanti  Robert E Tarjan
Syntymäaika 30. huhtikuuta 1948 (74-vuotias)( 30.4.1948 )
Syntymäpaikka Pomona ( Kalifornia , USA )
Maa
Tieteellinen ala Informatiikka
Työpaikka Princeton
Hewlett-Packardin yliopisto
Alma mater Caltech ,
Stanfordin yliopisto
Akateeminen tutkinto Tohtori Stanfordista (1972)
tieteellinen neuvonantaja Robert Floyd [4]
Palkinnot ja palkinnot Nevanlinna-palkinto (1982)
Turing-palkinto ( 1986 )
 Mediatiedostot Wikimedia Commonsissa

Robert Andre Tarjan ( eng.  Robert Endre Tarjan ; / ˈ r ɔː b ə t ˈ t ɑr dʒ æ n / [5] ; syntynyt 30. huhtikuuta 1948 , Pomona , USA ) on yhdysvaltalainen tietojenkäsittelytieteilijä.

Hän on kirjoittanut monia algoritmeja graafiteorian ja diskreetin matematiikan ongelmien ratkaisemiseksi , mukaan lukien Tarjanin off-line vähiten yhteisten esi-isten algoritmi . Hän on myös Fibonacci Heap- ja Expanding Tree -tietorakenteiden toinen kirjoittaja . Otettiin käyttöön poistoanalyysi .

PhD (1972), arvostettu yliopistoprofessori Princetonissa, jossa hän on opettanut vuodesta 1985, Senior Fellow HP Labs . American Philosophical Societyn jäsen (1990) [6] , National Academy of Sciences ja US Academy of Engineering jäsen.

Varhaiset vuodet

Hänen isänsä George Tarjan (1912-1991), kotoisin Zsolnasta ja valmistunut Budapestin yliopiston lääketieteellisestä tiedekunnasta , muutti Yhdysvaltoihin vuonna 1939, kun taas hänen vanhempansa ja veljensä , jotka jäivät Tšekkoslovakiaan , vangittiin v. keskitysleiri juutalaisen alkuperänsä vuoksi [7] ; Yhdysvalloissa hänestä tuli lastenpsykiatri ja hänet valittiin American Psychiatric Associationin presidentiksi [8] [9] . Isoisä - poliitikko ja politologi Odon Tarjan (Weiss, 1882-1946), Slovakian Unkarin puolueen perustaja, kansallisten vähemmistöjen aluepolitiikkaa käsittelevien kirjojen kirjoittaja [10] . Shakkiveli suurmestari James Tarjan .

Lapsena hän luki paljon tieteiskirjallisuutta ja halusi tähtitieteilijäksi. Robert kiinnostui matematiikasta luettuaan Martin Gardnerin muistiinpanot matemaattisista peleistä Scientific Americanissa . Vakava kiinnostus matematiikkaa kohtaan juurrutti häneen kahdeksannella luokalla "erittäin motivoivan" opettajan.

Tarjan oli onnekas koulussa opiskellessaan IBM :llä reikäkorttien lajittelu- ja lajittelukoneen parissa. Vuonna 1964 hän sai kesäkoulussa ensimmäisen vakavan kokemuksensa oikeista tietokoneista [9] .

Tarjan suoritti matematiikan kandidaatin tutkinnon California Institute of Technologysta vuonna 1969. Hän suoritti tietojenkäsittelytieteen maisterin tutkinnon Stanfordin yliopistosta (1971 ) ja tohtorin tutkinnon » (An Efficient Planarity Algorithm) [11] . Tarjan valitsi tietojenkäsittelytieteen poluksi, jonka kautta matematiikka voi tuoda konkreettista käytännön hyötyä [12] .

Ura

Tarjan on opettanut Princetonin yliopistossa vuodesta 1985 [12] , jossa hän on nykyään James S. McDonnell Distinguished University of Computer Science -professori. Hän toimi myös akateemisissa tehtävissä Cornellin yliopistossa (1972-1974), UC Berkeleyssä (1973-1975), Stanfordin yliopistossa (1974-1981), New Yorkin yliopistossa (1981-1985). Hän oli myös NEC Research Instituten jäsen (1989-1997) ja on vieraileva tutkija Massachusettsin yliopistossa (1996).

Tarjan on työskennellyt AT&T Bell Labsissa (1980-1989), InterTrust Technologiesissa (1997-2001), Compaqissa (2002) ja Hewlett Packardissa, jossa hän on jatkanut vuodesta 2006. Hän on toiminut jäsenenä useissa ACM- ja IEEE-komiteoissa sekä toimi useiden referoitujen lehtien toimittajana.

Algoritmit ja tietorakenteet

Tarjan keksi monia tehokkaita algoritmeja ja tietorakenteita erilaisten sovellettavien ongelmien ratkaisemiseen. Hän on julkaissut yli 228 artikkelia referoiduissa aikakauslehdissä ja monografioissa.

Tarjan tunnetaan vallankumouksellisesta työstään graafialgoritmien alalla. Merkittävimmät näistä ovat Tarjanin offline lähimmän yhteisen esi-isän etsintäalgoritmi syvimmän puusolmun nopeaan useaan löytämiseen, joka on kahden tietyn solmun yhteinen esi-isä, ja Tarjanin vahvasti yhdistettyjen komponenttien laskenta-algoritmi . Hopcroft-Tarjan-algoritmista tuli ensimmäinen lineaarinen algoritmi graafin tasoisuuden määrittämiseen [13] .

Tarjan kehitti joukon tärkeitä tietorakenteita, kuten Fibonacci Heap , Disjoint Set System ja Splay Tree (eräänlainen tasapainoinen binäärihakupuu; yhteistyössä Daniel Slitorin kanssa).

Nykyään Robert Tarjan on James S. McDonnell Distinguished University -tietotekniikan professori Princetonin yliopistossa ja työskentelee myös Hewlett-Packardilla [14] .

Palkinnot

Tarjan sai Turing-palkinnon John Hopcroftin kanssa vuonna 1986. Palkinnon saateteksti kuuluu:

Perustuloksista algoritmien ja tietorakenteiden kehittämisessä ja analysoinnissa.

Tarjan valittiin myös ACM:n (ACM Fellow) jäseneksi vuonna 1994. Onnittelutekstissä [1] sanotaan:

Hedelmällisestä työstä algoritmien ja tietorakenteiden kehittämisessä ja analysoinnissa.

Muut Robert Tarjan -palkinnot:

Helmikuun 2009 lopussa Tarjan sijoittui 39. sijalle CiteSeer -projektin siteeratuimpien kirjailijoiden luettelossa [16] .

Muistiinpanot

  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. ↑ Matemaattinen sukututkimus  (englanniksi) - 1997.
  5. ↑ Robert Tarjan ääntäminen: Kuinka äännetään sana Robert Tarjan kielellä englanti . Haettu 7. elokuuta 2019. Arkistoitu alkuperäisestä 7. elokuuta 2019.
  6. ↑ APS-jäsenhistoria . Haettu 28. maaliskuuta 2022. Arkistoitu alkuperäisestä 26. maaliskuuta 2022.
  7. ↑ Peter Tarjanin suullinen haastattelu
  8. ↑ Muistoksi George Tarjan, MD 1912-1991
  9. ↑ 1 2 Shasha, Dennis Elliott; Lazere, Cathy A. Robert E. Tarjan: In Search of Good Structure // Out of The Minds: The Lives and Discoveries of 15 Great  Computer . - 1998. - s. 102-119. — ISBN 978-0387979922 .
  10. ↑ Ödön Tarján - poliitikko, yrittäjä ja vapaamuurari
  11. ↑ Robert Endre Tarjan . Matematiikan sukututkimusprojekti. Haettu 9. tammikuuta 2008. Arkistoitu alkuperäisestä 17. maaliskuuta 2012.
  12. ↑ 1 2 Robert Endre Tarjan: Algoritmin taide (haastattelu  ) . Hewlett-Packard (syyskuu 2004). Haettu 9. tammikuuta 2008. Arkistoitu alkuperäisestä 17. maaliskuuta 2012.
  13. ↑ Kocay, William; Kreher, Donald L. Tasograafit // Kuvaajat , algoritmit ja optimointi  (uuspr.) . - Boca Raton, 2005. - S.  312 . — ISBN 978-1584883968 .
  14. ↑ HP Fellows: Robert Endre Tarjan  (englanniksi)  (linkki ei saatavilla) . Hewlett Packard. Haettu 9. tammikuuta 2008. Arkistoitu alkuperäisestä 17. maaliskuuta 2012.
  15. ↑ Robert E. Tarjan  . John Simon Guggenheimin säätiö . gf.org. Haettu 9. huhtikuuta 2019. Arkistoitu alkuperäisestä 26. tammikuuta 2020.
  16. ↑ Tilastot - Tietojenkäsittelytieteen eniten siteeratut kirjoittajat . Haettu 27. helmikuuta 2009. Arkistoitu alkuperäisestä 1. toukokuuta 2012.

Bibliografiset viittaukset

Linkit

  Siirry Wikidata-kohteeseen  Temaattiset sivustot
Sanakirjat ja tietosanakirjat
 Turing-palkinnon voittajat