Дональд Кнут: как я занялся анализом алгоритмов и ради этого поехал в СССР (37,91,97/97)

«Андрей (Ершов), представь, как было бы здорово организовать что-то вроде паломничества, где программисты со всего мира могли бы приехать в Хорезм и отпраздновать рождение этого понятия.»
— Дональд Кнут уговаривает Ершова организовать международный симпозиум

Кнут и Ершов

Осенью 1967 в Санта-Барбаре была конференция математиков, возможно, это был тот же год, когда я также побывал на конференции в Чапел-Хилле. Я встречал многих людей, которые стимулировали меня, и было множество интересных проблем, которые нам стоило обсудить друг с другом. Но когда я добрался до конференции в Санта-Барбаре, я понял, что это мой единственный шанс заняться исследованиями. Я не посещал лекции. Я просто сидел на берегу и писал свою статью об атрибутной грамматике прямо во время конференции. Но я посещал обеды. Я помню, как кто-то спросил меня, чем я занимаюсь и я решил побыть программистом, а не математиком в тот момент.

— Я думаю, я собираюсь стать программистом.
— О, так ты занимаешься численным анализом?
— Не совсем.
— Аааа, искусственный интеллект.
— Нет, и не искусственный интеллект.
— Тогда должно быть ты занимаешься языками программирования?

Новая область — анализ алгоритмов

Другими словами меня в итоге попросили написать книгу о компиляторе. На самом деле в то время считалось, что программирование состоит из трех частей: численный анализ, искусственный интеллект и языки программирования. Стэндфордский факультет также был своего рода разделен на три основных блока. У них были три квалифицированных экзамена и тому подобное. Но я сказал «Знаете, я проводил много исследований в области языков программирования, был редактором журнала по языкам программирования, но мой главный интерес немного другой». И тогда я понял, что нет названия тому, что интересует меня больше всего. И как это назвать?

К тому времени я написал уже 3000 страниц «Искусства программирования», напечатал часть из них и был почти готов опубликовать их. И оказалось, что нам нужна была математическая основа для понимания качества компьютерных методов. Вы хотели знать, насколько хорош метод, может ли он быть в два раза лучше, чем другой и т.д. Нужно было сказать не просто «да, лучше», но объяснить насколько лучше и почему. Поэтому я решил сделать это основной темой, объединяющей мои книги, найти способы оценки компьютерных достоинств. Но у меня не было для него названия.

На конференции в Санта-Барбаре я понял, что если я собираюсь объяснять кому-то в какой сфере я работаю, у меня должно быть для нее название. Поэтому я решил назвать её анализом алгоритмов. Я пишу книгу и я могу объяснить людям, что это значит. Я поговорил со своим издателем и сказал «Давай изменим название книги, давай назовем ее “Анализ алгоритмов”».

Эту идею не одобрили, но я в любом случае решил, что это будет моей карьерой, что я сосредоточусь в основном на анализе алгоритмов. Это значит, что я буду определять насколько хорош тот или иной алгоритм или компьютерный метод.

Однажды меня попросили провести лекцию на международном конгрессе обработки информации в 1971. Я озаглавил лекцию как «Анализ алгоритмов». Меня также попросили произнести речь на международной математической конференции во Франции в 1970 и я озаглавил ее как «Математический анализ алгоритмов». Я пытался продвигать этот термин, чтобы люди поняли, чем я занимаюсь. И я рад сообщить, что спустя 10 лет или около того, в поздних 70-ых, стали появляться колонки в журналах и начали выходить книги под названием «Анализ алгоритмов».

На самом деле, несмотря на то, что моим издателям не нравилось это название, довольно немногие книги имеют подобный заголовок. Но мне нужно было как-то назвать область, в которой я работаю. Если бы кто-то попросил меня объяснить, что это на самом деле значит, я бы сказал, что это просто то, чем я интересуюсь.

Международный симпозиум по алгоритмам в СССР

Я сказал, что я хотел, чтобы анализ алгоритмов был работой моей жизни. Большая часть моей работы, включая написание «Искусства программирования», заключалась в том, чтобы найти способ определить насколько хорош алгоритм. Изучение алгоритмов нравилось мне больше всего, и всегда было для меня на первом месте.

Я был рад узнать, что слово «алгоритм» произошло от арабского Аль-Хорезми. Сейчас Хорезм — это регион в Узбекистане, но тогда это было озеро. Я имею в виду Аральское море, которое раньше называлось озером Хорезми. Это часть мира, которую совершенно забыли.

Если смотреть на карту Ирана, то это место находится севернее, если смотреть на карту Румынии, то восточнее, если смотреть на карту Индии или Афганистана, то западнее, юг России, понимаете? Про эту часть мира просто забыли. Но я выяснил что оттуда произошло слово «алгоритм», Хорезм. Знаете, есть места, где живут армяне и они называют это армянской диаспорой? В Багдаде есть целый Хорезмский квартал. И я подумал, ладно, было бы интересно посетить Хорезм однажды. Я посмотрел в атлас и ужаснулся. Это же в самом сердце СССР, как я вообще туда доберусь?!? Нет дорог, которые вели бы прямо к этому месту.

Я сказал об этом своему другу Андрею Ершову, который приехал из России, из Советской Академии наук. Ну, он не был моим другом в то время, я не очень хорошо его знал, но он был другом Джона Маккарти и мы были на вечеринке в его доме. Я сказал Андрею: «Ты знаешь, что слово «алгоритм» произошло от места, которое находится в Советском союзе? Мы должны это как-нибудь отметить. Представь, как было бы здорово организовать что-то вроде паломничества, где программисты со всего мира могли бы приехать в Хорезм и отпраздновать рождение этого понятия».

И он сказал: «Звучит, как отличная идея!». Он вернулся домой и начал работу по организации всего этого. Он попросил Советскую Академию наук спонсировать международный симпозиум по алгоритмам, который бы длился две недели и проходил бы в районе Хорезма.

Еще прежде чем я добрался до Хорезма, когда я только вышел с самолета, меня встречали 200 детей, которые несли цветы, и затем у меня взяли интервью для местного телевидения. Это был первый случай, когда кто-либо проявил такой интерес к их землям. Гостеприимство людей на Среднем Востоке удивительно. На самом деле, знаете, хозяева были настолько щедрые, что я в шутку попросил их предоставить мне содержанку. И я уверен, что они бы так и сделали, если бы я не заверил их, что просто шучу. Мы могли бы посетить своеобразный город-музей Хиву, откуда создатель алгоритма Аль-Хорезми вероятно был родом.

Я не уверен, но в любом случае это своего рода сохранившийся город, который показывает великое достояние этой культуры. Половина людей на этой конференции были из СССР и другая половина с разных частей света. Мы могли просто обсуждать значимость алгоритмов. Возможность устроить эту небольшую встречу и увидеть этот уголок мира была одним из величайших достижений в моей жизни.

Д. Кнут танцует

Удивительно, но мы встретили в этом поселке детей разных национальностей: блондинов, голубоглазых, некоторых с корейской родословной. Мы побывали на хлопковых фермах и собирали хлопок. Я получил шапку, в которых ходят люди в Хорезме. Так что теперь, когда я работаю над алгоритмами, я могу быть подобающе одет.

Почему я выбрал анализ алгоритмов как область исследований

За каждой написанной работой, а я написал их немало, стоит какая-нибудь интересная история. Алгоритм сам по себе стал известным, но я сам не использовал его последние 20 лет. Однако он во всех учебниках и является поучительным примером.

Например он хорош в использовании, когда ты пытаешься просмотреть длинный отрывок из текста, чтобы найти определенное слово. Предположим, я ищу слово t-h-e(*артикль в английском языке) или что-то вроде того. Хотя, было бы глупо искать это слово, давайте искать d-i-k-r-a-n(*растение дикран).

Очевидно, ты останавливаешься на каждом месте в тексте и спрашиваешь себя «Это буква D? Отлично. Следом идет буква I? Хорошо. Дальше K? Нет, это слово 'direction'(*расстояние с англ.). Тогда ты перемещаешься дальше и повторяешь этот алгоритм сначала. Это D? Нет, мы уже выяснили, что это I. Значит нужно переместиться еще дальше. Но все не так просто. Есть более сложные слова. Если бы мы искали слово 'didymus'(*близнец с англ.), где две буквы D, то наш алгоритм уже бы не работал.

У профессора в Беркли, Стива Кука, есть удивительная теорема на этот счет. Он утверждает, что если бы мы взяли некий очень ограниченный по своим возможностям компьютер и если мы могли бы написать программу, которая решала бы проблему, для этого тупого компьютера вне зависимости от того насколько медленно работала бы эта программа, значит существует быстрый способ написать эту же программу для нормального компьютера.

Другими словами мы берем определенный компьютер с ограниченными возможностями и если на нем можно решить проблему, то существует быстрый способ сделать это на нормальном компьютере. Единственная проблема, которую стоило бы решить с этим компьютером, это возможность определить является ли набор букв палиндромом и провернуть то же самое в цепочке палиндромов.

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

Я был довольно хорошим программистом, но вот эта теорема утверждала, что есть способ сделать это, а я не мог придумать как. Я впервые был в такой своего рода тупиковой ситуации и не мог перестать думать об этом. Я потратил день и вечер, чтобы подробно расписать на доске теорию Кука и найти, наконец, быстрый способ воплотить это в жизнь на компьютере.

Внезапно я нашел зацепку. Изначально идея заключалась в том, чтобы написать программу, которая отражала бы эту общую теорему, но она также могла решить проблему поиска в тексте. Я упомянул об этом в поездке в Беркли и встретил там Вогана Пратта. Он был тем, кто внес самый больший вклад, я просто был тем, кто записал это впоследствии.

Потом мы узнали, что та же самая идея посетила Джима Морриса парой месяцев раннее, но люди посмотрели на его программу, не поняли её и поэтому не взяли. В любом случае я считаю, что это эффективный способ поиска в тексте, который также дает хорошее представление об основах информатики. Этот способ стал известным и ассоциируется с моим именем.

Как я уже говорил, я написал 160 работ и за каждой из них стоит какая-нибудь интересная история.

Перевод: Диана Шеремьёва