Robert Tarjan - Robert Tarjan
Robert Endre Tarjan | |
|---|---|
 | |
| narozený | 30.dubna 1948 |
| Státní občanství | americký |
| Alma mater | Kalifornský technologický institut (BS ) Stanfordská Univerzita (SLEČNA, PhD ) |
| Známý jako | Algoritmy a datové struktury |
| Ocenění | Paris Kanellakis Award (1999) Turing Award (1986) Cena Nevanlinna (1982) |
| Vědecká kariéra | |
| Pole | Počítačová věda |
| Instituce | Univerzita Princeton Newyorská univerzita Stanfordská Univerzita University of California, Berkeley Cornell University Microsoft Research Technologie Intertrust Hewlett Packard Compaq Výzkum NEC Bell Labs |
| Teze | Efektivní algoritmus rovinnosti (1972) |
| Doktorský poradce | Robert W. Floyd |
| Ostatní akademičtí poradci | Donald Knuth |
| Doktorandi | |
| webová stránka | www |
Robert Endre Tarjan (narozen 30. dubna 1948) je americký počítačový vědec a matematik. Je objevitelem několika graf algoritmy, včetně Tarjanův offline nejnižší algoritmus společných předků a spoluautorem obou roztáhnout stromy a Fibonacci se hromadí. Tarjan je v současné době James S. McDonnell Významný univerzitní profesor výpočetní techniky na Univerzita Princeton a hlavní vědecký pracovník v Intertrust Technologies Corporation.[1]
raný život a vzdělávání
Narodil se v Pomona, Kalifornie. Jeho otec byl dětský psychiatr se specializací na mentální retardaci a provozoval státní nemocnici.[2] Jako dítě četl Tarjan hodně sci-fi a chtěl být astronom. Začal se zajímat matematika po přečtení Martin Gardner Sloupec matematických her ve Windows Scientific American. O matematiku se začal vážně zajímat v osmé třídě díky „velmi podnětnému“ učiteli.[3]
Když byl na střední škole, Tarjan dostal práci, kde pracoval u zakladačů děrovacích karet IBM. Nejprve pracoval se skutečnými počítači, zatímco studoval astronomii na Letní vědecký program v roce 1964.[2]
Tarjan získal a Bakalářský titul v matematice z Kalifornský technologický institut v roce 1969 Stanfordská Univerzita, v roce 1971 získal magisterský titul v oboru počítačových věd a Ph.D. v oboru počítačových věd (s maturitou v oboru matematika) v roce 1972. Ve Stanfordu na něj dohlížel Robert Floyd[4] a Donald Knuth,[5] oba vysoce prominentní počítačoví vědci a jeho Ph.D. disertační práce byla Efektivní algoritmus rovinnosti. Tarjan si jako oblast zájmu vybral informatiku, protože věřil, že informatika je způsob, jak dělat matematiku, který může mít praktický dopad.[6]
Kariéra informatiky
Tarjan vyučuje na Princetonské univerzitě od roku 1985.[6] Zastával také akademické pozice v Cornell University (1972–73), University of California, Berkeley (1973–1975), Stanfordská Univerzita (1974–1980) a Newyorská univerzita (1981–1985). Byl také členem Výzkumného ústavu NEC (1989–1997).[7] V dubnu 2013 nastoupil do společnosti Microsoft Research Silicon Valley kromě pozice v Princetonu. V říjnu 2014 se vrátil k společnosti Intertrust Technologies jako hlavní vědecký pracovník.
Tarjan pracoval ve společnostech AT&T Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014 – dosud), Compaq (2002) a Hewlett Packard (2006–2013).
Algoritmy a datové struktury
Tarjan je známý svou průkopnickou prací na algoritmech teorie grafů a datových strukturách. Některé z jeho dobře známých algoritmů zahrnují Tarjanův offline nejméně běžný algoritmus předků, a Tarjanův algoritmus silně propojených komponent, a byl jedním z pěti spoluautorů medián mediánů lineární čas algoritmus výběru. Hopcroft – Tarjan testování rovinnosti Algoritmus byl první algoritmus lineárního času pro testování rovinnosti.[8]
Tarjan také vyvinul důležité datové struktury, jako je Fibonacciho hromada (halda datová struktura skládající se z lesa stromů) a rozložit strom (samočinně se upravující binární vyhledávací strom; společně vynalezli Tarjan a Daniel Sleator ). Dalším významným příspěvkem byla analýza disjunktně nastavená datová struktura; byl první, kdo dokázal optimální dobu běhu zahrnující inverzi Ackermannova funkce.
Ocenění
Tarjan obdržel Turing Award společně s John Hopcroft v roce 1986. Citace ceny uvádí[7] že to bylo:
Za základní úspěchy při navrhování a analýze algoritmů a datových struktur.
Tarjan byl také zvolen Člen ACM v roce 1994. Citace za toto ocenění uvádí:[9]
Za zásadní pokroky v návrhu a analýze datových struktur a algoritmů.
Mezi další ocenění Tarjana patří:
- Cena Nevanlinna v informační vědě (1983)[7] - první příjemce[10]
- Člen Americká akademie umění a věd, zvolen 1985[11]
- Cena Národní akademie věd za iniciativy ve výzkumu (1984)[7]
- Člen Národní akademie věd, zvolený 1987[12]
- Člen National Academy of Engineering, zvolený v roce 1988[13]
- Paris Kanellakis Award v teorii a praxi, ACM (1999)[7]
- Caltech Distinguished Alumni Award, Kalifornský technologický institut (2010)[14]
Patenty
Tarjan je držitelem nejméně 18 amerických patentů.[5] Tyto zahrnují:
- J. Bentley, D. Sleator a R. E. Tarjan, patent USA 4 796 003, Zhutnění dat, 1989[15]
- N. Mishra, R. Schreiber a R. E. Tarjan, patent USA 7 818 272, Metoda pro zjišťování shluků objektů v libovolném neorientovaném grafu pomocí rozdílu mezi zlomkem vnitřních připojení a maximálním zlomkem připojení vnějším objektem, 2010[16]
- B. Pinkas, S. Haber, R. E. Tarjan a T. Sander, patent USA 8220036, Vytvoření zabezpečeného kanálu s lidským uživatelem, 2012[17]
Poznámky
- ^ „Intertrust Leadership“. intertrust.com.
- ^ A b Shasha, Dennis Elliott; Lazere, Cathy A. (1998) [1995]. „Robert E. Tarjan: Hledání dobré struktury“. Z jejich myslí: Životy a objevy 15 skvělých počítačových vědců. Copernicus / Springer. str.102–119. ISBN 978-0-387-97992-2. OCLC 32240355.
- ^ „Robert Tarjan: The Art of the Algorithm“. Hewlett Packard. Citováno 2010-09-05.
- ^ „Robert Endre Tarjan“. Matematický genealogický projekt. Citováno 2008-01-09.
- ^ A b Tarjan, Robert Endre (15. listopadu 2019). "Životopis" (PDF). Archivovány od originál (PDF) dne 2019-11-23. Citováno 2019-11-23.
- ^ A b „Robert Endre Tarjan: Umění algoritmu (rozhovor)“. Hewlett Packard. Září 2004. Citováno 2008-01-09.
- ^ A b C d E King, V. „Robert E Tarjan - laureát ceny A.M. Turinga“. ACM. Citováno 2014-01-19.
- ^ Kocay, William; Kreher, Donald L (2005). "Rovinné grafy". Grafy, algoritmy a optimalizace. Boca Raton: Chapman & Hall / CRC. p.312. ISBN 978-1-58488-396-8. OCLC 56319851.
- ^ „Cena Fellows - Robert E. Tarjan“. ACM. 25. září 1998. Citováno 2005-11-18.
- ^ „Vítězové cen Rolfa Nevanlinny“. Mezinárodní matematická unie. Archivovány od originál dne 2008-12-27. Citováno 2014-01-19.
- ^ „Robert Endre Tarjan“. Americká akademie umění a věd. Citováno 2020-06-15.
- ^ „Robert Tarjan“. www.nasonline.org. Citováno 2020-06-15.
- ^ „Dr. Robert E. Tarjan“. Web NAE. Citováno 2020-06-15.
- ^ „Caltech jmenuje pět významných absolventů“ (Tisková zpráva). Kalifornský technologický institut. 2010-03-15. Archivovány od originál dne 10. 10. 2010. Citováno 2010-08-26.
- ^ Bentley, Jon L .; Sleator, Daniel D. K .; Tarjan, Robert E. (3. ledna 1989). „Patent Spojených států 4796003 - Zhutnění dat“.
- ^ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (19. října 2010). „Patent USA 7818272 - Metoda pro objevování shluků objektů v libovolném neorientovaném grafu s použitím rozdílu mezi zlomkem vnitřních spojení a maximálním zlomkem spojení vnějším objektem“.
- ^ Pinkas, Binyamin; Haber, Stuart A .; Tarjan, Robert E .; Sander, Tomáš (10. července 2012). „Patent USA 8220036 - Vytvoření bezpečného kanálu s lidským uživatelem“.
Reference
- Tarjan, Robert E. (1983). Datové struktury a síťové algoritmy. Philadelphia: Společnost pro průmyslovou a aplikovanou matematiku. ISBN 978-0-89871-187-5. OCLC 10120539.
- Tarjan, Robert E .; Pólya, George; Woods, Donald R. (1983). Poznámky k úvodní kombinatorice. Boston: Birkhauser. ISBN 978-0-8176-3170-3. OCLC 10018128.
- OCLC položky pro Roberta E. Tarjana
- Robert E. Tarjan na DBLP Bibliografický server
