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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Назва Мистецтво Програмування
Автор Дональд Кнут
Назва мовою оригіналу The Art of Computer Programming
Мова англійська
Жанр Інформатика
Видавництво Вільямс / Addison–Wesley
Публікація 19682009

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

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

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

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

Видання[ред.ред. код]

Виноски[ред.ред. код]

  1. http://www-cs-faculty.stanford.edu/~knuth/taocp.html The Art of Computer Programming