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

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

Автор множества алгоритмов решения задач теории графов и дискретной математики , включая алгоритм поиска наименьшего общего предка , соавтор ряда важных структур данных, в том числе фибоначчиевой кучи и расширяющегося дерева . Концептуализировал понятие амортизационного анализа .

Доктор философии (1972), заслуженный профессор Принстонского университета , где преподаёт с 1985 года, старший фелло . Член Американского философского общества (1990) , Национальной академии наук и .

Ранние годы

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

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

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

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

Карьера

С 1985 года — преподаватель в Принстонском университете , где ныне именной заслуженный Университетский профессор информатики ( James S. McDonnell Distinguished University Professor ). У него также были академические должности в Корнеллском университете (1972—1974), Калифорнийском университете в Беркли (1973—1975), Стэнфордском университете (1974—1981), Нью-Йоркском университете (1981—1985). Также был членом (1989—1997) и числится (на должности Visiting Scientist) в Массачусетском технологическом институте (1996).

Работал в AT&T Bell Labs (1980—1989), (1997—2001), Compaq (2002) и Hewlett-Packard , где продолжает работать с 2006 года. Избирался членом различных комитетов Ассоциации вычислительной техники (ACM) и Института инженеров электротехники и электроники (IEEE), а также работал редактором нескольких рецензируемых журналов.

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

Разработал множество эффективных алгоритмов и структур данных для решения различных прикладных задач. Опубликовал более 228 статей в рецензируемых журналах и монографиях.

Известен работами в области алгоритмов на графах. Наиболее яркие из них — для многократного быстрого поиска самого глубокого узла дерева, являющегося общим предком двух заданных узлов, и алгоритм Тарьяна вычисления сильно связных компонент . стал первым линейным алгоритмом определения планарности графа .

Разработал ряд важнейших структур данных , таких как фибоначчиева куча , система непересекающихся множеств и расширяющееся дерево ( англ. splay tree , один из видов сбалансированного двоичного дерева поиска; в соавторстве с .

Награды

В 1986 году совместно Джоном Хопкрофтом стал лауреатом премии Тьюринга «за фундаментальные результаты в области разработки и анализа алгоритмов и структур данных».

Избран действительным членом ACM (ACM Fellow) в 1994 году «за плодотворный труд в области разработки и анализа алгоритмов и структур данных».

Другие награды:

По состоянию на конец февраля 2009 года занимал 39-е место в списке самых цитируемых авторов в проекте CiteSeer .

Примечания

  1. (англ.) — 1997.
  2. . Дата обращения: 7 августа 2019. 7 августа 2019 года.
  3. . Дата обращения: 28 марта 2022. 26 марта 2022 года.
  4. . Дата обращения: 7 сентября 2022. 7 сентября 2022 года.
  5. . Дата обращения: 7 сентября 2022. 6 декабря 2022 года.
  6. 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 .
  7. . Дата обращения: 7 сентября 2022. 7 сентября 2022 года.
  8. . Mathematics Genealogy Project. Дата обращения: 9 января 2008. 17 марта 2012 года.
  9. (англ.) . Hewlett-Packard (September 2004). Дата обращения: 9 января 2008. 17 марта 2012 года.
  10. Kocay, William; Kreher, Donald L. Planar Graphs // (неопр.) . — Boca Raton, 2005. — С. . — ISBN 978-1584883968 .
  11. (англ.) . John Simon Guggenheim Foundation . gf.org. Дата обращения: 9 апреля 2019. 26 января 2020 года.
  12. . Дата обращения: 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 .
  • for Robert E Tarjan
  • for Robert Endre Tarjan

Ссылки

  • .
Источник —

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