stringtranslate.com

Искусство программирования

Искусство программирования компьютеров ( TAOCP ) — это всеобъемлющая монография , написанная ученым-компьютерщиком Дональдом Кнутом , в которой излагаются алгоритмы программирования и их анализ . Тома 1–5 предназначены для представления центрального ядра программирования для последовательных машин.

Когда Кнут начал проект в 1962 году, он изначально задумывал его как одну книгу с двенадцатью главами. Первые три тома того, что тогда должно было стать семитомным изданием, были опубликованы в 1968, 1969 и 1973 годах. Работа над томом 4 началась в 1973 году, но была приостановлена ​​в 1977 году для работы над набором, вызванной вторым изданием тома 2. Написание окончательного экземпляра тома 4A началось от руки в 2001 году, а первый онлайн-префасцикл, 2A, появился позже в 2001 году. [1] Первая опубликованная часть тома 4 появилась в мягкой обложке как Fascicle 2 в 2005 году. Том 4A в твердом переплете, объединяющий том 4, Fascicles 0–4, был опубликован в 2011 году. Том 4, Fascicle 6 («Satisfiability») был выпущен в декабре 2015 года; Том 4, выпуск 5 («Математические предварительные сведения; Возврат к началу; Танцующие ссылки») был выпущен в ноябре 2019 года.

Том 4B состоит из материала, разработанного на основе выпусков 5 и 6. [2] Рукопись была отправлена ​​издателю 1 августа 2022 года, а том был опубликован в сентябре 2022 года. [3] Выпуск 7, запланированный для тома 4C, был темой выступления Кнута 3 августа 2022 года. [4]

История

Дональд Кнут в 2005 году

Выиграв стипендию Westinghouse Talent Search , Кнут поступил в Технологический институт Кейса (ныне Университет Кейса Вестерн Резерв ), где его успеваемость была настолько выдающейся, что факультет проголосовал за присуждение ему степени магистра наук по завершении им степени бакалавра . Во время летних каникул Кнут был нанят корпорацией Burroughs для написания компиляторов , зарабатывая за летние месяцы больше, чем профессора зарабатывали за целый год. [5] Такие подвиги сделали Кнута темой для обсуждения на математическом факультете, в который входил Ричард С. Варга .

В январе 1962 года, когда он был аспирантом на математическом факультете Калтеха, Эддисон-Уэсли обратился к Кнуту с просьбой написать книгу о проектировании компиляторов, и он предложил более широкий охват. В тот же день он составил список из двенадцати названий глав. Летом 1962 года он работал над компилятором FORTRAN для UNIVAC , считая, что он «продал душу дьяволу», чтобы разработать компилятор FORTRAN [6] : 15  после разработок ALGOL с Burroughs. Он оставался консультантом Burroughs в период с 1960 по 1968 год, пока писал том 1 «Фундаментальные алгоритмы».

В это время он также разработал математический анализ линейного зондирования , что убедило его представить материал с количественным подходом. Получив докторскую степень в июне 1963 года, он начал работать над своей рукописью, первый черновик которой он закончил в июне 1965 года, в3000 рукописных страниц. [7] Он предполагал, что около пяти рукописных страниц можно перевести в одну печатную страницу, но его издатель вместо этого сказал, что около 1+1 ⁄ 2 рукописных страниц переведены в одну печатную страницу. Это означало, что у него было примерно2000 печатных страниц материала, что почти соответствует объему первых трех опубликованных томов.

На написание первого тома «Искусства программирования» — «Фундаментальные алгоритмы» ушло пять лет с 1963 по 1968 год, в течение которых он работал и в Калтехе, и в Берроузе.

Посвящение Кнута в первом томе гласит:

Эта серия книг с любовью посвящается
компьютеру Type 650, когда-то установленному в
Технологическом институте Кейса ,
в память о многих приятных вечерах. [a]

В предисловии он благодарит сначала свою жену Джилл, затем Берроуза за использование компьютеров B220 и B5500 при тестировании большинства программ, а также Калифорнийский технологический институт, Национальный научный фонд и Управление военно-морских исследований. [8] : xii 

Раздел 2.5 «Основных алгоритмов» посвящен динамическому распределению памяти . Части этого используются в подходе Берроуза к управлению памятью. Кнут утверждает, что «метод «граничной метки», представленный в разделе 2.5, был разработан автором в 1962 году для использования в управляющей программе для компьютера B5000». [8] : 460 

Кнут получил поддержку от Ричарда С. Варги, который был научным консультантом издателя. Варга навещал Ольгу Таусски-Тодд и Джона Тодда в Калтехе . С восторженным одобрением Варги издатель принял расширенные планы Кнута. В расширенной версии книга будет опубликована в семи томах, каждый из которых будет содержать всего одну или две главы. [9] Из-за роста главы 7, которая составляла менее 100 страниц рукописи 1965 года, согласно Тому 4A, стр. vi, план Тома 4 с тех пор расширился и включил Тома 4A, 4B, 4C, 4D и, возможно, больше.

В 1976 году Кнут подготовил второе издание второго тома, требуя, чтобы его снова набрали , но стиль шрифта, использованный в первом издании (называемый горячим шрифтом ), больше не был доступен. В 1977 году он решил потратить некоторое время на создание чего-то более подходящего. Восемь лет спустя он вернулся с T E X , который в настоящее время используется для всех томов.

Еще одной характерной чертой томов является различная сложность упражнений, включая числовую оценку от 0 до 50, где 0 — незначительный вопрос, а 50 — открытый вопрос в современных исследованиях.

Вознаграждение за обнаружение ошибок

Предложение так называемого чека вознаграждения Кнута на сумму «один шестнадцатеричный доллар» (100 шестнадцатеричных центов по основанию 16 в десятичной системе счисления составляют 2,56 доллара) за любые найденные ошибки, а также исправление этих ошибок в последующих изданиях способствовали тому, что работа остается безупречной и по-прежнему авторитетной даже спустя долгое время после ее первой публикации.

Язык ассемблера в книге

Все примеры в книгах используют гипотетический язык под названием « язык ассемблера MIX » (MIXAL), который работает на «мифическом компьютере под названием MIX». В настоящее время [ когда? ] компьютер MIX заменяется компьютером MMIX , который является версией RISC . Преобразование из MIX в MMIX было большим текущим проектом, для которого Кнут привлекал добровольцев для помощи. Существует программное обеспечение, такое как GNU MDK [10], для обеспечения эмуляции архитектуры MIX. Кнут считает использование языка ассемблера необходимым для оценки скорости и использования памяти алгоритмами.

MIX был очень похож на любой компьютер, существовавший в то время, но красивее. Название «MIX» — это 1009 римскими цифрами, и это дается формулой, включающей серийные номера нескольких компьютеров того времени: (360 + 650 + 709 + U3 + SS80 + 1107 + 1604 + G2- + B220 + S2000 + 920 + 601 + H800 + PDP-4 + 11)/16 = 1009 или MIX. Название MMIX — это 2009 римскими цифрами, и Кнут утверждает, что MMIX даже красивее, чем MIX.

Критический ответ

Кнут был награжден премией Тьюринга 1974 года «за его значительный вклад в анализ алгоритмов […], и в частности за его вклад в «искусство компьютерного программирования» посредством его известных книг в непрерывной серии под этим названием». [11] American Scientist включил эту работу в число «100 или около того книг, которые сформировали век науки», имея в виду двадцатый век. [12] На обложках третьего издания тома 1 цитируются слова Билла Гейтса : «Если вы думаете, что вы действительно хороший программист… прочитайте « Искусство компьютерного программирования » (Кнута) … Вам определенно следует прислать мне резюме, если вы сможете прочитать его целиком». [13] New York Times назвала его «определяющим трактатом профессии». [14]

Объемы

Завершенный

Планируется

Конспекты глав

Завершенный

Том 1 – Фундаментальные алгоритмы

Том 2 – Получисленные алгоритмы

Том 3 – Сортировка и поиск

Том 4А – Комбинаторные алгоритмы, часть 1

Том 4B – Комбинаторные алгоритмы, часть 2

Планируется

Тома 4C, 4D, 4E, 4F – Комбинаторные алгоритмы[15]

Том 5 – Синтаксические алгоритмы

Том 6 – Теория контекстно-свободных языков[16]

Том 7 – Методы компиляции

Английские издания

Текущие издания

Ниже приведены текущие издания в порядке возрастания номера тома:

Предыдущие выпуски

Полные тома

Эти тома были заменены более новыми изданиями и отсортированы по дате.

Фасциклы

Том 4, выпуски 0–4 были пересмотрены и опубликованы как том 4А.

Том 4, разделы 5–6 были переработаны и опубликованы как том 4B.

Префасцикулы

Том 1

Том 4

Оставшиеся предварительные выпуски содержат черновой материал, который должен появиться в будущих выпусках и томах.

Смотрите также

Ссылки

Примечания

  1. ^ В первом издании посвящение было сформулировано несколько иначе.

Цитаты

  1. ^ "примечание к ящику 3, папке 1".
  2. ^ Вкладка «Содержание» веб-страницы книги Pearson InformIT. Addison-Wesley Professional. 2022-09-28. ISBN 9780201038064.
  3. ^ Веб-страница Pearson InformIT. Addison-Wesley Professional. 2022-09-28. ISBN 9780201038064.
  4. ^ «CP 2022. Все вопросы. Ответы, 31 июля — 5 августа 2022 г., Хайфа, Израиль».
  5. ^ Франа, Филип Л. (2001-11-08). «Интервью с Дональдом Э. Кнутом». hdl :11299/107413.
  6. ^ Фейгенбаум, Эдвард (2007). «Устная история Дональда Кнута» (PDF) . Музей компьютерной истории . Архивировано (PDF) из оригинала 2008-12-09 . Получено 2020-09-17 .
  7. ^ Кнут, Дональд Э. (1993-08-23). ​​"Классика цитирования этой недели" (PDF) . Текущее содержание . стр. 8.
  8. ^ ab Knuth, Donald Ervin (2019-08-03). "Искусство программирования компьютеров (TAOCP) 2-е издание, 1973". Архивировано из оригинала 2019-08-03 . Получено 2018-02-06 .
  9. ^ Альберс, Дональд Дж. (2008). «Дональд Кнут». В Альберсе, Дональд Дж.; Александерсон, Джеральд Л. (ред.). Люди-математики: профили и интервью (2-е изд.). АК Петерс . ISBN 978-1-56881-340-0.
  10. ^ "GNU MDK - Проект GNU - Фонд свободного программного обеспечения". www.gnu.org . Получено 2022-10-23 .
  11. ^ "Дональд Э. Кнут – Лауреат премии имени А. М. Тьюринга". А. М. Тьюринг . Получено 25.01.2017 .
  12. ^ Моррисон, Филип ; Моррисон, Филис (ноябрь–декабрь 1999 г.). «100 or so a Century of Science Books» (около 100 книг, которые сформировали век науки). American Scientist . 87 (6). Sigma Xi, The Scientific Research Society (Научно-исследовательское общество). Архивировано из оригинала 20-08-2008 . Получено 11-01-2008 .
  13. ^ Вайнбергер, Мэтт. «Билл Гейтс однажды сказал: «Обязательно пришлите мне резюме», если закончите эту чертовски сложную книгу». Business Insider . Получено 13 июня 2016 г.
  14. ^ Лор, Стив (2001-12-17). "Фрэнсис Э. Холбертон, 84, ранний программист". The New York Times . Получено 2010-05-17 .
  15. ^ Д'Агостино, Сьюзен (16.04.2020). «Ученый-компьютерщик, который не может перестать рассказывать истории». Журнал Quanta . Получено 26.06.2023 . Сейчас ему 82 года, и он усердно работает над частью B четвертого тома и ожидает, что книга будет иметь по крайней мере части с A по F.
  16. ^ «TAOCP – Планы на будущее».
  17. ^ ab "TAOCP – Брошюра" (PDF) .
  18. ^ ab Wells, Mark B. (1973). "Обзор: Искусство программирования, том 1. Фундаментальные алгоритмы и том 2. Получисленные алгоритмы Дональда Э. Кнута" (PDF) . Бюллетень Американского математического общества . 79 (3): 501–509. doi : 10.1090/s0002-9904-1973-13173-8 .

Источники

Внешние ссылки