Роберт Эндре Тарджан (; ; род. 30 апреля 1948 года, Помона, США) — американский учёный в области теории вычислительных систем.
Автор множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка, соавтор ряда важных структур данных, в том числе фибоначчиевой кучи и расширяющегося дерева. Концептуализировал понятие амортизационного анализа.
Доктор философии (1972), заслуженный профессор Принстонского университета, где преподаёт с 1985 года, старший фелло . Член Американского философского общества (1990), Национальной академии наук и Инженерной академии США.
Ранние годы Отец — Джордж Тарджан (Дьёрдь Тарьян, 1912—1991) — уроженец Жолны и выпускник медицинского факультета Будапештского университета, эмигрировал в США в 1939 году, тогда как его оставшиеся в Чехословакии родители и брат в силу еврейского происхождения были заключены в концентрационный лагерь; в США стал детским психиатром и был избран президентом Американской психиатрической ассоциации. Дед — политик и политолог (Вайс, 1882—1946), основатель , автор книг по региональной политике в отношении национальных меньшинств. Брат — шахматный гроссмейстер Джеймс Тарджан.
В детстве читал много научной фантастики и хотел стать астрономом. Математикой заинтересовался после прочтения заметок Мартина Гарднера по математическим играм в журнале «Scientific American». Серьёзный интерес к математике привил ему в восьмом классе «очень мотивирующий» учитель.
Во время обучения в школе имел возможность поработать в IBM с сортировально-подборочной машиной для перфокарт. В 1964 году в летней школе получил первый серьёзный опыт работы с настоящими компьютерами.
Звание бакалавра по математике получил в Калифорнийском технологическом институте в 1969 году. В Стэнфордском университете получил магистерскую степень по информатике (1971) и степень доктора философии по информатике — в 1972 году, его научными руководителями в Стэнфорде были Роберт Флойд и Дональд Кнут, тема диссертации — «Эффективный алгоритм определения планарности графа».
Карьера С 1985 года — преподаватель в Принстонском университете, где ныне именной заслуженный Университетский профессор информатики (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 статей в рецензируемых журналах и монографиях.
Известен работами в области алгоритмов на графах. Наиболее яркие из них — оффлайновый алгоритм Тарьяна поиска ближайшего общего предка для многократного быстрого поиска самого глубокого узла дерева, являющегося общим предком двух заданных узлов, и алгоритм Тарьяна вычисления сильно связных компонент. Алгоритм Хопкрофта — Тарьяна стал первым линейным алгоритмом определения планарности графа.
Разработал ряд важнейших структур данных, таких как фибоначчиева куча, система непересекающихся множеств и расширяющееся дерево (, один из видов сбалансированного двоичного дерева поиска; в соавторстве с .
Награды В 1986 году совместно с Джоном Хопкрофтом стал лауреатом премии Тьюринга «за фундаментальные результаты в области разработки и анализа алгоритмов и структур данных».
Избран действительным членом ACM (ACM Fellow) в 1994 году «за плодотворный труд в области разработки и анализа алгоритмов и структур данных».
Другие награды: Стипендия Гуггенхайма (1978) Премия Неванлинны (1982) — первый лауреат этой премии (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.
Примечания
Библиографические ссылки
OCLC entries for Robert E Tarjan DBLP entry for Robert Endre Tarjan
Ссылки DBLP: Robert Endre Tarjan Robert Tarjan’s home page at Princeton.
Категория:Программисты США Категория:Математики по алфавиту Категория:Математики США Категория:Учёные в области информатики США Категория:Члены Национальной академии наук США Категория:Члены Американского философского общества Категория:Преподаватели Корнеллского университета Категория:Преподаватели Принстонского университета Категория:Профессора Принстонского университета Категория:Выпускники Инженерной школы Стэнфордского университета Категория:Выпускники Стэнфордского университета Категория:Выпускники Калифорнийского технологического института Категория:Авторы книг о компьютерах Категория:Стипендиаты Гуггенхайма Категория:Лауреаты премии Тьюринга Категория:Лауреаты премии Канеллакиса Категория:Лауреаты премии Неванлинны