Искусство программирования | это... Что такое Искусство программирования? (original) (raw)

Искусство программирования (англ. 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 году он вышел на пенсию, с намерением полностью сконцентрироваться на написании недостающих частей и приведении в порядок существующих.

Содержание

• 1 История
• 2 Содержание
• 3 Машинно-ориентированный язык примеров
• 4 Критика
• 5 Издания
  • 5.1 Оригинальные
    * 5.1.1 Третье (текущее)
    * 5.1.2 Предыдущие
  • 5.2 Русский перевод
• 6 См. также
• 7 Ссылки
• 8 Примечания

История

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

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

Критика

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

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

Издания

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

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

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

• 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 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

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

• Дональд Кнут Искусство программирования, том 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

См. также

• Грамотное программирование

Ссылки

• Официальная страница книги от её автора (англ.)
• Computer programming as an art (pdf) Turing Award talk given by Donald Knuth
• «Robert W Floyd, In Memoriam», by Donald E. Knuth -(on the influence of Bob Floyd)
• Injokes in the books
• Who is Bill Gosper? (on the influence of Bill Gosper on the 2nd Edition of Volume 2.)
• TAoCP and its Influence of Computer Science(Softpanorama)

Примечания

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. ↑ The Art of Computer Programming
7. ↑ Zito, Tom Close Encounters of the Steve Kind. folklore.org. Архивировано из первоисточника 14 марта 2012. Проверено 11 января 2008.

• 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

Дональд Кнут
Публикации	Искусство программирования • «The Complexity of Songs» • Computers and Typesetting • Конкретная математика • Surreal Numbers • Things a Computer Scientist Rarely Talks About • Selected papers series
Программное обеспечение	ΤΕΧ • MIXAL (MIX • MMIX • GNU MDK)
Шрифты	AMS Euler • Computer Modern • METAFONT
Грамотное программирование	WEB • CWEB
Алгоритмы	Knuth's Algorithm X • Knuth–Bendix completion algorithm • Алгоритм Кнута — Морриса — Пратта • Knuth shuffle • Robinson–Schensted–Knuth correspondence • Trabb Pardo–Knuth algorithm
Other	Dancing Links • Knuth reward check • Премия Кнута • Man or boy test • Quater-imaginary base • -yllion • Potrzebie system of weights and measures