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

Роберт Тарьян — американский учёный в области информатики, один из ведущих специалистов по теории графов, структурам данных и алгоритмам. Наиболее известен как соавтор алгоритма Тарьяна для поиска сильно связных компонент в ориентированном графе, а также как разработчик ряда фундаментальных алгоритмов на графах, таких как алгоритм поиска минимального остовного дерева (алгоритм Борувки — Тарьяна) и алгоритм поиска наименьшего общего предка (LCA). Лауреат Премии Тьюринга (1986) — высшей награды в области информатики.

Биография

Роберт Эндрю Тарьян родился 30 апреля 1948 года в городе Помона, штат Калифорния, США. Его отец, Джеймс Тарьян, был врачом, а мать, Рут Тарьян, — учительницей. С раннего возраста Роберт проявлял интерес к математике и логике. В 1969 году он получил степень бакалавра по математике в Калифорнийском технологическом институте (Калтех). Затем он продолжил обучение в Стэнфордском университете, где в 1971 году защитил магистерскую диссертацию, а в 1972 году — докторскую диссертацию по информатике под руководством Роберта Флойда.

После защиты диссертации Тарьян работал в Корнеллском университете (1972–1973), затем в Калифорнийском университете в Беркли (1973–1974), а с 1974 по 1981 год — в Стэнфордском университете. В 1981 году он перешёл в Bell Labs (ныне Nokia Bell Labs), где работал до 1985 года. С 1985 года он является профессором Принстонского университета, а также сотрудником Hewlett-Packard Laboratories (2002–2013) и Google (с 2013 года).

Научные достижения

Алгоритмы на графах

Тарьян внёс значительный вклад в теорию графов и разработку эффективных алгоритмов. Его ключевые работы включают:

• Алгоритм Тарьяна для поиска сильно связных компонент (1972). Этот алгоритм, основанный на обходе графа в глубину (DFS), позволяет за линейное время O(V+E) найти все сильно связные компоненты в ориентированном графе. Он широко применяется в компиляторах, анализе социальных сетей и веб-графов.
• Алгоритм поиска минимального остовного дерева (алгоритм Борувки — Тарьяна, 1976). Совместно с Джоном Хопкрофтом Тарьян разработал эффективный алгоритм, который находит минимальное остовное дерево за время O(E log log V) или O(E α(V)), где α — обратная функция Аккермана.
• Алгоритм поиска наименьшего общего предка (LCA) (1984). Совместно с Барбарой Симонс разработал алгоритм, который позволяет находить наименьшего общего предка двух узлов в дереве за время O(1) после предварительной обработки за O(N).
• Алгоритм поиска мостов и точек сочленения (1972). Тарьян предложил алгоритмы, которые за линейное время находят все мосты и точки сочленения в неориентированном графе.

Структуры данных

Тарьян внёс вклад в разработку и анализ структур данных:

• Система непересекающихся множеств (Union-Find). Тарьян совместно с Джоном Хопкрофтом и Робертом Флойдом проанализировал асимптотическую сложность операций объединения и поиска, показав, что время выполнения составляет O(α(V)), где α — обратная функция Аккермана.
• Стек Тарьяна — структура данных, используемая в алгоритме поиска сильно связных компонент.
• Сбалансированные деревья (например, красно-чёрные деревья). Тарьян участвовал в разработке и анализе алгоритмов балансировки деревьев.

Анализ алгоритмов

Тарьян внёс вклад в амортизационный анализ, метод оценки времени выполнения алгоритмов, при котором учитывается среднее время на одну операцию в последовательности. Он применил этот метод для анализа сложности операций в системах непересекающихся множеств и других структурах данных.

Премии и награды

• Премия Тьюринга (1986) — совместно с Джоном Хопкрофтом за фундаментальные достижения в области разработки и анализа алгоритмов и структур данных.
• Премия Неймана (1990) — за вклад в компьютерные науки.
• Премия Стила (1995) — за выдающийся вклад в математику и информатику.
• Премия Кнута (2004) — за выдающиеся достижения в области информатики.
• Член Национальной академии наук США (1990).
• Член Американской академии искусств и наук (1991).

Влияние и наследие

Работы Роберта Тарьяна оказали глубокое влияние на развитие информатики. Его алгоритмы широко используются в современных программных системах, включая компиляторы, базы данных, операционные системы и системы обработки графов. Тарьян является автором более 200 научных статей и нескольких книг, включая «Data Structures and Network Algorithms» (1983) и «Algorithms for Minimum Spanning Trees» (1990). Он также является одним из наиболее цитируемых учёных в области информатики.

Интересные факты

• Тарьян является одним из немногих учёных, получивших Премию Тьюринга в возрасте 38 лет.
• Он является соавтором алгоритма, который используется в поисковых системах для анализа веб-графов.
• Тарьян активно занимается преподавательской деятельностью и подготовил более 20 докторов наук.

Критика

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

Источники

• Тарьян, Роберт. «Data Structures and Network Algorithms». SIAM, 1983.
• Хопкрофт, Джон; Тарьян, Роберт. «Efficient Algorithms for Graph Manipulation». Communications of the ACM, 1973.
• Тарьян, Роберт. «Depth-First Search and Linear Graph Algorithms». SIAM Journal on Computing, 1972.
• Премия Тьюринга: Роберт Тарьян. ACM, 1986.
• Национальная академия наук США: Роберт Тарьян. NAS, 1990.