Еще один кусок искусства компьютерного программирования


Книга Дональда Кнута «Искусство компьютерного программирования» — легенда среди книг по информатике. Для тех, кто с нетерпением ждет следующей части этой работы, состоящей из нескольких частей, теперь доступна для загрузки 2-я редакция предварительной брошюры 6a.

В начале 1960-х Дональд Кнут, который в то время был доцентом Калифорнийского технологического института, принял заказ на написание книги о компиляторах языков программирования, но быстро понял, что сначала требуется книга по фундаментальной теории компьютерного программирования.

Кнут смог убедить Аддисона Уэсли в том, что эта книга — хорошая идея, и поэтому он взялся за нее, и к 1965 году он закончил черновик из двенадцати глав, состоящих из 3000 рукописных страниц, которые первоначально планировалось сделать одной книгой.

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

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

Еще два тома из семи томов, получивших аббревиатуру TAOCP, появились в 1969 и 1973 годах.

Том 2 — Получисловые алгоритмы (главы 3 и 4)

Том 3 — Сортировка и поиск (главы 5 и 6).

К этому времени Кнут присоединился к Стэнфордскому университету, к которому он до сих пор является членом, и эти первые три тома создали или, по крайней мере, консолидировали предмет информатики, а Кнут описывался как Евклид информатики. Его работа была одобрена многими, и на сайте Пирсона цитируется Билл Гейтс:

Если вы думаете, что вы действительно хороший программист … прочтите [Knuth’s] Art of Computer Programming … Вам непременно следует прислать мне резюме, если вы можете прочитать его целиком.

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

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

Во-вторых, тема первоначальной главы 7, «комбинаторный поиск», за прошедший период значительно расширилась. Это и главу 8 о рекурсии планировалось объединить в один том, но план изменился.

Новая издательская стратегия была принята, когда Кнут возобновил работу над своим великим опусом, в соответствии с которым должны были быть опубликованы короткие тома, известные как «главы». Это привело к появлению в 2005–2009 годах четырех тонких книг, которые затем были объединены в том 4A по комбинаторным алгоритмам в 2011 году, за которым вскоре последовал набор томов 1–4A в коробке.

В прошлом году Кнут согласился позволить Пирсону создать электронные версии томов 1, 2, 3 и 4A, а также тома 1, Fascicle 1, MMIX — RISC Computer for the New Millennium, который является томом, посвященным 64-битным RISC. компьютер, разработанный Кнутом для иллюстрации машинных аспектов программирования.

В 1999 году объяснил важность MMIX для TAOCP:

Он заменяет MIX, машину в стиле 1960-х, которая раньше играла такую роль … Я стремился разработать MMIX так, чтобы его машинный язык был простым, элегантным и легким для изучения. В то же время я тщательно включил все сложности, необходимые для достижения высокой производительности на практике, чтобы MMIX в принципе мог быть построен и даже, возможно, мог конкурировать с некоторыми из самых быстрых универсальных компьютеров на рынке.

MMIX настолько важен, что теперь ему посвящена еще одна книга: MMIX Supplement, The: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth.

Автором его является профессор математики и информатики Мюнхенского университета прикладных наук доктор Мартин Рукерт, который ведет домашнюю страницу MMIX.

«Я очень рад видеть настоящую книгу Мартина Рукерта: она набита полезными вещами, из которых можно извлечь невероятное количество уроков. Мартин не просто переписал мои ранние программы для MIX и переделал их на современный язык. Он проник в их сущность и воссоздал их заново с элегантностью и хорошим вкусом. Его тщательно проверенный код представляет собой значительный вклад в искусство педагогики, а также в искусство программирования ».

В настоящее время Кнут работает над томом 4B, и это средняя треть, глава 6a, которая сейчас доступна для бета-тестирования;

Кнут говорит на своей странице последних новостей:

[это] будет основным введением в тему логической удовлетворенности, подчеркивая ее многочисленные приложения, а также множество алгоритмов для решения задач SAT с все большей и большей скоростью. Осенью 2011 года я начал изучать эту тему, и она показалась мне невероятно интересной. Таким образом, я получил огромное удовольствие, рассказывая эту историю и соединяя SAT со многими другими аспектами информатики и математики.

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

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

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

Далее он просит людей связаться с ним и сообщить, что они не смогли найти никаких ошибок в длинном списке примеров в префасцилке 6a.

Так что, если вы хотите внести небольшой вклад в эту легендарную работу, посетите страницу Knuth’s Recent News, загрузите 318-страничный pdf-файл и ознакомьтесь с некоторыми из его упражнений.


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