Astronet Астронет: Astronet Ответы на все вопросы
http://variable-stars.ru/db/msg/1175502
Ответы на все вопросы Ответы на все вопросы
26.03.2002 15:49 | Astronet

5 октября 2001 года в Техническом университете г. Мюнхен Дональд Кнут прочел лекцию, названную "Ответы на все вопросы". Лекция собрала около 350 слушателей. В данной статье представлен текст этой лекции в редакции Элина Джексона, редактора журнала "Записки Американского Математического Общества" (Notices of the AMS).

По образованию математик, Дональд Кнут получил известность своими исследованиями по информатике, особенно по теории алгоритмов. Он является автором многих книг (список его трудов в MathSciNet содержит 160 названий), среди которых трехтомное "Искусство программирования"[1], за которое в 1986 г. он получил награду Американского Математического Общества. В соответствующем заявлении говорится, что данная книга "внесла больший вклад в преподавание математики нынешнему поколению студентов, чем любая математическая книга, вышедшая в последние десятилетия". Долгожданный четвертый том находится в стадии подготовки и некоторые его части доступны на веб-странице Кнута http://www-cs-faculty.stanford.edu/~knuth.

Кнут - создатель языков для подготовки текстов TeX и METAFONT, которые произвели переворот в написании и распространении технической литературы во многих отраслях, включая и математику. В 1974 г. он прочел в Американском Математическом Обществе Гиббсовскую лекцию, которую назвал "Подготовка математических текстов". Впоследствии она была опубликована в Бюллетене Американского Математического Общества.[2]

Кнут получил диплом по математике в 1963 г. в Калтехе под руководством Маршалла Холла. В 1974 г. он был награжден Премией Тьюринга Ассоциации Компьютерной Техники. Среди его наград - Национальная Научная Медаль США (National Medal of Science, 1979), медаль Адельсколда Шведской Королевской академии наук(1994), премия Харви Техниона (Израиль, 1995), медаль Джона фон Неймана от IEEE (1995) и премия Киото Фонда Инамори. С 1968 года Кнут работает в Стэнфордском Университете, где он в настоящее время имеет звание заслуженного профессора Искусства Программирования.

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

Итак, кто хочет задать первый вопрос? Если вопросов нет... (Кнут делает вид, что собирается уходить.)

Вопрос: Был специальный доклад американскому президенту, доклад PITAC[3], содержащий некоторые рекомендации. Меня интересует, не хотели бы вы прокомментировать приоритеты, сформулированные в этих рекомендациях: более хорошая разработка программ, создание терафлопного компьютера, совершенствование Интернета, включая повышение безопасности и пропускной способности, и социально-экономические аспекты регулирования информации, находящейся в компьютерных сетях.

Кнут: Мне кажется, что это очень хороший набор проблем для доклада президенту... Но на самом деле что я хотел бы увидеть, так это дать возможность тысячам специалистов по информатике делать то, что они хотят. Это то, что реально продвинуло бы отрасль вперед. По своему опыту написания "Искусства программирования"[1] знаю : если бы вы меня каждый год спрашивали, что из произошедшего в информатике за этот год наиболее важно, я, возможно, не смог бы сказать ничего, но за пять лет отрасль меняется полностью. Информатика - это потрясающее сотрудничество людей со всего мира, добавляющих маленькие кирпичики в огромную стену. Именно эти отдельные кирпичики, а не эпохальные события, и составляют суть нашей работы.

Следующий вопрос?

Вопрос: Математики говорят, что у Бога есть "Книга Доказательств", куда записываются наиболее красивые доказательства. Можете ли вы назвать какие-нибудь алгоритмы, достойные "Книги Алгоритмов"?

Кнут: Хороший вопрос. Идею о том, что у Бога есть книга, в которой записаны лучшие математические доказательства, высказал Поль Эрдос, и, кажется, мой друг Гюнтер Циглер из Берлина недавно писал об этом[4].

Я помню, математики говорили мне в 60-е годы, что они признают информатику взрослой наукой, когда в ней будет 1000 фундаментальных алгоритмов. Я думаю, мы уже достигли порядка 500. Несомненно, есть множество алгоритмов, которые, я думаю, можно считать совершенно прекрасными и в некотором роде бессмертными. Два примера - алгоритм Эвклида и соответствующий, работающий в бинарной записи, возможно, разработанный в Китае примерно тогда же, когда эвклидов - в Греции. В своих книгах я в основном имею дело с классическими и уже давно существующими алгоритмами, но тем не менее каждый год появляются новые идеи, которые, я думаю, останутся навсегда.

Вопрос: Есть ли у вас какие-нибудь соображения по поводу квантовых вычислений?

Кнут: Да, но я знаю про них не очень много. Это парадигма, полностью отличная от привычной мне. Она имеет с ней много общего, но она очень непривычна в том плане, что вы получаете все ответы в конце, а не определяете на каждом шаге, что делать дальше. Многое из этого показано в фильме "Run Lola Run", в котором сюжет повторяется три раза с тремя различными финалами. Квантовые вычисления - нечто похожее: мир идет многими путями одновременно, и мы выбираем тот, где результат лучше.

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

Вопрос из задних рядов ?

Вопрос: Я работаю в области теории доказательств, и одна из наиболее важных работ там - ваша статья 1970 года "Задачи с простыми высказываниями в общих алгебрах" [5] , написанная вместе с П. Бендиксом. У меня два вопроса. Во-первых, продолжаете ли вы следить за этой областью, и что вы думаете о ее состоянии? И второй, кто такой Бендикс и как сложилась его дальнейшая судьба?

Кнут: Эта работа была опубликована в 1970, но на самом деле я сделал ее в 1967, когда был в Калтехе. Это была простая идея, но, к счастью, она оказалась широко применимой. Идея состоит в том, чтобы взять набор математических аксиом и получить все их следствия. Если у меня есть набор аксиом, а у вас - возможная теорема, вы спрашиваете, следует ли она из этих аксиом. Я назвал статью "Задачи с простыми высказываниями в общей алгебре", и сказал, что задача является "простой", если мой метод с ней справляется. Теперь этот метод значительно расширен другими людьми, и гораздо большее количество задач "просты". Я думаю, их работа замечательна.

1967 был для меня самым драматическим годом. У меня не было времени для исследований. У меня было двое детей младше 2-х лет, я был назначен лектором в Ассоциации Компьютерной Техники на три недели, я должен был читать лекции на летней школе НАТО в Копенгагене, я должен был выступать на конференции в Оксфорде, и так далее. И я занимался корректурой "Искусства программирования", первый том которого вышел в 1968. Все это вдобавок к тем обычным курсам, которые я читал тогда, и к обострению язвы, из-за которого я ложился в больницу, и редакторству в дюжине журналов. В том году я работал над двумя маленькими идеями. Одна стала известна как алгоритм Кнута-Бендикса, другая известна как атрибутивные грамматики[7]. Это был самый продуктивный год моей жизни, но и, кроме того, самый беспокойный.

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

В 60-е, если бы я писал статью со своим руководителем Маршаллом Холлом, это значило бы, что он придумывает теорию, а я занимаюсь программированием. Но если я писал совместно с кем-то еще - я делал теорию, а этот кто-то занимался программами. Пит Бендикс был хорошим программистом, который реализовал метод.

Вопрос: Мне кажется, что проще переработать книгу, чем вносить изменения в огромные программные продукты, которые мы видим каждый день. Как можно применить теорию к усовершенствованию программного обеспечения?

Кнут: Несомненно, ошибки в программах исправлять гораздо сложнее, чем в книге. На самом деле, мой главный вывод из десятилетней работы над TEX-ом состоит в том, что писать программы трудно. Это гораздо труднее, чем все остальное, чем я занимался. Пока я писал TEX, я не мог заниматься полноценным преподаванием. Хотя я люблю преподавание, я был вынужден на год от него отказаться - слишком многое надо было держать в голове одновременно. Писать книгу лишь немногим сложнее, чем писать техническую статью, но писать программы гораздо труднее, чем книгу.

В своих книгах я предлагал вознаграждение первому, кто найдет очередную ошибку в тексте, и я должен признать, что я выписал в Германию чеков больше, чем куда бы то ни было. Я получал письма отовсюду, но немецкие читатели оказались моими лучшими критиками. Я точно так же платил за ошибки в своих программах - TeX-е и METAFONT-е. Вознаграждения удваивались каждый год: я начинал с $2.56, потом $5.12, и так далее, до $327.68, когда я прекратил удваивание. В TEX-е и METAFONT-е не находилось ошибок с 1994 или 1995 года, хотя ходят слухи, что кто-то недавно нашел одну. Я планирую снова заняться этим через год или два. Я делаю все в "пакетном режиме", кстати. Я собираюсь снова заняться возможными ошибками в TeX-е, скажем, в 2003 году.

Я считаю, что давать знать пользователям, что ты приветствуешь сообщения об ошибках - единственная серьезная методика, которая может быть использована в индустрии программного обеспечения. По-моему, Microsoft должен был бы сказать: "Вы будете получать чек от Билла Гейтса за каждую найденную ошибку"

Вопрос: Какое значение вы придаете разработке эффективных алгоритмов и что, по-вашему, ждет ее в будущем?

Кнут: Я считаю, что разработка эффективных алгоритмов является, в некотором роде, ядром информатики. Она находится в центре поля нашей деятельности. Компьютеры сегодня гораздо быстрее, чем раньше, и поэтому для многих задач нет необходимости заботиться об эффективности алгоритмов. Я могу писать в каком-то смысле очень неэффективные программы, но если они выдают ответ через секунду - кого это волнует? Тем не менее, некоторые вещи мы должны повторять миллионы или миллиарды раз, и простого знания конечности числа повторений не хватает для получения ответа. Поэтому число задач, требующих разработки эффективных алгоритмов, по-прежнему велико. Например, многие задачи являются NP-полными1, а этот класс является далеко не самым сложным. Поэтому я вижу практически неограниченные перспективы для разработки эффективных алгоритмов. И это меня радует, так как это является моим любимым делом.

Вопрос: Вы серьезно интересуетесь головоломками, в том числе "Ханойской башней" для числа стержней, большем 3. Я не буду задавать более сложный вопрос - каково кратчайшее решение - так как не уверен, что все знают эту головоломку. Но я хочу задать более философский вопрос - можно ли показать, что эта задача неразрешима?

Кнут: Знает ли аудитория задачу "Ханойской башни"? У вас есть 3 стержня и набор дисков разного размера, и надо переложить все диски с одного стержня на другой, причем диски на стержнях всегда должны быть отсортированы так, чтобы больший лежал внизу. Вы можете перекладывать по одному диску за раз. Генри Дудени предложил обобщение этой задачи да большее количество стержней, и вопрос о кратчайшем решении для случая 4 стержней оставался открытым более 100 лет. Задача с 3 стержнями очень проста, мы обучаем первокурсников решать ее.

Но возьмем другую, более известную задачу - предположение Гольдбаха: каждое четное число можно представить как сумму двух нечетных простых. Я считаю, что эта задача никогда не будет решена. Я даже думаю, что эта задача может не иметь доказательства. Она может быть одной из тех непроверяемых теорем, которые, как показал Гёдель, должны существовать. На самом деле, сейчас мы знаем, что в каком-то смысле почти все правильно построенные высказывания о математике непроверяемы. Предположение Гольдбаха, в каком-то смысле, правильно, потому что не может быть ложным. Существует так много способов представить четное число суммой двух нечетных, что с ростом самого числа число его представлений становится все больше и больше. Возьмите $10^{10^{10}}$ -значное четное число и представьте, сколькими способами его можно разложить на сумму двух нечетных. Для $n$-битного нечетного числа вероятность оказаться простым пропорциональна $1/n$. Каким образом все эти пары нечетных чисел могут быть не простыми? Этого просто не может быть. Но это не значит, что вы нашли доказательство, так как определение простоты мультипликативно, тогда как предположение Гольдбаха относится к аддитивному свойству. Поэтому это предположение преспокойно может быть верным, но при этом может не существовать строгого способа доказать это.

Для случая 4-стержневой "Ханойской башни" есть множество способов достичь того, что нам кажется кратчайшим числом ходов, но у нас нет способа как-то охарактеризовать эти решения. Именно поэтому я для себя решил, что никогда не смогу решить ее, и прекратил над ней думать в 1972 году. Но в свое время я потратил целую неделю, всерьез пытаясь ее решить.

Вопрос: Каковы сейчас пять самых важных задач в информатике?

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

Вопрос: Вы долгое время занимались компьютерной подготовкой текстов. Каковы ваши впечатления от результатов этой работы?

Кнут: Я очень счастлив, что моя работа была в открытом доступе и позволила людям на всех платформах общаться друг с другом через Интернет. Я особенно обрадован несколькими последними проектами. Две недели назад я слушал замечательную лекцию Бернда Вегнера (Berndt Wegner) из Берлинского Технического Университета о планах сетевых журналов Европейского Математического Общества. Это было бы просто немыслимо без свободно распространяемых программных продуктов, выросших из моей работы. Поэтому я очень доволен, что она способствует прогрессу науки.

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

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

Вопрос: Не могли бы вы обрисовать перспективы информатики, вехи ее развития на следующие десять - двадцать лет?

Кнут: Вы опять спрашиваете о вехах. Есть большой интерес к приложениям в биологии, так как в этой области в последнее время было много чего открыто и существуют шансы победить болезни. Тот факт, что существование человека основан на дискретном коде, означает что люди вроде вас и меня, хорошо разбирающихся в дискретных задачах, способны сделать в этой области что-то стоящее. Эти задачи очень сложны и многообещающи, поэтому я предвижу здесь хорошее будущее.

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

Насчет биологии, я думаю, мы можем уверенно предсказать, что там будут серьезные задачи еще как минимум лет 500. Я не могу сказать того же про информатику.

Вопрос: Какова связь между математикой и программированием как искусством?

Кнут: По-немецки искусство - это Kunst. Американский фильм "Искусственный интеллект" - соответственно Kunctlicher Intelligenz, одновременно "искусственный" и "художественный". Я думаю о программировании с оглядкой на красоту как о чем-то изящном, чем-то, чем вы можете гордиться, если сумели их соединить. Математика точно так же изящна. Обе науки, информатика и математика, отличны от других своей искусственностью, их нет в природе. Они полностью в нашей власти. Мы выдвигаем аксиомы, и когда мы решаем задачу, мы можем доказать, что действительно решили ее. Ни один астроном никогда не будет знать, верны ли его теории. Вы не можете слетать и померить солнце.

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

Вопрос: Какова связь между Богом и компьютерами?

Кнут: В одной из своих книг, "Освещение библейских текстов, стихи 3:16"[6] я использовал случайный выбор для изучения шестидесяти различных стихов Библии и того, что люди различных исповеданий, жившие в разное время говорили о них. Изначально я провел это исследование для себя, а потом обнаружил, что это достаточно интересно, и мне следовало бы написать об этом книгу. Шестьдесят лучших художников, многие из которых немцы, по моей просьбе проиллюстрировали ее. Эти работы дважды выставлялись в Германии, а также в других странах. Кроме того, они выставлялись в Национальном Соборе в Вашингтоне. В книге я использовал методологию, которая применяется в информатике для анализа сложных структур, чтобы проверить, не поможет ли он нашему пониманию Библии, которая, естественно, является такой сложной структурой. В книге я не даю ответов, я просто говорю, как здорово по моему мнению то, что жизнь остается непрерывным исследованием. Здесь сам путь более важен, чем его конечная цель.

Вопрос: Знаете ли вы, "P=NP"2уже доказано? Ходят слухи, что это так.

Кнут: Что именно вы слышали?

Вопрос: Что-то из России.

Кнут: Из России? Это новость для меня. Я не думаю, что кто-то уже доказал это. Но, я знаю, Энди Яо (Andy Yao) надеется решить эту задачу в ближайшие пять-десять лет. Он вдохновлен Эндрю Уайлсом (Andrew Wiles), посвятившим семь лет доказательству Последней Теоремы Ферма. Они оба из Принстона. Если кто и способен сделать это, то это Энди.

Три или четыре года назад появилась статья в китайском журнале, в которой один профессор заявлял что способен решить NP-сложную задачу3 за полиномиальное время. Он рассматривал задачу о кликах4, и использовал очень хитрый способ их представления. Метод предположительно работал за полиномиальное время, но реально требовал что-то порядка n12 шагов, так что было невозможно его проверить уже при n=5. Поэтому было очень сложно искать ошибки в его доказательстве. Я поехал в Стэнфорд и засел за него с нашими дипломниками, и нам потребовалась пара часов, чтобы найти ошибку. Я написал автору письмо об этом, и еще через пару месяцев он ответил, что "нет, нет, там нет ошибки". Я решил больше с этим не связываться. Я сделал свою часть работы. Но я не верю, что эта задача решена. Это самая сложная задача из стоящих сегодня перед современной теоретической информатикой, а возможно, и всей современной наукой.

Вопрос: Что вы думаете о криптографических алгоритмах? И о нынешних попытках политиков ограничить исследования в этой обрасти?

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

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

Вопрос: Будут ли у нас разумные машины когда-нибудь в будущем? И должны ли они быть?

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

В последние год или два вышли наводящие на размышления книги, одна, написанная Хансом Моравеком (Hans Moravec)[10], и еще одна - Рэем Казвеллом (Ray Kuzwell)[9]. Обе утверждают, что через двадцать или тридцать лет у нас будут машины, более умные, чем человек. Некоторых людей это пугает. По моему мнению, если действительно так будет - флаг им в руки. Что с того, что они будут умнее нас? Мы сможем учиться у них. Но я не вижу каких-либо прорывов в данном вопросе.

Две недели назад в Греции я был на представлении книги Кристоса Пападимитру (Cristos Papadimitrou), председателя компьютерного общества в Беркли. Он опубликовал по-гречески роман "Улыбка Тьюринга"[8]. Не хочу пересказывать сюжет, но когда он будет переведен на немецкий или английский, вы найдете там очень хорошее обсуждение искусственного интеллекта и теста Тьюринга.

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

Вопрос: Что вы думаете о патентах на программное обеспечение? Сейчас в Европе идет большая дискуссия на эту тему.

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

Алгоритмы - сугубо математические вещи, которые точно так же не должны патентоваться, как значение числа $\pi$. Но в отношении чего-нибудь нетривиального, наподобие метода внутренней точки (interior point method) в линейном программировании, гораздо больше оправданий тому, кто получает права на лицензирование метода на короткое время, вместо того, чтобы объявлять его коммерческой тайной. В этом - вся идея патентования, само слово "патент" означает "сделать доступным".

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

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

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

Кнут: Есть один человек, живущий под Франкфуртом, который, возможно, получил бы больше тысячи долларов. Еще один, из Лос-Гатоса, Калифорния, которого я никогда не встречал, обналичивает чек на $2.56 примерно раз в месяц, и так уже несколько лет. Всего я выписал более двух тысяч чеков за эти годы, в среднем чуть больше $8.00 на каждый. И даже если каждый обналичит эти чеки, более ценно для меня то, что мои книги становятся лучше.

Перевод С.В. Карпова

Литература

1 The Art of Computer Programming ,by Donald E. Knuth. Русский перевод этого трехтомника "Искусство программирования" переиздавался последний раз в 2000 г.

Volume 1:Fundamental Algorithms (third edition,Addison-Wesley,1997).

Volume 2:Seminumerical Algorithms (third edition,Addison-Wesley, 1997).

Volume 3:Sorting and Searching (second edition, Addison-Wesley, 1998).

Volume 4:Combinatorial Algorithms (in preparation).

2 Mathematical typography,by Donald E.Knuth.Bull. Amer.Math.Soc.(N.S.)1 (1979),no.2,337 372. Reprinted in Digital Typography (Stanford,California:CSLI Publications,1998),pp.19 65.

3 President's information technology advisory committee. See http://www.itrd.gov/ac/.

4 Proofs from The Book, by Martin Aigner and Gunter Ziegler. Second edition, Springer Verlag, 2001.

5 Simple word problems in universal algebras,by Peter B.Bendix and Donald Knuth.Computational Problems in Abstract Algebra ,J.Leech,ed.(Oxford: Pergamon,1970),pp.263 297.Reprinted in Automation of Reasoning ,Jorg H.Siekmann and Graham Wrightson,eds.(Springer,1983),pp.342 376.

6 3:16 Bible Texts Illuminated, by Donald E.Knuth. A-R Editions,Madison,Wisconsin,1990.

7 Semantics of context-free languages,by Donald E. Knuth.Mathematical Systems Theory 2 (1968), 127 145.See also The genesis of attribute grammars,in Lecture Notes in Computer Science 461 (1990),1 12.

8 TO XAMOGELO TOY TOYRINGK (The Smile of Turing), by Christos Papadimitriou.Livani Publishers, Athens,Greece,2001.

9 The Age of Spiritual Machines:When Computers Exceed Human Intelligence, by Ray Kurzweil.Penguin USA,2000.

10 Robot:Mere Machine to Transcendent Mind, by Hans P.Moravec. Oxford University Press, 2000.


Примечания переводчика:

1 NP-полные задачи, класс наиболее сложных задач из принадлежащих к NP, то есть разрешимых за полиномиальное время на недетерминированной машине Тьюринга. Разрешимость любой из NP-полных задач на детерминированной машине Тьюринга (то есть доказательство ее принадлежности к классу P) означает разрешимость любой задачи данного класса, то есть эквивалентность P=NP. Примеры задач этого класса - проверка выполнимости пропозициональных форм, задачи о максимальной клике, коммивояжере и гамильтоновом цикле. Подробнее о проблемах, связанных со сложностью вычислительных задач, можно прочитать здесь.

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

3 NP-сложная задача, разрешимая с помощью недетерминированной машины Тьюринга. К данному классу относятся, например, известные задачи коммивояжера и задача о упаковке. NP-полные задачи являются подклассом данного.

4 Задача о наибольшей клике (Maximum Clique Problem), NP-полная задача, в которой требуется найти на карте наибольшую группу городов, каждый из которых напрямую соединен дорогой со всеми городами этой группы. Для ее решения в настоящее время неизвестен алгоритм лучше, чем прямая проверка всех возможных групп.


Rambler's Top100 Яндекс цитирования