Это не официальный сайт wikipedia.org 01.01.2023

Тарджан, Роберт — Википедия
Википедия

Тарджан, Роберт

Роберт Андре Тарджан (англ. Robert Endre Tarjan; /ˈrɔːbət ˈtɑrdʒæn/[4]; род. 30 апреля 1948, Помона, США) — американский учёный в области теории вычислительных систем.

Роберт Тарджан
англ. Robert E. Tarjan
Bob Tarjan.jpg
Дата рождения 30 апреля 1948(1948-04-30) (74 года)
Место рождения Помона (штат Калифорния, США)
Страна
Научная сфера Информатика
Место работы Принстонский университет
Hewlett-Packard
Альма-матер Калифорнийский технологический институт,
Стэнфордский университет
Учёная степень доктор философии Стэнфорда (1972)
Научный руководитель Роберт Флойд[3]
Награды и премии Премия Неванлинны (1982)
Премия Тьюринга (1986)
Логотип Викисклада Медиафайлы на Викискладе

Он является автором множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка (Tarjan’s off-line least common ancestors algorithm). Также он является соавтором структур данных «Фибоначчиева куча» и «Расширяющееся дерево». Ввел термин Амортизационный анализ.

Доктор философии (1972), заслуженный Университетский профессор Принстона, где преподает с 1985 года, старший фелло HP Labs[en]. Член Американского философского общества (1990)[5], Национальных Академии наук и Инженерной академии США.

Ранние годыПравить

Его отец Джордж Тарджан (1912—1991), уроженец Жолны и выпускник медицинского факультета Будапештского университета, эмигрировал в США в 1939 году, тогда как его оставшиеся в Чехословакии родители и брат в силу еврейского происхождения были заключены в концентрационный лагерь[6]; в США он стал детским психиатром и был избран президентом Американской психиатрической ассоциации[7][8]. Дед — политик и политолог Одон Тарджан (Вайс, 1882—1946), основатель Словацкой венгерской партии, автор книг по региональной политике в отношении национальных меньшинств[9]. Брат — шахматный гроссмейстер Джеймс Тарджан.

В детстве он читал много научной фантастики и хотел стать астрономом. Роберт заинтересовался математикой после прочтения заметок Мартина Гарднера по математическим играм в журнале Scientific American. Серьёзный интерес к математике привил ему в восьмом классе «очень мотивирующий» учитель.

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

Тарджан получил звание бакалавра по математике в технологическом институте Калифорнии (California Institute of Technology) в 1969 году. В Стэнфордском университете он получил магистерскую степень по компьютерным наукам (1971) и степень доктора философии (Doctor of Philosophy) в компьютерных науках — в 1972 г. Его научными руководителями в Стэнфорде были Роберт Флойд и Дональд Кнут, диссертация называлась «Эффективный алгоритм определения планарности графа» (An Efficient Planarity Algorithm)[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) (один из видов сбалансированного двоичного дерева поиска; в соавторстве с Дэниелом Слитором).

Сегодня Роберт Тарджан заслуженный профессор компьютерных наук (James S. McDonnell Distinguished University Professor of Computer Science) в университете Принстона, а также работает в Hewlett-Packard[13].

НаградыПравить

Тарджан получил Премию Тьюринга вместе с Джоном Хопкрофтом в 1986 г. В сопроводительном тексте к награде написано:

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

Тарьян также был избран членом ACM (ACM Fellow) в 1994. В поздравительном тексте [1] указано:

За плодотворный труд в области разработки и анализа алгоритмов и структур данных.

Другие награды Роберта Тарджана:

В конце февраля 2009 года Тарджан занимает 39 место в списке самых цитируемых авторов в проекте CiteSeer[15].

ПримечанияПравить

  1. ↑ http://www.researchgate.net/publication/222775875_Updating_a_balanced_search_tree_in_O(1)_rotations
  2. ↑ http://www.in.com/robert-tarjan/profile-238439.html
  3. ↑ Математическая генеалогия (англ.) — 1997.
  4. ↑ Robert Tarjan pronunciation: How to pronounce Robert Tarjan in English  (неопр.). Дата обращения: 7 августа 2019. Архивировано 7 августа 2019 года.
  5. ↑ APS Member History  (неопр.). Дата обращения: 28 марта 2022. Архивировано 26 марта 2022 года.
  6. ↑ Oral history interview with Peter Tarjan
  7. ↑ In memoriam George Tarjan, M.D. 1912—1991
  8. ↑ 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.
  9. ↑ Ödön Tarján — Politician, Entrepreneur and Freemason
  10. ↑ Robert Endre Tarjan  (неопр.). Mathematics Genealogy Project. Дата обращения: 9 января 2008. Архивировано 17 марта 2012 года.
  11. ↑ 1 2 Robert Endre Tarjan: The art of the algorithm (interview) (англ.). Hewlett-Packard (September 2004). Дата обращения: 9 января 2008. Архивировано 17 марта 2012 года.
  12. ↑ Kocay, William; Kreher, Donald L. Planar Graphs // Graphs, algorithms, and optimization (неопр.). — Boca Raton, 2005. — С. 312. — ISBN 978-1584883968.
  13. ↑ HP Fellows: Robert Endre Tarjan (англ.) (недоступная ссылка — история). Hewlett-Packard. Дата обращения: 9 января 2008. Архивировано 17 марта 2012 года.
  14. ↑ Robert E. Tarjan (англ.). John Simon Guggenheim Foundation. gf.org. Дата обращения: 9 апреля 2019. Архивировано 26 января 2020 года.
  15. ↑ 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

СсылкиПравить

Источник — https://ru.wikipedia.org/w/index.php?title=Тарджан,_Роберт&oldid=129264412