Robert Tarjan | |
---|---|
Angličtina Robert E Tarjan | |
Datum narození | 30. dubna 1948 (74 let) |
Místo narození | Pomona ( Kalifornie , USA ) |
Země | |
Vědecká sféra | Informatika |
Místo výkonu práce |
Princeton Hewlett-Packard University |
Alma mater |
Caltech , Stanfordská univerzita |
Akademický titul | PhD ze Stanfordu (1972) |
vědecký poradce | Robert Floyd [4] |
Ocenění a ceny |
Cena Nevanlinna (1982) Turingova cena ( 1986 ) |
Mediální soubory na Wikimedia Commons |
Robert Andre Tarjan ( Ang. Robert Endre Tarjan ; / ˈ r ɔː b ə t ˈ t ɑr dʒ æ n / [5] ; narozen 30. dubna 1948 , Pomona , USA ) je americký počítačový vědec.
Je autorem mnoha algoritmů pro řešení problémů v teorii grafů a diskrétní matematice, včetně Tarjanova off-line algoritmu nejmenších společných předků . Je také spoluautorem datových struktur Fibonacci Heap a Expanding Tree . Zaveden pojem analýza odpisů .
PhD (1972), významný univerzitní profesor na Princetonu, kde vyučuje od roku 1985, Senior Fellow HP Labs . Člen American Philosophical Society (1990) [6] , National Academy of Sciences a US Academy of Engineering.
Jeho otec George Tarjan (1912-1991), rodák ze Zsolny a absolvent lékařské fakulty Univerzity v Budapešti , emigroval v roce 1939 do Spojených států, zatímco jeho rodiče a bratr , kteří zůstali v Československu , byli vězněni v roce 1939. koncentrační tábor kvůli jejich židovskému původu [7] ; v USA se stal dětským psychiatrem a byl zvolen prezidentem Americké psychiatrické asociace [8] [9] . Dědeček - politik a politolog Odon Tarjan (Weiss, 1882-1946), zakladatel Slovenské maďarské strany , autor knih o regionální politice vůči národnostním menšinám [10] . Bratr - šachový velmistr James Tarjan .
Jako dítě četl hodně sci-fi a chtěl být astronomem. Robert se začal zajímat o matematiku poté, co si přečetl poznámky Martina Gardnera o matematických hrách v Scientific American . Vážný zájem o matematiku mu v osmé třídě vštípil „velmi motivujícího“ učitele.
Při studiu na škole měl Tarjan to štěstí, že pracoval v IBM s třídicím a třídícím strojem na děrné štítky. V roce 1964 na letní škole získal první seriózní zkušenost s reálnými počítači [9] .
Tarjan získal bakalářský titul z matematiky na California Institute of Technology v roce 1969. Získal magisterský titul v oboru počítačových věd na Stanfordské univerzitě (1971 ) a Ph.D. » (An Efficient Planarity Algorithm) [11] . Tarjan si zvolil informatiku jako cestu, jejímž prostřednictvím může matematika přinést hmatatelné praktické výhody [12] .
Tarjan vyučuje na Princetonské univerzitě od roku 1985 [12] , kde je nyní James S. McDonnell Distinguished University Professor of Computer Science. Zastával také akademické funkce na Cornell University (1972-1974), UC Berkeley (1973-1975), Stanford University (1974-1981), New York University (1981-1985). Byl také členem NEC Research Institute (1989-1997) a je hostujícím vědcem na University of Massachusetts (1996).
Tarjan pracoval ve společnostech AT&T Bell Labs (1980-1989), InterTrust Technologies (1997-2001), Compaq (2002) a Hewlett Packard, kde působí od roku 2006. Působil jako člen různých výborů ACM a IEEE a působil jako redaktor několika recenzovaných časopisů.
Tarjan přišel s mnoha účinnými algoritmy a datovými strukturami pro řešení různých aplikovaných problémů. Publikoval přes 228 článků v recenzovaných časopisech a monografiích.
Tarjan je známý svou revoluční prací v oblasti grafových algoritmů. Nejpozoruhodnější z nich jsou Tarjanův Offline Algoritmus hledání nejbližšího společného předka pro rychlé vícenásobné hledání nejhlubšího stromového uzlu, který je společným předkem dvou daných uzlů, a Tarjanův algoritmus pro výpočet silně propojených komponent . Hopcroft-Tarjanův algoritmus se stal prvním lineárním algoritmem pro určení rovinnosti grafu [13] .
Tarjan vyvinul řadu důležitých datových struktur, jako je Fibonacciho halda , Disjoint Set System a Splay Tree (typ vyváženého binárního vyhledávacího stromu; spoluautor Daniel Slitor).
Dnes je Robert Tarjan James S. McDonnell Distinguished University Professor of Computer Science na Princeton University a také pracuje v Hewlett-Packard [14] .
Tarjan obdržel Turingovu cenu s Johnem Hopcroftem v roce 1986. Doprovodný text ceny zní:
Za zásadní výsledky ve vývoji a analýze algoritmů a datových struktur.Tarjan byl také zvolen členem ACM (ACM Fellow) v roce 1994. Gratulační text [1] uvádí:
Za plodnou práci při vývoji a analýze algoritmů a datových struktur.Další ocenění Roberta Tarjana:
Na konci února 2009 se Tarjan umístil na 39. místě v seznamu nejcitovanějších autorů v projektu CiteSeer [16] .
![]() | ||||
---|---|---|---|---|
Slovníky a encyklopedie | ||||
|
Turingovy ceny | Vítězové|
---|---|
|