В Стэнфордском университете прошла лекция легендарного учёного, автора многотомника «Искусство программирования» Дональда Кнута (Donald Knuth). Встреча была посвящена элегантным алгоритмам работы с графами, а также выходу новой части его фундаментального труда — раздела 12a выпуска 7 тома 4C, посвящённого задаче выполнения ограничений (Constraint Satisfaction). Кнут поделился личной историей любви к алгоритму Тарьяна, рассказал о трагических обстоятельствах открытия слабых компонент и объяснил, почему глубокие структуры данных важнее «чистой» математики.
❤️ Алгоритм Тарьяна: любовь с первого взгляда 0:11
В ходе лекции Дональд Кнут признался в любви к алгоритму Роберта Тарьяна (Robert Tarjan) для поиска компонент сильной связности . По словам профессора, когда он впервые изучил эту процедуру в 1973 году, он осознал, что глубокими могут быть не только математические теоремы, но и сами структуры данных.
Особенности «любимого алгоритма» Кнута:
- Элегантность: Алгоритм работает за линейное время, совершая минимум обращений к памяти — в худшем случае всего $5m + 17n$ обращений ($m$ — число ребер, $n$ — число вершин) .
- Эффективность: Система организована так, что вся необходимая информация для принятия решения всегда находится «под рукой» у процессора, исключая повторные вычисления .
- Глубина: Кнут подчеркивает, что алгоритм не просто находит компоненты, но и одновременно выполняет топологическую сортировку графа .
Интересно, что в 1972 году рецензенты математических журналов не оценили гениальность Тарьяна. Кнут продемонстрировал архивный отзыв, где говорилось, что алгоритм «не вызывает удивления» . Однако время доказало обратное: сегодня этот метод считается эталоном в Computer Science.
🕸 Сильные и слабые компоненты: теория 5:38
Кнут подробно разъяснил различие между типами связности в ориентированных графах.
Компоненты сильной связности
Вершины $u$ и $v$ находятся в одной компоненте сильной связности, если существует путь из $u$ в $v$ и обратно из $v$ в $u$ . Если сжать каждую такую компоненту в одну супер-вершину, исходный граф превратится в направленный ациклический граф (DAG) .
Слабые компоненты (Weak Components)
Понятие слабых компонент часто путают с компонентами связности неориентированного графа, что Кнут считает «неудачным» . Математически верное определение слабых компонент связано с порядком:
- Если сжать сильные компоненты, мы получим частичный порядок.
- Если сжать слабые компоненты (в понимании Кнута и Моцкина), мы получим линейный (полный) порядок .
- Две вершины попадают в одну слабую компоненту, если они несравнимы в рамках частичного порядка или связаны цепочкой несравнимых элементов .
🕯 Печальная история Теодора Моцкина 10:29
История открытия слабых компонент омрачена трагедией. Кнут рассказал, что в 1970 году он, Рон Грэм (Ron Graham) и Теодор Моцкин (Theodore Motzkin) вели переписку, работая над одной проблемой с разных сторон. Моцкин предложил концепцию слабых компонент в письме от 28 февраля 1970 года .
В декабре 1970 года Кнут решил, что все трое должны стать соавторами статьи, так как их подходы дополняли друг друга. Однако в то же утро он получил известие о внезапной смерти Моцкина от сердечного приступа . Статья была опубликована в журнале Discrete Mathematics уже посмертно . Долгое время информация об этом открытии в широких источниках (включая Википедию) была скудной, пока ситуацию не исправил профессор Дэвид Эпштейн (David Eppstein) .
🔍 Анатомия поиска в глубину (DFS) 28:56
Для объяснения работы алгоритма Кнут использовал метафору игры в спелеолога: вы исследуете пещеру (граф), оставляя за собой метки . В процессе поиска в глубину (Depth First Search) ребра графа делятся на пять типов :
- Tree Arc (Дерево): ребро, ведущее к новой вершине.
- Back Arc (Обратное): ведет к предку в текущем дереве поиска (сигнализирует о цикле).
- Loop (Петля): ребро из вершины в саму себя.
- Forward Arc (Прямое): ведет к потомку, который уже был посещен другим путем.
- Cross Arc (Перекрестное): ведет к вершине, которая не является ни предком, ни потомком (уже «осевшая» компонента) .
Кнут продемонстрировал «Тайный соус Тарьяна» — использование стека для хранения активных вершин и специального указателя (Low Point), который позволяет определить, когда мы нашли «сток» (sink) графа . Как только алгоритм находит компоненту-сток, он «закрывает» её и удаляет из рассмотрения, переходя к следующей.
🛠 Оптимизация: когда «трюкачество» оправдано 1:11:11
В последние два года (2022–2024) Кнут и Тарьян снова вернулись к улучшению алгоритма 50-летней давности . Они разработали версию, которая работает еще быстрее, чем оригинал.
Кнут затронул важный этический вопрос программирования:
- Преждевременная оптимизация: По его мнению, это корень всех зол.
- Постзревшая оптимизация (Postmature optimization): Когда алгоритм уже изучен досконально, можно добавить «хитрости» (trickery), чтобы выжать максимум производительности .
Профессор считает, что если трюк хорошо задокументирован, его не нужно бояться. Компьютер не понимает сложности кода — он просто выполняет инструкции, и если запутанный код работает быстрее, для машины это благо . Кнут также упомянул Эдсгера Дейкстру (Edsger Dijkstra), который пытался решить задачу о компонентах связности независимо. Дейкстра разработал решение с четырьмя дополнительными массивами, но оно оказалось сложнее и медленнее, чем элегантный подход Тарьяна .
🎹 Личные воспоминания о Дейкстре 1:19:11
Отвечая на вопросы из зала, Кнут вспомнил своего коллегу Эдсгера Дейкстру. Он описал его как человека «неспособного на компромисс» и абсолютного перфекциониста .
- Дейкстра был настолько принципиален, что многие боялись его как коллегу, хотя ценили как советчика.
- В последние годы жизни Дейкстра перестал писать программы, считая, что всё нужно делать только бумагой и ручкой, что Кнут назвал «довольно глупым» (dumb) .
- Они проводили время, играя на пианино в четыре руки, и Кнут всегда позволял Дейкстре вести партию .
📦 Где изучить подробнее?
Кнут анонсировал обновление своего сайта, где будут выложены обновленные программы на языке CWEB . Также он порекомендовал свою книгу «Stanford GraphBase», где алгоритм Тарьяна применен к анализу тезауруса Роже (Roget's Thesaurus). В этом примере вершины — это категории слов (например, «Ангел»), а дуги — связи между синонимами .
