stringtranslate.com

Роберт Тарьян

Роберт Эндре Тарьян (родился 30 апреля 1948 года) — американский учёный-компьютерщик и математик . Он является первооткрывателем нескольких алгоритмов теории графов , включая алгоритм сильно связанных компонентов , и соавтором как распластанных деревьев, так и куч Фибоначчи . В настоящее время Тарьян является почётным профессором университета имени Джеймса С. Макдоннелла по компьютерным наукам в Принстонском университете .

Личная жизнь и образование

Он родился в Помоне, Калифорния . Его отец, Джордж Тарьян (1912-1991), выросший в Венгрии, [1] был детским психиатром, специализирующимся на умственной отсталости, и управлял государственной больницей. [2] Младший брат Роберта Тарьяна Джеймс стал гроссмейстером по шахматам. [3] В детстве Роберт Тарьян много читал научной фантастики и хотел стать астрономом . Он заинтересовался математикой после прочтения колонки Мартина Гарднера о математических играх в Scientific American . Он серьезно заинтересовался математикой в ​​восьмом классе благодаря «очень стимулирующему» учителю. [4]

Во время учебы в старшей школе Тарьян устроился на работу, где он работал с IBM-коллабораторами перфокарт. Впервые он работал с настоящими компьютерами, изучая астрономию на Летней научной программе в 1964 году. [2]

Тарьян получил степень бакалавра по математике в Калифорнийском технологическом институте в 1969 году. В Стэнфордском университете он получил степень магистра по информатике в 1971 году и степень доктора философии по информатике (с дополнительной специальностью по математике) в 1972 году. В Стэнфорде его научными руководителями были Роберт Флойд [5] и Дональд Кнут [6] , оба выдающиеся специалисты по информатике, а его докторская диссертация была посвящена теме «Эффективный алгоритм планарности» . Тарьян выбрал информатику в качестве области своих интересов, поскольку считал, что информатика — это способ заниматься математикой, который может иметь практическое значение. [7]

Сейчас Тарьян живет в Принстоне, штат Нью-Джерси, и Кремниевой долине. Он женат на Найле Ризк. [8] У него три дочери: Элис Тарьян, Софи Завацки и Максин Тарьян. [9]

Карьера в области компьютерных наук

Тарьян преподает в Принстонском университете с 1985 года. [7] Он также занимал академические должности в Корнеллском университете (1972–73), Калифорнийском университете в Беркли (1973–1975), Стэнфордском университете (1974–1980) и Нью-Йоркском университете (1981–1985). Он также был научным сотрудником Исследовательского института NEC (1989–1997). [10] В апреле 2013 года он присоединился к Microsoft Research Silicon Valley в дополнение к должности в Принстоне. В октябре 2014 года он вернулся в Intertrust Technologies в качестве главного ученого.

Тарьян работал в AT&T Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014–настоящее время), Compaq (2002) и Hewlett Packard (2006–2013).

Алгоритмы и структуры данных

Тарьян известен своей новаторской работой по алгоритмам теории графов и структурам данных. Некоторые из его известных алгоритмов включают офлайновый алгоритм наименьших общих предков Тарьяна , алгоритм сильно связанных компонентов Тарьяна и алгоритм поиска мостов Тарьяна , и он был одним из пяти соавторов алгоритма линейного времени выбора медианы медиан . Алгоритм проверки планарности Хопкрофта-Тарьяна был первым линейным алгоритмом для проверки планарности. [11]

Тарьян также разработал важные структуры данных, такие как куча Фибоначчи (структура данных кучи, состоящая из леса деревьев) и splay tree (самонастраивающееся двоичное дерево поиска; совместно изобретено Тарьяном и Дэниелом Слейтором ). Другим значительным вкладом стал анализ структуры данных непересекающихся множеств ; он был первым, кто доказал оптимальное время выполнения, включающее обратную функцию Аккермана . [12]

Награды

Тарьян получил премию Тьюринга совместно с Джоном Хопкрофтом в 1986 году. В документе о присуждении премии указано [10] , что она была:

За фундаментальные достижения в разработке и анализе алгоритмов и структур данных.

В 1994 году Тарьян был также избран членом ACM. В постановлении о присуждении этой награды говорится: [13]

За основополагающие достижения в проектировании и анализе структур данных и алгоритмов.

Среди других наград Тарьяна можно отметить:

Избранные публикации

Статьи Тарьяна были процитированы в общей сложности более 94 000 раз. [20] Среди наиболее цитируемых:

Патенты

Тарьян имеет не менее 18 патентов США. [6] К ним относятся:

Примечания

  1. ^ "Евреи — лауреаты премии имени А. М. Тьюринга от ACM". jinfo.org .
  2. ^ ab Шаша, Деннис Эллиотт; Лазер, Кэти А. (1998) [1995]. "Роберт Э. Тарьян: В поисках хорошей структуры". Вне их разума: жизни и открытия 15 великих ученых-компьютерщиков . Copernicus/Springer. стр. 102–119. ISBN 978-0-387-97992-2. OCLC  32240355.
  3. ^ Мелвин, Шабсин (август 1984 г.). «Джордж Тарджан, доктор медицины, сто двенадцатый президент, 1983–1984». Американский журнал психиатрии . 141 (8): 931–934. doi :10.1176/ajp.141.8.931.
  4. ^ "Роберт Тарьян: Искусство алгоритма". Hewlett-Packard . Получено 2010-09-05 .
  5. ^ "Роберт Эндре Тарьян". Проект генеалогии математики . Получено 2008-01-09 .
  6. ^ ab Tarjan, Robert Endre (15 ноября 2019 г.). "Curriculum Vitae" (PDF) . Архивировано из оригинала (PDF) 2019-11-23 . Получено 2019-11-23 .
  7. ^ ab "Роберт Эндре Тарьян: Искусство алгоритма (интервью)". Hewlett-Packard. Сентябрь 2004 г. Получено 09.01.2008 г.
  8. ^ «Найла Ризк и Роберт Тарджан». Нью-Йорк Таймс . Июль 2013.
  9. ^ "Фотографии с симпозиума в честь 60-летия Боба Тарьяна". ​​DIMACS. Май 2008 г.
  10. ^ abcde King, V. "Роберт Э. Тарьян — лауреат премии имени А. М. Тьюринга". ACM . Получено 19 января 2014 г.
  11. ^ Kocay, William; Kreher, Donald L (2005). "Planar Graphs". Графы, алгоритмы и оптимизация . Boca Raton: Chapman & Hall/CRC. стр. 312. ISBN 978-1-58488-396-8. OCLC  56319851.
  12. ^ Тарьян, Роберт Э .; ван Лиувен, Ян (1984). «Анализ алгоритмов объединения множеств в худшем случае». Журнал ACM . 31 (2): 245–281. doi : 10.1145/62.2160 . S2CID  5363073.
  13. ^ "Fellows Award — Robert E. Tarjan". ACM . 25 сентября 1998 г. Получено 18 ноября 2005 г.
  14. ^ "Лауреаты премии Рольфа Неванлинны". Международный математический союз . Архивировано из оригинала 2008-12-27 . Получено 2014-01-19 .
  15. ^ "Роберт Эндре Тарьян". Американская академия искусств и наук . Получено 15 июня 2020 г.
  16. ^ "Роберт Тарьян". www.nasonline.org . Получено 2020-06-15 .
  17. ^ "Доктор Роберт Э. Тарджан". Сайт НАЭ . Проверено 15 июня 2020 г.
  18. ^ "История членства в APS". search.amphilsoc.org . Получено 2022-04-19 .
  19. ^ "Caltech Names Five Distinguished Alumni" (пресс-релиз). Калифорнийский технологический институт . 2010-03-15. Архивировано из оригинала 2010-10-10 . Получено 2010-08-26 .
  20. ^ "Robert Tarjan Google Scholar Page". Google Scholar . Получено 6 марта 2023 г. .
  21. ^ Тарьян, Роберт (1 июня 1972 г.). «Поиск в глубину и линейные графовые алгоритмы». Журнал SIAM по вычислениям . 1 (2): 146–160. doi :10.1137/0201010. ISSN  0097-5397. S2CID  16467262.
  22. ^ Фредман, Майкл Л.; Тарьян, Роберт Эндре (1987-07-01). «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации». Журнал ACM . 34 (3): 596–615. doi : 10.1145/28869.28874 . ISSN  0004-5411. S2CID  7904683.
  23. ^ "Back Matter". Структуры данных и сетевые алгоритмы : 125–131. Январь 1983. doi :10.1137/1.9781611970265.bm. ISBN 978-0-89871-187-5.
  24. ^ Голдберг, Эндрю В.; Тарьян, Роберт Э. (1988-10-01). «Новый подход к проблеме максимального потока». Журнал ACM . 35 (4): 921–940. doi : 10.1145/48014.61051 . ISSN  0004-5411. S2CID  14492800.
  25. ^ Бентли, Джон Л.; Слейтор, Дэниел Д.К.; Тарьян, Роберт Э. (3 января 1989 г.). «Патент США 4796003 — Сжатие данных».
  26. ^ Нина, Мишра; Шрайбер, Роберт Сэмюэл; Роберт Э., Тарьян (19 октября 2010 г.). «Патент США 7818272 — Метод обнаружения кластеров объектов в произвольном неориентированном графе с использованием разницы между долей внутренних связей и максимальной долей связей внешнего объекта».
  27. ^ Пинкас, Биньямин; Хабер, Стюарт А.; Тарьян, Роберт Э.; Сандер, Томас (10 июля 2012 г.). «Патент США 8220036 — Установление безопасного канала с пользователем-человеком».

Ссылки

Внешние ссылки

На Викискладе есть медиафайлы по теме Роберт Тарьян.