Роберт Тарьян: Грамматика эффективных алгоритмов

Попросите любого студента-информатика проследить путь графа с помощью поиска в глубину, и он, знает он об этом или нет, выполняет технику, которую Роберт Тарьян превратил из любопытного факта в дисциплину. Его статья 1972 года «Поиск в глубину и алгоритмы линейных графов» сегодня читается как фундаментальный учебник грамматики — работа, настолько глубоко поглощенная областью, что имя ее автора почти исчезло из того, как люди говорят о ней, даже несмотря на то, что его имя привязано к полудюжине структур, которые они используют каждый день.

Путь математика к машинам

Роберт Эндре Тарьян родился 30 апреля 1948 года в Помоне, Калифорния, в семье Джорджа Тарьяна, детского психиатра, специализирующегося на интеллектуальных нарушениях; его младший брат Джеймс стал гроссмейстером по шахматам. В детстве Тарьян хотел стать астрономом, пока колонки головоломок Мартина Гарднера в Scientific American и вдохновляющий учитель в восьмом классе не подтолкнули его к математике. Он получил степень бакалавра математики в Калтехе в 1969 году, затем поступил в Стэнфорд, где получил степень магистра компьютерных наук в 1971 году и докторскую степень в 1972 году, защитив диссертацию по алгоритмам планарности под руководством Роберта Флойда и Дональда Кнута. Позже он просто опишет свой выбор области: компьютерные науки — это способ заниматься математикой, которая может иметь практическое применение, — фраза, которая также служит описанием всей его работы.

Создание инструментария

Карьера Тарьяна, охватившая Корнелл, Калифорнийский университет в Беркли, Стэнфорд, AT&T Bell Labs, Нью-Йоркский университет, NEC Research Institute, Microsoft Research, Compaq, Hewlett Packard и Intertrust Technologies, прежде чем он обосновался в Принстоне в 1985 году в качестве заслуженного профессора университета имени Джеймса С. Макдоннелла, породила совокупность алгоритмов и структур данных, необычную тем, сколько из них стали несущей инфраструктурой, а не теоретическими курьезами. Его имя связано с алгоритмом Тарьяна для поиска сильно связных компонентов в графе, автономным алгоритмом для вычисления наименьших общих предков и алгоритмом линейного времени для поиска мостов — все это методы, построенные на основе структуры поиска в глубину, которую он формализовал. В 1975 году он представил первый точный анализ структуры данных union-find в сочетании со сжатием путей, доказав ее почти постоянное амортизированное время выполнения с использованием обратной функции Аккермана, результат, настолько тесно связанный с реальной производительностью, что теперь он лежит в основе всего, от алгоритма минимального остовного дерева Краскала до оптимизации компиляторов. Вместе с Дэниелом Слитором в Bell Labs он стал соавтором splay-деревьев, саморегулирующихся бинарных деревьев поиска, которые перебалансируются в процессе использования, а не за счет хранения явных метаданных баланса, и с их помощью стал пионером конкурентного анализа, структуры для оценки онлайн-алгоритмов против всезнающего противника. Вместе с Майклом Фредманом он разработал фибоначчиевы кучи в 1985 году, структуру приоритетной очереди, которая сделала алгоритм кратчайшего пути Дейкстры и алгоритмы сетевой оптимизации асимптотически быстрее всего, что было до этого. Его учебник Data Structures and Network Algorithms получил премию Фредерика У. Ланкастера и стал стандартным чтением в этой области.

Прорыв в планарности с Хопкрофтом

Единственным достижением, наиболее явно отмеченным в его цитировании премии Тьюринга, является совместная работа с Джоном Хопкрофтом: первый алгоритм линейного времени для проверки того, можно ли нарисовать граф на плоскости без пересечения ребер, опубликованный в 1974 году. Проверка планарности была медленной и громоздкой проблемой, пока их алгоритм не свел ее к вопросу тщательного обхода в глубину — технике, настолько центральной для их решения, что предыдущая формализация поиска в глубину Тарьяном стала, в ретроспективе, инструментом, который сделал результат Хопкрофта-Тарьяна возможным. Оба разделили премию ACM Тьюринга 1986 года «за фундаментальные достижения в проектировании и анализе алгоритмов и структур данных», цитата, которая отмечает совокупность совместных и параллельных работ, а не какую-то одну статью.

Признание на протяжении четырех десятилетий

Тарьян стал первым лауреатом премии Неванлинны в области информатики в 1983 году, отметившей выдающийся вклад в математические аспекты компьютерных наук. Он получил премию Тьюринга в 1986 году, был избран в Американскую академию искусств и наук в 1985 году, Национальную академию наук в 1987 году и Национальную инженерную академию в 1988 году. Он получил премию Парижа Канеллакиса в области теории и практики в 1999 году и награду выдающегося выпускника Калтеха в 2010 году. Его послужной список публикаций насчитывает более 250 статей с десятками тысяч цитирований, и он владеет более чем дюжиной патентов США в области структур данных и безопасности, что отражает карьеру, которая плавно перемещалась между академической теорией в Принстоне и прикладными исследованиями в промышленных лабораториях, таких как Bell Labs, NEC и Microsoft.

Почему Роберта называют гением

Аргумент Тарьяна в пользу этого слова основан на чем-то конкретном: он не просто решал отдельные сложные задачи, он идентифицировал лежащий в основе комбинаторный механизм — поиск в глубину, амортизированный анализ, саморегулирование, — который сделал быстрым целые классы ранее медленных алгоритмов, и он делал это неоднократно на протяжении четырех десятилетий, а не один раз. Анализ union-find и алгоритм планарности Хопкрофта-Тарьяна остаются материалом учебников именно потому, что это не хитрые трюки, а общие методы, которые другие исследователи могли повторно использовать; эта возможность повторного использования, больше, чем любой отдельный результат, — это то, что вознаграждали комитеты премии Неванлинны и премии Тьюринга. Честная сложность заключается в том, что его самый знаменитый результат, алгоритм планарности линейного времени, является явно совместной работой с Джоном Хопкрофтом, и цитирование премии Тьюринга отмечает обоих мужчин совместно, а не коронует кого-то одного как одинокого гения — сама премия является доказательством того, что область рассматривает это как совместное достижение, а не как единичное изобретение. Другие знаковые результаты Тарьяна были аналогичным образом построены с названными соавторами: splay-деревья с Дэниелом Слитором, фибоначчиевы кучи с Майклом Фредманом. Неоспоримым является огромная плотность фундаментальных, до сих пор преподаваемых результатов, носящих его имя, рекорд, с которым мало кто в этой области может сравниться.

Наследие

Каждый студент-информатик, изучающий поиск в глубину, union-find, splay-деревья или фибоначчиевы кучи, по сути, до сих пор учится по статьям Тарьяна, спустя десятилетия после их написания. Его работа лежит в основе компиляторов, сетевой маршрутизации и географических информационных систем, при этом большинство пользователей даже не знают его имени — тихая судьба математики инфраструктурного уровня, которая полностью преуспела. Он продолжал выдавать новые результаты, будучи уже за семьдесят, перемещаясь между преподавательской деятельностью в Принстоне и ролями главного научного сотрудника в Intertrust Technologies и исследователя в Microsoft и Hewlett Packard, форма карьеры, которая сама по себе выступает против того, чтобы рассматривать его как чисто академическую фигуру: большая часть его наиболее цитируемых работ была выполнена, протестирована и применена в промышленных исследовательских лабораториях, а не в университетском вакууме. Эта двойная жизнь, публикация строгой математики при одновременном патентовании практических систем, — это часть того, что отделяет его послужной список от теоретиков, чьи идеи остались ограниченными журналами.