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

«Мистецтво Програмування»

Автор	Дональд Кнут
Назва мовою оригіналу	The Art of Computer Programming
Мова	англійська
Тема	алгоритм
Жанр	Інформатика
Видавництво	Вільямс / Addison–Wesley
Видано	1968—видання продовжується
Вебсайт	cs.stanford.edu/~knuth/taocp.html

Мистецтво програмування (англ. The Art of Computer Programming (TAOCP)) — фундаментальна монографія відомого американського фахівця в галузі комп'ютерних наук та математика Дональда Кнута, присвячена розгляду та аналізу найважливіших алгоритмів, що застосовуються в інформатиці. 1999 року книгу було визнано однією з дванадцяти найкращих фізико-математичних монографій століття.

Написання книги було розпочате автором 1962 року. Спочатку планувалося випустити її одним томом, але обсяг матеріалу виявився настільки великим, що кількість томів було збільшено до семи. Перші три томи було видано досить швидко: перший том — 1968 р., другий том — 2 1969 року, та третій — 1973 року, після чого було зроблено перерву до лютого 2005 року, в якому автор опублікував першу частину четвертого тому. Було прийнято рішення випускати інші частини четвертого тому приблизно по дві на рік окремими випусками, після чого офіційно видати весь четвертий том. Протягом 2005—2009 років було видано випуски 0, 1, 2, 3 і 4, а 2011 року було видано том 4А, до якого увійшла інформація цих випусків. Також 2005 року було видано випуск 1 «MMIX — RISC-комп'ютер для нового тисячоліття», інформація з якого увійде до нового (четвертого) видання першого тому. У 2015 році був виданий випуск 6 Satisfiability, що містив середню третину майбутнього тому 4B. 2019 року було видано випуск 5 Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links, що містив першу третину майбутнього тому 4B. У 2022 році був виданий том 4B.

Час, необхідний на повне завершення книги, сам автор оцінює в 20 років безперервної щоденної роботи. Оскільки Кнут завжди вважав «Мистецтво програмування» основним проектом свого життя, 1990 року він вийшов на пенсію, з наміром повністю сконцентруватися на написанні відсутніх частин і приведення до ладу існуючих.

Історія

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

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

Видання

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

• 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

Див. також

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