Искусство программирования ( англ. The Art of Computer Programming (TAOCP)) - фундаментальная монография известного американского специалиста в области компьютерных наук и математикa Дональда Кнута, посвященная рассмотрению и анализу важнейших алгоритмов, применяемых в информатике. 1999 года книга была признана одной из двенадцати лучших физико-математических монографий века.
Написание книги было начато автором 1962 года. Изначально планировалось выпустить ее одним томом, но объем материала оказался настолько велик, что количество томов было увеличено до семи. Первые три тома были изданы довольно быстро: первый том - 1968 г., второй том - 2 1969 года, и третий - 1973 года, после чего последовал перерыв до февраля 2005 года, в котором автор опубликовал первую часть четвертого тома. Было принято решение выпускать другие части четвертого тома примерно по две в год отдельными выпусками, после чего официально издать весь четвертый том. В течение 2005-2009 годов было выдано выпуски 0, 1, 2, 3 и 4, а 2011 году был издан том 4А, в который вошла информация этих выпусков. Также 2005 года был издан выпуск 1 «MMIX -RISC -компьютер для нового тысячелетия », информация с которого войдет в новый (четвертого) издания первого тома.
Время, необходимое на полное завершение книги, сам автор оценивает в 20 лет непрерывной ежедневной работы. Поскольку Кнут всегда считал «Искусство программирования» основным проектом своей жизни, в 1990 году он вышел на пенсию, с намерением полностью сконцентрироваться на написании недостающих частей и приведение в порядок существующих.
История искусства программирования
Как признанный эксперт по созданию компиляторов, Кнут начал писать книгу по их проектированию 1962 года. Вскоре он осознал, что охват материала должен быть гораздо шире. В июне 1965 года он завершил написание первой версии он сначала хотел выдать одной книгой из двенадцати разделов. Объем рукописного текста составил 3000 страниц. По расчетам Кнута, этот объем должен уместиться на 600 страницах печатного текста, но, как сообщил ему его издатель, реальный объем составил бы 2000 страниц. В этой связи структуру книги был пересмотрен в пользу нескольких томов, по 1-2 разделы каждый. времени, в связи с постоянным ростом материала, было решено, что четвертый том также будет разбит на отдельные книги: 4A, 4B, 4C, а возможно, и 4D. Но и это разделение видимо не будет окончательным, поскольку разделы 7,1 и 7.2.1 уже в сумме занимают более 650 страниц.
1976 Кнут подготовил второе издание второго тома, что потребовало повторного набора. Но типографское оформление, которое применялось в первом издании, в то время уже было недоступным. Чтобы избежать подобных неприятностей в будущем, 1977 года Кнут начал разрабатывать собственную типографскую систему компьютерного набора. По его расчетам, работа должна продолжаться не более шести месяцев, но было понадобилось около десяти лет, прежде чем она была завершена. Система получила названиеTeX, и сейчас применяется для верстки всех томов «Искусства программирования». Кроме того, впоследствии, TeX стал фактическим стандартом для написания статей и монографий по естественным наукам.
Как и другие книги Кнута, «Искусство программирования» отмечен его «фирменным знаком»: за каждую ошибку, найденную в тексте, автор выплачивает один шестнадцатиричный доллар, то есть $ 2,56 (0x100 центов, в системе счисления по основе 16 ). Другой отличительной особенностью книги является большое количество упражнений для самостоятельного выполнения, различной степени сложности, начиная от простых задачек «для разогрева» и заканчивая проблемами, решение которых вообще неизвестно. Сложность каждого упражнения оценен по числовой шкале от 0 до 50. Так, в ранних изданиях оценкой 50 была обозначена Великую теорему Ферма, но в третьем издании эта оценка «девальвировала» до 45, поскольку к тому времени теорему уже было доказано.
Содержание
Первоначальный план написания книги предполагал следующую разбивку материала.
- Том 1. Основные алгоритмы.
- Глава 1. Основные понятия.
- Глава 2. Информационные структуры.
- Том 2. Напивчисельни алгоритмы.
- Глава 3. Случайные числа.
- Глава 4. Арифметика.
- Том 3. Сортировка и поиск.
- Глава 5. Сортировка.
- Глава 6. Поиск.
- Том 4. Комбинаторные алгоритмы.
- Глава 7. Комбинаторный поиск.
- Глава 8. Рекурсия.
- Том 5. Синтаксические алгоритмы.
- Глава 9. Лексикографический поиск.
- Глава 10. Синтаксический поиск.
- Том 6. Теория языков.
- Том 7. Компиляторы.
Фактически эта схема была реализована до третьего тома включительно.
Сейчас издано том 4А, содержащий первые главы 7 главы. Новые разделы планируется сначала выдавать отдельными выпусками (примерно по 128 страниц), ориентировочно по два выпуска в год (перед выходом том 4А подобным образом были изданы выпуски 0, 1, 2, 3 и 4).
Машинно-ориентированный язык примеров
Примеры программ, приведенные в книге, используют «MIX-ассемблер», предназначенный для работы на гипотетическом MIX-компьютере. В третьем издании морально устаревший MIX был заменен на MMIX, имеющий полноценную RISC-архитектуру. Существует программное обеспечение, обеспечивающее эмуляцию (M) MIX-машины на стандартных IBM-совместимых компьютерах. GNU Compiler Collection имеет возможность компиляции C / C++ кода на целевой архитектуре MMIX.
Многих читателей отталкивает факт использования языка низкого уровня, но Кнут считает свой выбор оправданным, поскольку привязка к архитектуре необходима для того, чтобы можно было точно судить о таких характеристиках алгоритма, как скорость, использование памяти и др.. Однако, вследствие такого выбора, целевая аудитория сильно сужается. Кроме того, ограничивается область ее применения как «книги рецептов» для программистов-практиков, многие из которых не знают ассемблера, а если и знают, то не испытывают желания переводить низкоуровневые алгоритмы из книги на языки высокого уровня. Многочисленные практические руководства, в которых тот же материал излагается более популярно, выдают именно по этой причине.
Критика
Основной чертой монографии Кнута, что выгодно отличает ее от других книг, посвященных программированию, чрезвычайно высоко поднята планка качества материала и академичности изложения, а также глубина анализа рассматриваемых вопросов. Благодаря этому она стала настоящим бестселлером и настольной книгой каждого профессионального программиста. Журнал American Scientist включил «Искусство программирования» в список 12 лучших физико-математических монографий XX-го века вместе с работами Дирака по квантовой механике, Эйнштейна по теории относительности, Рассела и Уайтхеда по основам математики и некоторыми другими.
Обложка третьего издания первого тома книги содержит цитату Билла Гейтса : "Если вы считаете себя действительно хорошим программистом..., прочитайте "Искусство программирования» Кнута... Если вы сможете понять всю эту работу, то вам, безусловно, следует прислать мне резюме ". Впрочем, фольклор приписывает эти слова Стиву Джобсу.
