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

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:К переименованию Шаблон:Плохой перевод Шаблон:Учёный

Роберт Эндре Тарджан (Шаблон:Lang-en; Шаблон:IPAc-en[1]; род. 30 апреля 1948, Помона, США) — американский учёный в области теории вычислительных систем.

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

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

Ранние годы

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

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

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

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

Карьера

С 1985 года — преподаватель в Принстонском университете[8], где ныне именной заслуженный Университетский профессор информатики (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 статей в рецензируемых журналах и монографиях.

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

Разработал ряд важнейших структур данных, таких как фибоначчиева куча, система непересекающихся множеств и расширяющееся дерево (Шаблон:Lang-en, один из видов сбалансированного двоичного дерева поиска; в соавторстве с Дэниелом Слитором).

Награды

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

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

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

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

Примечания

Шаблон:Примечания

Библиографические ссылки

Ссылки

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

  1. ↑ Шаблон:Cite web
  2. ↑ Шаблон:Cite web
  3. ↑ Oral history interview with Peter Tarjan
  4. ↑ In memoriam George Tarjan, M.D. 1912—1991
  5. ↑ 5,0 5,1 Шаблон:Книга
  6. ↑ Ödön Tarján — Politician, Entrepreneur and Freemason
  7. ↑ Шаблон:Cite web
  8. ↑ 8,0 8,1 Шаблон:Cite web
  9. ↑ Шаблон:Книга
  10. ↑ Шаблон:Cite web
  11. ↑ Шаблон:Cite web

Шаблон:Выбор языка Шаблон:Премия Тьюринга

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Тарджан,_Роберт&oldid=10908887