80-летний Дональд Кнут все еще улучшает TAOCP


Дональд Кнут, автор классической книги «Искусство компьютерного программирования», отметил свое 80-летие и все еще работает над улучшением своей монументальной работы. Он также все еще надеется, что люди проверят сложные упражнения TAOCP, чтобы убедиться, что они верны.

Одному из величайших деятелей информатики Дональду Кнуту исполнилось 80 лет. Это событие ознаменовалось празднованием Knuth80 в городе Питео на севере Швеции. На мероприятии была отмечена работа Кнута как в области компьютерных наук, так и в музыке, и был проведен научный симпозиум под названием «Knuth80: алгоритмы, комбинаторика и информация». В симпозиуме приняли участие некоторые известные компьютерные науки.

Боб Седжвик, профессор компьютерных наук Уильяма О. Бейкера в Принстонском университете, выступил с докладом об оценке мощности; Тим Рафгарден, профессор компьютерных наук в Стэнфордском университете, рассказал о «Дон», стабильных сопоставлениях и матроидах. Войтек Шпанковски, профессор Саула Розена в области компьютерных наук, электротехники и вычислительной техники в Университете Пердью, провел сессию на тему «Аналитическая теория информации: от Шеннона до Кнута и обратно».

После сеансов информатики состоялась мировая премьера Fantasia Apocalyptica, мультимедийного произведения для органа и видео, написанного Кнутом.

Кнут все еще усердно работает в Стэнфорде и продолжает работать над The Art of Computer Programming. Он возвращается к книге, добавляя или уточняя области, где, как он говорит на своем веб-сайте, он добавляет вещи, о которых он не знал в 1960-х.

Один из разделов TAOCP недавно был опубликован в предварительной форме в мягкой обложке в виде тома 4, выпуск 6: «Удовлетворенность». Том включает в себя подробную информацию о семи различных решателях SAT, начиная от простых алгоритмов, подходящих для небольших задач, и заканчивая современными алгоритмами промышленного уровня. Другие темы включают проверку ограниченной модели, теорию следов, алгоритмы Лас-Вегаса, фазовые изменения в случайных процессах, эффективное кодирование задач в конъюнктивную нормальную форму и использование глобальных и локальных симметрий. Предлагается более 500 упражнений, тщательно составленных для самостоятельного обучения, вместе с подробными ответами.

Кнут говорит:

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

Я все еще придерживаюсь убеждения, что эти детали чрезвычайно поучительны, и меня не устраивает перспектива напечатать печатное издание с таким количеством невыполненных упражнений. Таким образом, я хотел бы внести сюда призыв к некоторым читателям прямо сказать мне: « Дорогой Дон, я очень внимательно прочитал упражнение N и ответ на него, и я считаю, что оно на 100% правильно ».

Затем он приводит список упражнений в Части 6 тома 4 и говорит, что, хотя многие другие упражнения в книге «совершенно не страшны», на самом деле довольно элементарны,

«Конечно, я хочу вдаваться в подробности высокого уровня, чтобы помочь продвинутым читателям; и эти темные уголки моих книг, естественно, труднее всего исправить. Отсюда и этот призыв о помощи».

Итак, поехали. Вы можете заслужить благодарность компьютерной легенды.


Добавить комментарий