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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Искусство программирования
The Art of Computer Programming
Автор:

Дональд Кнут

Жанр:

Информатика

Язык оригинала:

английский

Оригинал издан:

1968

Переводчик:

С.Г.Тригуб, Ю.Г.Гордиенко, И.В.Красикова

Серия:

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

Издатель:

Вильямс / Addison–Wesley

Выпуск:

1968 - 2009

Электронная версия

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

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

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

История[править | править исходный текст]

В качестве признанного эксперта по созданию компиляторов, в 1962 году Кнут начал писать книгу по их проектированию. Вскоре он осознал, что охват материала должен быть намного шире. В июне 1965 года он закончил написание первой версии того, что он изначально хотел издать одной книгой из двенадцати разделов. Объём рукописного текста составил 3000 страниц. По расчётам Кнута, этот объём должен был уместиться на 600 страницах печатного текста, но, как сообщил ему его издатель, реальный объём составил бы 2000 страниц. В связи с этим структура книги была пересмотрена в пользу нескольких томов, по 1-2 раздела каждый. С тех пор, в связи с постоянным ростом материала, было решено, что четвёртый том также будет разбит на отдельные книги: 4A, 4B, 4C, а возможно, и 4D. Но и это разделение по-видимому не будет окончательным, так как разделы 7.1 и 7.2.1 уже в сумме занимают более 650 страниц.

В 1976 году Кнут подготовил второе издание второго тома, что потребовало повторного набора. Но типографское оформление (монотипия), использовавшееся в первом издании, к этому моменту уже было недоступно. Чтобы избежать подобных огорчений в будущем, в 1977 году Кнут начал разрабатывать собственную типографскую систему компьютерного набора. По его расчётам, работа должна была занять не более шести месяцев, но потребовалось около десяти лет, прежде чем она была завершена[4]. Система получила название TeX, и в настоящее время используется для верстки всех томов «Искусства программирования». Кроме того, впоследствии, TeX стал фактическим стандартом для написания статей и монографий по естественным наукам.

Как и другие книги Кнута, «Искусство программирования» отмечена его «фирменным знаком»: за каждую ошибку, найденную в тексте, автор выплачивает один шестнадцатеричный доллар, то есть $2,56 (0x100 центов, в системе счисления по основанию 16). Другой отличительной особенностью книги является обилие упражнений для самостоятельного выполнения, разной степени сложности, начиная от простых задачек «для разогрева» и заканчивая открытыми проблемами. Сложность каждого упражнения оценена по числовой шкале от 0 до 50. Так, в ранних изданиях числом 50 была отмечена Великая теорема Ферма, но в третьем издании эта оценка «девальвировала» до 45, так как к этому моменту её доказательство уже перестало быть открытой проблемой[5].

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

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

Критика[править | править исходный текст]

Основной чертой монографии Кнута, выгодно отличающей её от других книг, посвящённых программированию, является исключительно высоко поднятая планка качества материала и академичности изложения, а также глубина анализа рассматриваемых вопросов. Благодаря этому она стала настоящим бестселлером и настольной книгой каждого профессионального программиста[6]. Журнал American Scientist включил «Искусство программирования» в список 12 лучших физико-математических монографий XX-го столетия[2] вместе с работами Дирака по квантовой механике, Эйнштейна по теории относительности, Рассела и Уайтхеда по основаниям математики и немногочисленными другими[7].

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

Издания[править | править исходный текст]

Оригинальные[править | править исходный текст]

Третье (текущее)[править | править исходный текст]

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

  • 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

Предыдущие[править | править исходный текст]

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

Русский перевод[править | править исходный текст]

  • Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
  • Дональд Кнут Искусство программирования, том 1, выпуск 1. MMIX -- RISC-компьютер для нового тысячелетия = The Art of Computer Programming, Volume 1, Fascicle 1 : MMIX -- A RISC Computer for the New Millennium. — М.: «Вильямс», 2006. — С. 160. — ISBN 0-201-85392-2
  • Дональд Кнут Искусство программирования, том 2. Получисленные алгоритмы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
  • Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — С. 824. — ISBN 0-201-89685-0
  • Дональд Кнут Искусство программирования, том 4, A. Комбинаторные алгоритмы, часть 1 = The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. — М.: «Вильямс», 2013. — 960 с. — ISBN 978-5-8459-1744-7

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Примечания[править | править исходный текст]

  1. The Art of Computer Programming
  2. 1 2 Morrison, Philip & Morrison, Phylis (1999), "«100 or so Books that shaped a Century of Science»", American Scientist (Sigma Xi, The Scientific Research Society) . — Т. 87 (6), <http://www.americanscientist.org/bookshelf/pub/100-or-so-books-that-shaped-a-century-of-science>. Проверено 11 января 2008. 
  3. 1 2 Knuth: Retirement
  4. History of TeX — TeX Users Group
  5. Вильямс — Рецензии на книгу найти не удалось
  6. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4, От издателей русского перевода
  7. The Art of Computer Programming
  8. Zito, Tom Close Encounters of the Steve Kind. folklore.org. Проверено 11 января 2008. Архивировано из первоисточника 14 марта 2012.
  • Slater Robert Portraits in Silicon. — MIT Press, 1987. — ISBN 0-262-19262-4
  • Shasha Dennis Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. — Copernicus, 1995. — ISBN 0-387-97992-1