timelets

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

Оказывается, в конце 50-х годов 25-летний Хоар сначала выучил русский язык, а потом по культурному обмену провел год в аспирантуре МГУ, изучая теорию вероятностей "на факультете А.Н.Колмогорова". Там он заинтересовался проблематикой машинного перевода, и первой публикацией Хоара была статья, которую он написал по-русски и опубликовал в сборнике "Машинный перевод и прикладная лингвистика" (1961, вып. 6).

Подход к машинному переводу в те далекие ранние времена заключался в том, чтобы подставлять из словаря переводы отдельных слов или словосочетаний, используя информацию о том, как части речи сочетаются по-разному в разных языках, чтобы соединять эти куски вместе. Но как минимум для этого программе нужно узнать где-то (посмотреть в словаре) переводы всех слов данного предложения. Крохотная память компьютеров тогда не вмещала целый словарь, даже небольшой. Нужно было каждый раз считывать его с магнитной ленты, для этого надо каждый раз всю ее прочитать. Если в предложении 20 слов, то удобно расположить их в алфавитном порядке, и по мере чтения ленты находить следующее и следующее слово.

Эта необходимость привела Хоара к задаче быстрой сортировки слов в алфавитном порядке (а затем любых данных), и для этого он изобрел Quicksort, а опубликовал статью о нем после возвращения в Англию, в 1962-м. Все это выглядит немного как первоапрельская фантазия, но тем не менее правда.

Дональд Кнут, знаменитый американский ученый-алгоритмист, написал несколько дней назад заметку о том, как LLM помогла ему, точнее его соавтору, решить алгоритмическую задачу, над которой Кнут работал несколько недель. Заметка начинается словами "Shock! Shock!"

Задача, которую решил Клод, не какая-то знаменитая, и у нее нет, насколько мне известно, важных применений. Мне кажется, интересно даже не столько то, что ИИ ее решил, сколько *как* решил. Это подробнее описано в статье Кнута, но если вкратце - перед Клодом поставили задачу и он работал над ней примерно в 30 подходов-итераций. После каждой итерации он записывал в файл для самого себя краткое описание того, что он только что попробовал и что из этого вышло, и это помогало ему искать новые подходы и не зацикливаться. В процессе решения он испробовал много разных идей, как математических, так и программистских, и в конце концов нашел одну работающую, проверив ее на куче вариантов (хоть и не доказал ее строго, доказательство написал позже сам Кнут). Весь процесс занял около часа, и был почти автоматическим - человеку пришлось несколько раз останавливать или подправлять итерации, в которой Клод путался в своих следах и терял контекст.

Мне кажется, что работа ИИ в этом случае вполне сравнима с тем, как мог над такой задачей работать талантливый студент-аспирант, которому дал ее научный руководитель. Конечное решение не супер сложное и до него вполне можно дойти с помощью упорства и дисциплины (важно проверять свои идеи путем написания тест-программ, не заходя слишком далеко в теорию). Те же 30 итераций аспирант мог сделать за неделю-две; только ИИ сделал за час и без аспиранта.

Это возможно здесь и сейчас, в 2026 году. Обратите внимание, вглядитесь хорошенько. Будущее продолжает наступать на настоящее ударными темпами. Полгода или год назад модели еще не могли настолько самостоятельно работать над математическими задачами на таком уровне.

Теперь попытаюсь вкратце объяснить и показать суть проблемы, которую решил Клод для Кнута.



Рассмотрим все возможные комбинации из трех цифр от 1 до 3, начиная от 111 и кончая 333. Всего таких 3*3*3=27. Сделаем из них 27 вершин графа и проведем стрелки от каждой вершины к трем следующим после нее по каждой из 3 координат. Например, из 112 можно "пойти" в 212 (увеличили первую координату), 122 (вторую), 113 (третью). После 3 всегда возвращаемся к 1, так что из 113, например, можно пойти в 213, 123 или 111.

Мы получили граф из 27 вершин и 27*3=81 ребер между ними. Он показан на картинке выше (не обращайте внимания на цвета ребер пока что). Горизонтальные ребра, соединяющие по первой координате, надо представлять как уходящие вправо и возвращающиеся слева: например, в первой строке 111 -> 211 -> 311 -> 111. Эти возвращения не нарисованы, чтобы визуально разгрузить картинку. В этом графе есть много циклов, например только что написанный. Вопрос в том, какие есть в нем гамильтоновы циклы, т.е. проходящие через каждую вершину 1 раз. Длина такого цикла 27, по числу вершин. Найти гамильтонов цикл легко, но сложнее - хотя тоже возможно - найти три таких цикла, которые все используют разные ребра, и таким образом в них входят все 27*3=81 ребер графа.

Такое разбиение показано на картинке: три цикла выкрашены в три разных цвета. Я также нарисовал отдельно три графа, в каждом из которых один из циклов выделен, так что можно проследить глазами, как он путешествует сквозь все 27 вершин. Они показаны внизу записи.

Таких разбиений, разных, есть много: сотни. Это не задача, которую решил ИИ. Это Кнут сделал сам; то, надо чем он работал, это как такое решение обобщить на любое количество цифр, не только от 1 до 3. Для любого числа m > 2 мы можем построить граф из m^3 вершин, в каждой записана тройка чисел от 1 до m; ребра как описано выше, их 3*m^3; и вопрос в том, как разбить этот граф на 3 гамильтоновых цикла.

Для m=3 легко найти решение и даже много решений перебором (не совсем наивным, но близко к тому). Для больших m это не работает; надо придумать подход, формулу (в первый цикл входят (i,j,k) с такими-то свойствами; во второй с такими-то итд.). Логично, чтобы суть формулы была одна для разных m; но есть разные довольно красивые и симметричные разбиения для m=3, которые не работают при попытке обобщить для больших m.

После многих попыток в разные стороны, которые не удавались, Клод смог найти формулу, которая эмпирически работала для всех нечетных m от 3 до 101, и Кнут позже доказал, что она работает для всех нечетных m. Еще пару дней спустя другие энтузиасты нашли также решение для всех четных m > 3, тоже с помощью LLM. Задача теперь полностью решена.