# Дональд Кнут: «Алгоритм Тарьяна — это моя самая большая любовь в программировании» Источник: https://www.youtube.com/watch?v=Hi8r_63LGyg Канал: Stanford Online Опубликовано: 07.01.2025 --- В Стэнфордском университете прошла лекция легендарного учёного, автора многотомника «Искусство программирования» Дональда Кнута (Donald Knuth). Встреча была посвящена элегантным алгоритмам работы с графами, а также выходу новой части его фундаментального труда — раздела 12a выпуска 7 тома 4C, посвящённого задаче выполнения ограничений (Constraint Satisfaction). Кнут поделился личной историей любви к алгоритму Тарьяна, рассказал о трагических обстоятельствах открытия слабых компонент и объяснил, почему глубокие структуры данных [4:05] важнее «чистой» математики. ## ❤️ Алгоритм Тарьяна: любовь с первого взгляда [[JUMP:0:11]] В ходе лекции Дональд Кнут признался в любви к алгоритму Роберта Тарьяна (Robert Tarjan) для поиска компонент сильной связности [3:51]. По словам профессора, когда он впервые изучил эту процедуру в 1973 году, он осознал, что глубокими могут быть не только математические теоремы, но и сами структуры данных. Особенности «любимого алгоритма» Кнута: * **Элегантность:** Алгоритм работает за линейное время, совершая минимум обращений к памяти — в худшем случае всего $5m + 17n$ обращений ($m$ — число ребер, $n$ — число вершин) [45:31]. * **Эффективность:** Система организована так, что вся необходимая информация для принятия решения всегда находится «под рукой» у процессора, исключая повторные вычисления [4:31]. * **Глубина:** Кнут подчеркивает, что алгоритм не просто находит компоненты, но и одновременно выполняет топологическую сортировку графа [45:02]. Интересно, что в 1972 году рецензенты математических журналов не оценили гениальность Тарьяна. Кнут продемонстрировал архивный отзыв, где говорилось, что алгоритм «не вызывает удивления» [19:36]. Однако время доказало обратное: сегодня этот метод считается эталоном в Computer Science. ## 🕸 Сильные и слабые компоненты: теория [[JUMP:5:38]] Кнут подробно разъяснил различие между типами связности в ориентированных графах. ### Компоненты сильной связности Вершины $u$ и $v$ находятся в одной компоненте сильной связности, если существует путь из $u$ в $v$ и обратно из $v$ в $u$ [6:07]. Если сжать каждую такую компоненту в одну супер-вершину, исходный граф превратится в направленный ациклический граф (DAG) [8:42]. ### Слабые компоненты (Weak Components) Понятие слабых компонент часто путают с компонентами связности неориентированного графа, что Кнут считает «неудачным» [7:15]. Математически верное определение слабых компонент связано с порядком: 1. Если сжать сильные компоненты, мы получим частичный порядок. 2. Если сжать слабые компоненты (в понимании Кнута и Моцкина), мы получим линейный (полный) порядок [9:21]. 3. Две вершины попадают в одну слабую компоненту, если они несравнимы в рамках частичного порядка или связаны цепочкой несравнимых элементов [16:39]. ## 🕯 Печальная история Теодора Моцкина [[JUMP:10:29]] История открытия слабых компонент омрачена трагедией. Кнут рассказал, что в 1970 году он, Рон Грэм (Ron Graham) и Теодор Моцкин (Theodore Motzkin) вели переписку, работая над одной проблемой с разных сторон. Моцкин предложил концепцию слабых компонент в письме от 28 февраля 1970 года [10:56]. В декабре 1970 года Кнут решил, что все трое должны стать соавторами статьи, так как их подходы дополняли друг друга. Однако в то же утро он получил известие о внезапной смерти Моцкина от сердечного приступа [12:05]. Статья была опубликована в журнале *Discrete Mathematics* уже посмертно [12:18]. Долгое время информация об этом открытии в широких источниках (включая Википедию) была скудной, пока ситуацию не исправил профессор Дэвид Эпштейн (David Eppstein) [9:48]. ## 🔍 Анатомия поиска в глубину (DFS) [[JUMP:28:56]] Для объяснения работы алгоритма Кнут использовал метафору игры в спелеолога: вы исследуете пещеру (граф), оставляя за собой метки [28:56]. В процессе поиска в глубину (Depth First Search) ребра графа делятся на пять типов [30:18]: * **Tree Arc (Дерево):** ребро, ведущее к новой вершине. * **Back Arc (Обратное):** ведет к предку в текущем дереве поиска (сигнализирует о цикле). * **Loop (Петля):** ребро из вершины в саму себя. * **Forward Arc (Прямое):** ведет к потомку, который уже был посещен другим путем. * **Cross Arc (Перекрестное):** ведет к вершине, которая не является ни предком, ни потомком (уже «осевшая» компонента) [38:15]. Кнут продемонстрировал «Тайный соус Тарьяна» — использование стека для хранения активных вершин и специального указателя (Low Point), который позволяет определить, когда мы нашли «сток» (sink) графа [33:37]. Как только алгоритм находит компоненту-сток, он «закрывает» её и удаляет из рассмотрения, переходя к следующей. ## 🛠 Оптимизация: когда «трюкачество» оправдано [[JUMP:1:11:11]] В последние два года (2022–2024) Кнут и Тарьян снова вернулись к улучшению алгоритма 50-летней давности [1:11:11]. Они разработали версию, которая работает еще быстрее, чем оригинал. Кнут затронул важный этический вопрос программирования: 1. **Преждевременная оптимизация:** По его мнению, это корень всех зол. 2. **Постзревшая оптимизация (Postmature optimization):** Когда алгоритм уже изучен досконально, можно добавить «хитрости» (trickery), чтобы выжать максимум производительности [1:14:46]. Профессор считает, что если трюк хорошо задокументирован, его не нужно бояться. Компьютер не понимает сложности кода — он просто выполняет инструкции, и если запутанный код работает быстрее, для машины это благо [1:15:17]. Кнут также упомянул Эдсгера Дейкстру (Edsger Dijkstra), который пытался решить задачу о компонентах связности независимо. Дейкстра разработал решение с четырьмя дополнительными массивами, но оно оказалось сложнее и медленнее, чем элегантный подход Тарьяна [1:10:44]. ## 🎹 Личные воспоминания о Дейкстре [[JUMP:1:19:11]] Отвечая на вопросы из зала, Кнут вспомнил своего коллегу Эдсгера Дейкстру. Он описал его как человека «неспособного на компромисс» и абсолютного перфекциониста [1:19:24]. * Дейкстра был настолько принципиален, что многие боялись его как коллегу, хотя ценили как советчика. * В последние годы жизни Дейкстра перестал писать программы, считая, что всё нужно делать только бумагой и ручкой, что Кнут назвал «довольно глупым» (dumb) [1:20:31]. * Они проводили время, играя на пианино в четыре руки, и Кнут всегда позволял Дейкстре вести партию [1:20:05]. --- ### 📦 Где изучить подробнее? Кнут анонсировал обновление своего сайта, где будут выложены обновленные программы на языке **CWEB** [1:18:45]. Также он порекомендовал свою книгу «Stanford GraphBase», где алгоритм Тарьяна применен к анализу тезауруса Роже (Roget's Thesaurus). В этом примере вершины — это категории слов (например, «Ангел»), а дуги — связи между синонимами [1:22:11]. ---