Войти
| Роберт Эндре Тарджан | |
|---|---|
 | |
| Родился | (1948-04-30) 30 апреля 1948 г. (возраст 72). Помона, Калифорния |
| Гражданство | Американский |
| Alma mater | Калифорнийский технологический институт (BS ). Стэнфордский университет (MS, Доктор философии ) |
| Известен | Алгоритмы и структуры данных |
| Награды | Премия Пэрис Канеллакис (1999). Премия Тьюринга (1986). Премия Неванлинны (1982) |
| Научная карьера | |
| Области | Информатика |
| Учреждения | Принстонский университет. Нью-Йоркский университет. Стэнфордский университет. Калифорнийский университет, Беркли. Корнелл Университет. Microsoft Research. Intertrust Technologies. Hewlett-Packard. Compaq. NEC Research. Bell Labs |
| Диссертация | Эффективный алгоритм планарности (1972) |
| Докторант | Роберт В. Флойд |
| Другие научные консультанты | Дональд Кнут |
| Докторанты | |
| Веб-сайт | www.cs.princeton.edu / ~ ret / |
Роберт Эндре Тарджан ( родился 30 апреля 1948 г.), американский компьютерный ученый и математик. Он является первооткрывателем нескольких алгоритмов графа, в том числе автономного алгоритма наименьших общих предков Тарьяна, и соавтором обоих расширенных деревьев и Фибоначчи. кучи. В настоящее время Тарджан является Джеймсом С. Макдоннеллом заслуженным профессором компьютерных наук в Принстонском университете и главным научным сотрудником Intertrust Technologies Corporation.
Он родился в Помоне, Калифорния. Его отец был детским психиатром, специализирующимся на умственной отсталости, и руководил государственной больницей. В детстве Тарджан читал много научной фантастики и хотел стать астрономом. Он заинтересовался математикой после прочтения статьи Мартина Гарднера о математических играх в Scientific American. Он серьезно заинтересовался математикой в восьмом классе благодаря «очень стимулирующему» учителю.
В старших классах Тарьян устроился на работу, где работал с подборщиками перфокарт IBM. Впервые он работал с настоящими компьютерами, изучая астрономию в Летней научной программе в 1964 году.
Тарджан получил степень бакалавра по математике в Калифорнийском институте Технологии в 1969 году. В Стэнфордском университете он получил степень магистра компьютерных наук в 1971 году и докторскую степень в области компьютерных наук (с дополнительным знанием математики) в 1972. В Стэнфорде им руководили Роберт Флойд и Дональд Кнут, оба выдающиеся компьютерные ученые и его доктор философии. Диссертация была Эффективный алгоритм планарности. Тарджан выбрал информатику в качестве области своих интересов, потому что считал, что информатика - это способ заниматься математикой, который может иметь практическое значение.
Тарьян преподавал в Принстонском университете. с 1985 года. Он также занимал академические должности в Корнельском университете (1972–73), Калифорнийском университете, Беркли (1973–1975), Стэнфордском университете ( 1974–1980) и Нью-Йоркский университет (1981–1985). Он также был научным сотрудником Исследовательского института NEC (1989–1997). В апреле 2013 года он присоединился к Microsoft Research Silicon Valley в дополнение к должности в Принстоне. В октябре 2014 года он вернулся в Intertrust Technologies в качестве главного научного сотрудника.
Тарьян работал в ATT Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014 – настоящее время), Compaq (2002) и Hewlett Packard (2006–2013).
Тарьян известен своими новаторскими работами над алгоритмами теории графов и структурами данных. Некоторые из его хорошо известных алгоритмов включают в себя автономный алгоритм наименее общих предков Тарьяна и алгоритм сильно связанных компонентов Тарьяна, и он был одним из пяти соавторов медиана медиан линейное время алгоритм выбора. Алгоритм Хопкрофта – Тарьяна проверки планарности был первым алгоритмом линейного времени для проверки планарности.
Тарьян также разработал важные структуры данных, такие как куча Фибоначчи ( структура данных кучи, состоящая из леса деревьев), и splay tree (самонастраивающееся двоичное дерево поиска; совместно изобретено Тарьаном и Дэниелом Слейтором ). Другим значительным вкладом стал анализ структуры данных с непересекающимся набором ; он был первым, кто доказал оптимальное время выполнения с использованием обратной функции Аккермана.
Тарьян получил Премию Тьюринга совместно с Джоном Хопкрофтом в 1986 году. Цитата для награды гласит, что она была:
За фундаментальные достижения в разработке и анализе алгоритмов и структур данных.
Тарьян был также избран членом ACM в 1994 году. Эта награда гласит:
За выдающиеся достижения в разработке и анализе структур данных и алгоритмов.
Некоторые из других наград, присуждаемых Тарьяну, включают:
Тарьян имеет как минимум 18 патентов США. К ним относятся:
