Русская Википедия:Искусство программирования

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:Издание

«Искусство программирования» (Шаблон:Lang-en[1]) — фундаментальная монография известного американского математика и специалиста в области компьютерных наук Дональда Кнута, посвящённая рассмотрению и анализу важнейших алгоритмов, используемых в информатике. В 1999 году книга была признана одной из двенадцати лучших физико-математических монографий столетия[2].

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

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

История

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

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

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

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

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

Содержание

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

  • Том 1. Основные алгоритмы.
    • Глава 1. Основные понятия.
    • Глава 2. Информационные структуры.
  • Том 2. Получисленные алгоритмы.
    • Глава 3. Случайные числа.
    • Глава 4. Арифметика.
  • Том 3. Сортировка и поиск.
    • Глава 5. Сортировка.
    • Глава 6. Поиск.
  • Том 4. Комбинаторные алгоритмы.

Фактически эта схема была реализована вплоть до третьего тома включительно.

В настоящий моментШаблон:Когда издан томШаблон:Nbsp4А, который содержит первые разделы 7Шаблон:Nbspглавы. Новые разделы планируется первоначально издавать отдельными выпусками (приблизительно по 128 страниц), ориентировочно по два выпуска в год (перед выходом томаШаблон:Nbsp4А подобным образом были изданы выпуски 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
  • 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
  • Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Dancing Links, (Addison-Wesley, June 16, 2017) 320pp, Шаблон:ISBN

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

  • Кнут Д.Э. Искусство программирования для ЭВМ. Том 1. Основные алгоритмы - М.: Мир, 1976. - 735 с.
  • Кнут Д.Э. Искусство программирования для ЭВМ. Том 2. Получисленные алгоритмы - М.: Мир, 1977. - 724 с.
  • Кнут Д.Э. Искусство программирования для ЭВМ. Том 3. Сортировка и поиск - М.: Мир, 1978. - 844 с.

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

  • 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-13: 978-0133992311,

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Дональд Кнут

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Cite web
  2. ↑ 2,0 2,1 Шаблон:Citation Шаблон:Wayback
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
  5. ↑ Шаблон:Cite web
  6. ↑ Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4, От издателей русского перевода
  7. ↑ Шаблон:Cite web
  8. ↑ Шаблон:Cite news
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Искусство_программирования&oldid=10019522