В 2024 году легендарный профессор Стэнфордского университета Дональд Кнут провёл открытую лекцию, в которой поделился новостями о завершении своей многолетней работы над очередным выпуском фундаментального труда «Искусство программирования», а также признался в любви к конкретному математическому методу. В центре внимания выдающегося учёного оказались структуры данных, а именно — алгоритм Роберта Тарьяна для поиска сильно связанных компонент в графах. Рассказ профессора объединил строгую математику, личные воспоминания о великих математиках прошлого и уникальные исторические анекдоты.
📚 Долгожданная книга и «удовлетворение ограничений» 0:11
Своё выступление Дональд Кнут начал с математической шутки о числе 28, назвав его совершенным, и выразил надежду, что сможет прочитать столь же «совершенную» лекцию. Главной же новостью дня стало завершение работы над интерьером его новой книги: рукопись была официально отправлена издателю. Профессор объявил, что читатели уже могут оформить предварительный заказ. Несмотря на то, что печать физического тиража вряд ли завершится к Рождеству, дизайн обложки уже утверждён, а официальная дата публикации назначена на 3 февраля.
Новая работа получила название «Удовлетворение ограничений» (Constraint Satisfaction) и представляет собой выпуск 7 тома 4 (Fascicle 7, Volume 4). Дональд Кнут отметил, что этот проект оставался его главным делом на протяжении последних пяти лет, и в его реализации ему помогало огромное количество людей. По плану автора, эта книга составит первую треть будущего тома 4C. Профессор с иронией добавил, что если «Сила пребудет с ним» достаточно долго, то со временем он выпустит и выпуск 12. Все сопутствующие материалы, ссылки и компьютерные программы лектор пообещал традиционно разместить на своём персональном сайте.
💘 Алгоритм, в который можно влюбиться: почему Тарьян покорил Кнута 3:10
Особое место в лекции занял разбор подзаголовка выступления: «Какой алгоритм вы любите больше всего?». Дональд Кнут признался, что обычно ненавидит вопросы о «самых любимых» вещах, однако в данном случае ответ для него очевиден — это алгоритм Роберта Тарьяна для поиска сильных компонент графа.
Впервые познакомившись с этой элегантной процедурой в 1973 году, Кнут, по его собственному признанию, впервые осознал, что глубокими и нетривиальными могут быть не только математические теоремы или сами алгоритмы, но и структуры данных, на которых они базируются. Красота алгоритма Тарьяна заключается в том, насколько идеально в нём сочетаются элементы: каждый раз, когда компьютеру необходимо принять решение или вычислить следующий шаг, нужная информация уже находится «на кончиках его пальцев». Машина не выполняет ни одного действия дважды, фактически решая две задачи одновременно.
🕸️ Сильные и слабые компоненты: математическая суть 5:25
Для объяснения предмета Дональд Кнут напомнил базовое определение ориентированного графа как множества точек (вершин), соединённых стрелками (дугами). Две вершины принадлежат к одной сильно связанной компоненте (strong component), если из первой можно добраться во вторую, а из второй — вернуться в первую. Если в графе есть цикл, то все его вершины гарантированно входят в одну сильную компоненту. При этом компонента может состоять и из одной-единственной вершины, если к ней ведут стрелки, но из неё самой выхода нет.
Ситуация со слабыми компонентами (weak components) в научной литературе, по мнению Кнута, сложилась неудачно. В ряде работ под «слабой компонентой» понимали обычную связность без учёта направления стрелок, что лектор считает методологической ошибкой, предлагая называть это «неориентированной компонентой». Настоящая слабая компонента — гораздо более глубокое понятие.
Математический смысл этих терминов Дональд Кнут объяснил через операции сжатия (shrinkage):
- Если сжать каждую сильную компоненту графа в одну супервершину, мы получим направленный ациклический граф (DAG), описывающий частичный порядок (partial order).
- Если же аналогичным образом сжать слабые компоненты, граф превратится в строго прямую линию, то есть в тотальный (линейный) порядок (total order).
Лектор похвалил статью о слабых компонентах в Википедии, написанную профессором Дэвидом Эпштейном, отметив её высокое качество, но добавил, что ей явно не хватает иллюстраций.
🕯️ Трагическая история профессора Моцкина 10:29
История открытия слабых компонент оказалась тесно переплетена с трагическими событиями. Само понятие было сформулировано профессором Теодором Моцкиным (Theodore Motzkin) в ходе его оживлённой научной переписки с Роном Грэмом и Дональдом Кнутом в начале 1970 года. Профессор продемонстрировал архивное письмо от Моцкина к Грэму, датированное 28 февраля 1970 года, где закладывались основы выстраивания тотального порядка.
В декабре 1970 года Кнут обнаружил, что каждый из троих исследователей (он сам, Грэм и Моцкин) подошёл к задаче со своей стороны, и каждый доказал теорему, превосходящую по общему характеру выводы коллег. Осознав, что его собственное доказательство опиралось на результаты Моцкина, Кнут принял решение сделать его полноценным соавтором будущей статьи. Однако на следующее утро пришло известие, что во вторник профессор Моцкин скоропостижно скончался от сердечного приступа. Статья была опубликована посмертно в 1972 году в самом первом выпуске второго тома журнала Discrete Mathematics.
Дональд Кнут подчеркнул, что в те годы никто даже в самых смелых мечтах не мог представить, насколько богатым и авторитетным станет этот журнал, насчитывающий сегодня тысячи страниц научных публикаций. Примечательно, что и знаменитый алгоритм Роберта Тарьяна увидел свет в том же 1972 году — во втором выпуске первого тома престижного журнала SIAM Journal on Computing.
🧗 Спелеология в компьютерной памяти: как работает поиск в глубину 27:48
Для демонстрации работы алгоритма Дональд Кнут предложил наглядную аналогию с игрой-приключением: исследователь находится в тёмной пещере со множеством комнат, соединённых односторонними переходами, и его задача — изучить структуру этого лабиринта. Базовым инструментом для этого выступает поиск в глубину (Depth-First Search, DFS). Чтобы не заблудиться, спелеолог (или компьютерная программа) должен оставлять в посещённых комнатах опознавательные знаки («мусор»).
Профессор продемонстрировал граф, вершины для которого он сгенерировал случайным образом с помощью самодельного устройства — ручки со стеклянными марблами внутри. На примере этого графа Кнут выделил пять типов дуг, возникающих в процессе поиска в глубину:
- Древесные дуги (tree arcs) — основные ребра, формирующие остовное дерево поиска.
- Обратные дуги (back arcs) — стрелки, ведущие назад к своим прямым предкам.
- Петли (loops) — дуги, ведущие из вершины в саму себя, не влияющие на связность компонент.
- Прямые дуги (forward arcs) — стрелки, идущие вперед к далеким потомкам по дереву.
- Перекрестные дуги (cross arcs) — ребра, ведущие к вершинам, которые не являются ни предками, ни потомками текущей точки.
Главная особенность алгоритма Тарьяна заключается в том, что в процессе обхода он последовательно находит так называемые «вершины-стоки» (sinks) — компоненты, из которых нет выхода во внешнюю неисследованную часть графа. Как только такая сильная компонента обнаружена, алгоритм объявляет её «стабильной» (settled), мысленно удаляет из графа и переходит к поиску следующего стока. Это позволяет не только найти все компоненты, но и одновременно выполнить их топологическую сортировку. С точки зрения быстродействия алгоритм феноменален: в худшем случае для графа с $M$ дугами и $N$ вершинами требуется всего $5M + 17N$ обращений к памяти.
Предыстория этого открытия также любопытна. Джон Хопкрофт (John Hopcroft) приехал в Стэнфорд на академический отпуск (сабатикал) и делил один рабочий кабинет с аспирантом Бобом Тарьяном. Хопкрофт разработал алгоритм для поиска двусвязных компонент в неориентированных графах и показал его Тарьяну. Тот развил эту идею и адаптировал её для ориентированных структур, что привело к созданию шедевра мирового программирования.
🏎️ Постпреждевременная оптимизация и спор с Дейкстрой 1:04:16
Дональд Кнут рассказал, что над этой же задачей параллельно размышлял другой великий учёный — Эдсгер Дейкстра (Edsger Dijkstra). В марте 1973 года Дейкстра прислал Кнуту черновик своей работы, которая впоследствии стала кульминационной 25-й главой его знаменитой книги. Дейкстра независимо пришёл к идее последовательного удаления компонент-стоков, однако его техническая реализация оказалась значительно сложнее. Для отслеживания структуры графа Дейкстре потребовалось ввести четыре дополнительных массива данных. Тарьян же нашёл гораздо более изящное и лаконичное решение с использованием одного стека.
Два года назад (в 2022 году) Кнут и Тарьян снова вернулись к анализу алгоритма 1972 года и смогли его улучшить. Им удалось снизить количество обращений к памяти с $7M$ до $5M$, изменив классическое определение указателя «низшей точки» (low point). Они объединили два служебных поля в одно, из-за чего сам код стал выглядеть несколько сложнее для человеческого восприятия, но стал работать быстрее.
Отвечая на возможную критику, Кнут вспомнил свой знаменитый афоризм: «Преждевременная оптимизация — корень всех зол в программировании». Однако в данном случае, как шутливо заявил профессор, имела место «постпреждевременная оптимизация» (postmature optimization). Профессор убеждён, что когда мы имеем дело с уже зрелым, проверенным временем алгоритмом, вполне оправданно применить хитрость ради ускорения.
«Когда компьютер доходит до участка кода, который ему трудно понять, он не начинает работать медленнее», — отрезал Кнут, подчеркнув, что любые сложные трюки в коде допустимы, если они качественно задокументированы.
🎹 Бескомпромиссный Дейкстра и четыре руки на пианино 1:19:11
В финальной части лекции Дональд Кнут поделился личными воспоминаниями об Эдсгере Дейкстре, с которым был знаком много лет. По мнению Кнута, главной сильной стороной Дейкстры и одновременно его главным недостатком была абсолютная неспособность идти на компромиссы. Коллеги часто отчаянно нуждались в его авторитетных советах, но в то же время панически боялись видеть его в качестве постоянного сотрудника на кафедре из-за его тотального, ультимативного перфекционизма.
Тем не менее, за пределами науки их связывали тёплые отношения. Кнут вспомнил, как гостил дома у Дейкстры в Нидерландах, а затем навещал его во время работы в Остине (Техас). Учёные любили вместе играть на пианино в четыре руки, и Кнут, улыбаясь, признался, что в этих музыкальных дуэтах всегда безропотно уступал Дейкстре ведущую роль. Впрочем, лектор критически отозвался о решении Дейкстры в последние годы жизни полностью отказаться от использования компьютеров и писать программы исключительно на бумаге, назвав такой подход ошибочным.
Свои текущие программные реализации алгоритмов поиска сильных и слабых компонент (написанные в системе визуального программирования CWEB) Кнут выложил в открытый доступ на своём сайте. В качестве примера практического применения этих инструментов он привёл анализ гигантского графа синонимов и антонимов из оригинального тезауруса Роже (Roget's Thesaurus) 1820 года, содержащего более тысячи вершин, исследование которого Кнут назвал невероятно увлекательным процессом.
