Тарджан, Роберт
Материал из Википедии — свободной энциклопедии
| Роберт Тарджан | |
|---|---|
| англ. Robert E. Tarjan | |
 | |
| Дата рождения | 30 апреля 1948 (76 лет) |
| Место рождения | Помона (штат Калифорния, США) |
| Страна | |
| Род деятельности | математик, специалист в области информатики, преподаватель университета |
| Научная сфера | Информатика |
| Место работы |
Принстонский университет Hewlett-Packard |
| Альма-матер |
Калифорнийский технологический институт, Стэнфордский университет |
| Учёная степень | доктор философии Стэнфорда (1972) |
| Научный руководитель | Роберт Флойд[3] |
| Награды и премии |
Премия Неванлинны (1982) Премия Тьюринга (1986) |
 Медиафайлы на Викискладе | |
Роберт Эндре Тарджан (англ. Robert Endre Tarjan; /ˈrɔːbət ˈtɑrdʒæn/[4]; род. 30 апреля 1948 года, Помона, США) — американский учёный в области теории вычислительных систем.
Автор множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка, соавтор ряда важных структур данных, в том числе фибоначчиевой кучи и расширяющегося дерева. Концептуализировал понятие амортизационного анализа.
Доктор философии (1972), заслуженный профессор Принстонского университета, где преподаёт с 1985 года, старший фелло HP Labs[англ.]. Член Американского философского общества (1990)[5], Национальной академии наук и Инженерной академии США.
Ранние годы
[править | править код]Отец — Джордж Тарджан (Дьёрдь Тарьян, 1912—1991) — уроженец Жолны и выпускник медицинского факультета Будапештского университета, эмигрировал в США в 1939 году, тогда как его оставшиеся в Чехословакии родители и брат в силу еврейского происхождения были заключены в концентрационный лагерь[6]; в США стал детским психиатром и был избран президентом Американской психиатрической ассоциации[7][8]. Дед — политик и политолог Эдён Тарьян[венг.] (Вайс, 1882—1946), основатель Словацкой венгерской партии права[венг.], автор книг по региональной политике в отношении национальных меньшинств[9]. Брат — шахматный гроссмейстер Джеймс Тарджан.
В детстве читал много научной фантастики и хотел стать астрономом. Математикой заинтересовался после прочтения заметок Мартина Гарднера по математическим играм в журнале «Scientific American». Серьёзный интерес к математике привил ему в восьмом классе «очень мотивирующий» учитель.
Во время обучения в школе имел возможность поработать в IBM с сортировально-подборочной машиной для перфокарт. В 1964 году в летней школе получил первый серьёзный опыт работы с настоящими компьютерами[8].
Звание бакалавра по математике получил в Калифорнийском технологическом институте в 1969 году. В Стэнфордском университете получил магистерскую степень по информатике (1971) и степень доктора философии по информатике — в 1972 году, его научными руководителями в Стэнфорде были Роберт Флойд и Дональд Кнут, тема диссертации — «Эффективный алгоритм определения планарности графа»[10][11].
Карьера
[править | править код]С 1985 года — преподаватель в Принстонском университете[11], где ныне именной заслуженный Университетский профессор информатики (James S. McDonnell Distinguished University Professor). У него также были академические должности в Корнеллском университете (1972—1974), Калифорнийском университете в Беркли (1973—1975), Стэнфордском университете (1974—1981), Нью-Йоркском университете(1981—1985). Также был членом NEC Research Institute (1989—1997) и числится (на должности Visiting Scientist) в Массачусетском технологическом институте (1996).
Работал в AT&T Bell Labs (1980—1989), InterTrust Technologies (1997—2001), Compaq (2002) и Hewlett-Packard, где продолжает работать с 2006 года. Избирался членом различных комитетов Ассоциации вычислительной техники (ACM) и Института инженеров электротехники и электроники (IEEE), а также работал редактором нескольких рецензируемых журналов.
Алгоритмы и структуры данных
[править | править код]Разработал множество эффективных алгоритмов и структур данных для решения различных прикладных задач. Опубликовал более 228 статей в рецензируемых журналах и монографиях.
Известен работами в области алгоритмов на графах. Наиболее яркие из них — оффлайновый алгоритм Тарьяна поиска ближайшего общего предка для многократного быстрого поиска самого глубокого узла дерева, являющегося общим предком двух заданных узлов, и алгоритм Тарьяна вычисления сильно связных компонент. Алгоритм Хопкрофта — Тарьяна стал первым линейным алгоритмом определения планарности графа[12].
Разработал ряд важнейших структур данных, таких как фибоначчиева куча, система непересекающихся множеств и расширяющееся дерево (англ. splay tree, один из видов сбалансированного двоичного дерева поиска; в соавторстве с Дэниелом Слитором.
Награды
[править | править код]В 1986 году совместно Джоном Хопкрофтом стал лауреатом премии Тьюринга «за фундаментальные результаты в области разработки и анализа алгоритмов и структур данных».
Избран действительным членом ACM (ACM Fellow) в 1994 году «за плодотворный труд в области разработки и анализа алгоритмов и структур данных».
Другие награды:
- Стипендия Гуггенхайма (1978)[13]
- Премия Неванлинны (1982) — первый лауреат этой премии
- William O. Baker Award for Initiatives in Research[англ.] (1984)
- Paris Kanellakis Award in Theory and Practice, ACM (1999)
- Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences (2004)
По состоянию на конец февраля 2009 года занимал 39-е место в списке самых цитируемых авторов в проекте CiteSeer[14].
Примечания
[править | править код]- ↑ http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations
- ↑ http://www.in.com/robert-tarjan/profile-238439.html
- ↑ Mathematics Genealogy Project (англ.) — 1997.
- ↑ Robert Tarjan pronunciation: How to pronounce Robert Tarjan in English. Дата обращения: 7 августа 2019. Архивировано 7 августа 2019 года.
- ↑ APS Member History. Дата обращения: 28 марта 2022. Архивировано 26 марта 2022 года.
- ↑ Oral history interview with Peter Tarjan. Дата обращения: 7 сентября 2022. Архивировано 7 сентября 2022 года.
- ↑ In memoriam George Tarjan, M.D. 1912—1991. Дата обращения: 7 сентября 2022. Архивировано 6 декабря 2022 года.
- ↑ 1 2 Shasha, Dennis Elliott; Lazere, Cathy A. Robert E. Tarjan: In Search of Good Structure // Out of Their Minds: The Lives and Discoveries of 15 Great Computer (англ.). — 1998. — P. 102—119. — ISBN 978-0387979922.
- ↑ Ödön Tarján — Politician, Entrepreneur and Freemason. Дата обращения: 7 сентября 2022. Архивировано 7 сентября 2022 года.
- ↑ Robert Endre Tarjan. Mathematics Genealogy Project. Дата обращения: 9 января 2008. Архивировано 17 марта 2012 года.
- ↑ 1 2 Robert Endre Tarjan: The art of the algorithm (interview) (англ.). Hewlett-Packard (September 2004). Дата обращения: 9 января 2008. Архивировано 17 марта 2012 года.
- ↑ Kocay, William; Kreher, Donald L. Planar Graphs // Graphs, algorithms, and optimization (неопр.). — Boca Raton, 2005. — С. 312. — ISBN 978-1584883968.
- ↑ Robert E. Tarjan (англ.). John Simon Guggenheim Foundation. gf.org. Дата обращения: 9 апреля 2019. Архивировано 26 января 2020 года.
- ↑ Statistics — Most Cited Authors in Computer Science. Дата обращения: 27 февраля 2009. Архивировано 1 мая 2012 года.
Библиографические ссылки
[править | править код]- Tarjan, Robert E. Data structures and network algorithms (неопр.). — Philadelphia, 1983. — ISBN 978-0898711875.
- Tarjan, Robert E.; Polya, George; Woods, Donald R. Notes on introductory combinatorics (неопр.). — Boston, 1983. — ISBN 978-0817631703.
- OCLC entries for Robert E Tarjan
- DBLP entry for Robert Endre Tarjan
Ссылки
[править | править код] | ||||
|---|---|---|---|---|
| Словари и энциклопедии | ||||
Лауреаты премии Тьюринга | |
|---|---|
| |
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
