Искусство программирования

Искусство программирования
The Art of Computer Programming
Автор	Дональд Кнут
Жанр	Информатика
Язык оригинала	английский
Оригинал издан	1968
Переводчик	С. Г. Тригуб, Ю. Г. Гордиенко, И. В. Красиков и др.
Серия	Искусство программирования
Издатель	Вильямс / Addison–Wesley
Выпуск	с 1968 года

«Искусство программирования» (англ. The Art of Computer Programming) — фундаментальная монография известного американского математика и специалиста в области компьютерных наук Дональда Кнута, посвящённая рассмотрению и анализу важнейших алгоритмов, используемых в информатике. В 1999 году книга была признана одной из двенадцати лучших физико-математических монографий столетия.

Проект написания книги был начат автором в 1962 году. Изначально планировалось выпустить её одним томом, но объём материала оказался столь большим, что количество томов было увеличено до семи. Первые три тома были изданы достаточно быстро: том 1 — в 1968 году, том 2 — в 1969 году, том 3 — в 1973 году. После этого последовал перерыв до февраля 2005 года, в котором автор опубликовал первую часть четвёртого тома. Было принято решение выпускать остальные части четвёртого тома приблизительно по две в год отдельными выпусками, после чего официально издать весь четвёртый том. На протяжении 2005—2009 годов были изданы выпуски 0, 1, 2, 3 и 4, а в 2011 году был выпущен том 4А, в который вошла информация из этих выпусков. Также в 2005 году был выпущен выпуск 1 «MMIX — RISC-компьютер для нового тысячелетия», информация из которого войдёт в новое, четвёртое издание первого тома. Были изданы выпуск 6 (в 2015 году) и выпуск 5 (в 2017 году), представляющие собой части тома 4B. Сам том 4B вышел в 2022 году.

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

История

В качестве признанного эксперта по созданию компиляторов, в 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, так как к этому моменту её доказательство уже перестало быть открытой проблемой.

Сводка условных обозначений для третьего тома, 1978 год «Сортировка и поиск» (слева — оценка, справа — краткое объяснение)

• Чёрный треугольник — Рекомендуется
• М — С математическим уклоном
• ВМ — Требует знания «высшей математики»
• 00 — Требует немедленного ответа
• 10 — Простое (на 1 минуту)
• 20 — Средней трудности (на 15 мин)
• 30 — Повышенной трудности
• 40 — Для «матпрактикума»
• 50 — Исследовательская проблема

Содержание

Изначальный план написания книги предполагал следующую разбивку материала.

• Том 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-го столетия наряду с работами Дирака по квантовой механике, Эйнштейна по теории относительности, Рассела и Уайтхеда по основаниям математики.

Обложка третьего издания первого тома книги содержит цитату Билла Гейтса: «Если вы считаете себя действительно хорошим программистом…, прочитайте „Искусство программирования“ (Кнута)… Если вы сможете прочесть весь этот труд, то вам определённо следует отправить мне резюме».

Издания

Оригинальные

Третье (текущее)

В порядке возрастания номеров томов:

• Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
• Volume 1, Fascicle 1: MMIX — A RISC Computer for the New Millennium. (Addison-Wesley, February 14, 2005) ISBN 0-201-85392-2 (will be in the fourth edition of volume 1)
• Volume 2: Seminumerical Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
• Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
• Volume 4A: Combinatorial Algorithms, Part 1 (Upper Saddle River, New Jersey: Addison-Wesley, 2011), xvi+883pp. ISBN 0-201-03804-8
• Volume 4B: Combinatorial Algorithms, Part 2 (Upper Saddle River, New Jersey: Addison-Wesley, 2023), xviii+714pp. ISBN 0-201-03806-4

Предыдущие

По дате публикации:

• Volume 1, first edition, 1968. 634pp. ISBN 0-201-03801-3.
• Volume 2, first edition, 1969, xi+624pp, ISBN 0-201-03802-1.
• Volume 3, first edition, 1973, xi+723pp+centerfold, ISBN 0-201-03803-X
• Volume 1, second edition, 1973, xiii+634pp, ISBN 0-201-03809-9.
• Volume 2, second edition, 1981, xiii+ 688pp. ISBN 0-201-03822-6.
• Volume 4, Fascicle 2: Generating All Tuples and Permutations, (Addison-Wesley, February 14, 2005) v+127pp, ISBN 0-201-85393-0
• Volume 4, Fascicle 3: Generating All Combinations and Partitions. (Addison-Wesley, July 26, 2005) vi+150pp, ISBN 0-201-85394-9
• Volume 4, Fascicle 4: Generating all Trees — History of Combinatorial Generation, (Addison-Wesley, February 6, 2006) vi+120pp, ISBN 0-321-33570-8
• Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, (Addison-Wesley Professional, April 28, 2008) vi+240pp, ISBN 0-321-53496-4
• Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams (Addison-Wesley Professional, March 27, 2009) viii+260pp, ISBN 0-321-58050-8
• Volume 4, Fascicle 6: Satisfiability, (Addison-Wesley, December 8, 2015) xiii+310pp, ISBN 978-0-13-439760-3
• Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Dancing Links, (Addison-Wesley, June 16, 2017) 320pp, ISBN 978-0-13-467179-6

Русский перевод

• Кнут Д. Э. Искусство программирования для ЭВМ. Том 1. Основные алгоритмы — М.: Мир, 1976. — 735 с.
• Кнут Д. Э. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы — М.: Мир, 1977. — 724 с.
• Кнут Д. Э. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск — М.: Мир, 1978. — 844 с.
• Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы = The Art of Computer Programming. Volume 1. Fundamental Algorithms / под ред. С. Г. Тригуб (гл. 1), Ю. Г. Гордиенко (гл. 2) и И. В. Красикова (разд. 2.5 и 2.6). — 3. — Москва: Вильямс, 2002. — Т. 1. — 720 с. — ISBN 5-8459-0080-8.
• Кнут Д. Э. Искусство программирования, том 1, выпуск 1. MMIX — RISC-компьютеры нового тысячелетия = The Art of Computer Programming, Volume 1, Fascicle 1: MMIX — A RISC Computer for the New Millennium. — М.: «Вильямс», 2007. — 160 с. — ISBN 978-5-8459-1163-6.
• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы = The Art of Computer Programming. Volume 2. Seminumerical Algorithms / под ред. Л. Ф. Козаченко (гл. 3, разд. 4.6.4 и 4.7), В. Т. Тертышного (гл. 4) и И. В. Красикова (разд. 4.6). — 3. — Москва: Вильямс, 2001. — Т. 2. — 832 с. — ISBN 5-8459-0081-6.
• Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.
• Кнут Д. Э. Искусство программирования, том 4, A. Комбинаторные алгоритмы, часть 1 = The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1 / под ред. И. В. Красикова. — 1. — Москва: Вильямс, 2013. — Т. 4. — 960 с. — ISBN 978-5-8459-1744-7.

Связанные книги

• Martin Ruckert «The MMIX Supplement: Supplement to The Art of Computer Programming Volumes 1, 2, 3 by Donald E. Knuth», 1st Edition, (Addison-Wesley Professional, February 15, 2015), 224 pp, ISBN 978-0133992311,

Литература

• Slater, Robert. Portraits in Silicon (неопр.). — MIT Press, 1987. — ISBN 0-262-19262-4.
• Shasha, Dennis; Cathy Lazere. Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists (англ.). — Copernicus, 1995. — ISBN 0-387-97992-1.

Ссылки

• Официальная страница книги от её автора (англ.)
• TAoCP and its Influence of Computer Science(Softpanorama)