Мистецтво програмування

Як визнаний експерт зі створення компіляторів, Кнут почав писати книгу для їх проектування 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-го століття разом з роботами Дірака з квантової механіки, Ейнштейна з теорії відносності, Рассела і Уайтхеда з основ математики та деякими іншими[1].

Обкладинка третього видання першого тому книги містить цитату Білла Гейтса: «Якщо ви вважаєте себе справді добрим програмістом …, прочитайте „Мистецтво програмування“ Кнута … Якщо ви зможете зрозуміти всю цю працю, то вам, безумовно, слід надіслати мені резюме». Втім, фольклор приписує ці слова Стіву Джобсу.

Поточне видання:

• 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 4, Fascicle 5: Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links. (Addison-Wesley Professional, 2019), xiii+383pp. ISBN 978-0-13-467179-6
• Volume 4, Fascicle 6: Satisfiability. (Addison-Wesley Professional, 2015), xiii+310pp. ISBN 978-0-13-439760-3

• Вступ до алгоритмів