Искусство компьютерного программирования ( TAOCP ) — это обширная монография , написанная учёным-компьютерщиком Дональдом Кнутом, в которой представлены алгоритмы программирования и их анализ . Тома 1–5 предназначены для представления основного ядра компьютерного программирования для последовательных машин.
Когда Кнут начал этот проект в 1962 году, он изначально задумывал его как одну книгу из двенадцати глав. Первые три тома семитомного набора были опубликованы в 1968, 1969 и 1973 годах. Серьезная работа над четвертым томом началась в 1973 году, но была приостановлена в 1977 году из-за работы над набором текста, вызванной вторым изданием. Тома 2. Написание окончательной версии Тома 4А началось в 2001 году от руки, а первый онлайн-предварительный выпуск, 2А, появился позже в 2001 году. [1] Первая опубликованная часть Тома 4 появилась в мягкой обложке под названием Fascicle 2 в 2005. Том 4A в твердом переплете, объединяющий Том 4, Главы 0–4, был опубликован в 2011 году. Том 4, Глава 6 («Выполнимость») был выпущен в декабре 2015 года; Том 4, выпуск 5 («Математические предварительные сведения; Возврат; Танцующие ссылки») был выпущен в ноябре 2019 года.
Том 4B состоит из материала, полученного из выпусков 5 и 6. [2] Рукопись была отправлена издателю 1 августа 2022 года, а том был опубликован в сентябре 2022 года. [3]
Глава 7, запланированная для тома 4C, была тема выступления Кнута 3 августа 2022 г. [4]
История
Дональд Кнут в 2005 году
Выиграв стипендию Westinghouse Talent Search , Кнут поступил в Технологический институт Кейса (ныне Университет Кейс Вестерн Резерв ), где его успеваемость была настолько выдающейся, что преподаватели проголосовали за присвоение ему степени магистра наук после получения степени бакалавра . Во время летних каникул Кнут был нанят корпорацией Берроуза для написания компиляторов , зарабатывая за летние месяцы больше, чем профессора за целый год. [5] Такие подвиги сделали Кнута темой обсуждения на математическом факультете, в который входил Ричард С. Варга .
В январе 1962 года, когда он был аспирантом математического факультета Калифорнийского технологического института, Аддисон-Уэсли обратился к Кнуту с просьбой написать книгу о проектировании компиляторов, и он предложил более широкую область применения. В тот же день он составил список из двенадцати названий глав. Летом 1962 года он работал над компилятором FORTRAN для UNIVAC . За это время он также придумал математический анализ линейного зондирования , который убедил его представить материал с количественным подходом. После получения докторской степени. в июне 1963 года он начал работу над своей рукописью, первый набросок которой закончил в июне 1965 года в3000 рукописных страниц. [6] Он предполагал, что около пяти рукописных страниц можно перевести в одну печатную страницу, но его издатель вместо этого сказал, что около 1+1 ⁄ рукописных страниц переводятся на одну печатную страницу. Это означало, что у него было примерно2000 печатных страниц материала, что соответствует размеру первых трех опубликованных томов. В этот момент Кнут получил поддержку от Ричарда С. Варги, который был научным консультантом издателя. Варга навещал Ольгу Таусски-Тодд и Джона Тодда в Калифорнийском технологическом институте . При восторженной поддержке Варги издатель принял расширенные планы Кнута. В расширенной версии книга будет опубликована в семи томах, каждый из которых будет состоять всего из одной или двух глав. [7] Из-за увеличения главы 7, которая составляла менее 100 страниц рукописи 1965 года, за том. 4А с. vi, план Тома 4 с тех пор расширился и теперь включает тома 4A, 4B, 4C, 4D и, возможно, другие.
В 1976 году Кнут подготовил второе издание второго тома, потребовав его повторной верстки , но стиль шрифта, использованный в первом издании (называемый горячим шрифтом ), больше не был доступен. В 1977 году он решил потратить некоторое время на создание чего-то более подходящего. Восемь лет спустя он вернулся с T E X , который в настоящее время используется во всех томах.
Предложение так называемого чека с вознаграждением Кнута на сумму «один шестнадцатеричный доллар» (100 шестнадцатеричных центов по основанию 16 в десятичном формате равно 2,56 доллара) за любые обнаруженные ошибки, а также исправление этих ошибок в последующих печатных изданиях способствовало доведению до совершенства этой книги. и по-прежнему авторитетный характер работы даже спустя долгое время после ее первой публикации. Еще одной особенностью объемов является вариативность сложности упражнений. У Кнута даже есть числовая шкала сложности для оценки этих упражнений, варьирующаяся от 0 до 50, где 0 — тривиально, а 50 — открытый вопрос в современных исследованиях.
Посвящение Кнута гласит:
Эта серия книг с любовью посвящена компьютеру Type 650, когда-то установленному в Технологическом институте Кейса , с которым я провел много приятных вечеров. [а]
Язык ассемблера в книге
Во всех примерах в книгах используется язык под названием « Язык ассемблера MIX », который работает на гипотетическом компьютере MIX. В настоящее время [ когда? ] компьютер MIX заменяется компьютером MMIX , который является версией RISC . Для эмуляции архитектуры MIX существует такое программное обеспечение, как GNU MDK [8] . Кнут считает, что использование языка ассемблера необходимо для оценки скорости и использования памяти алгоритмами.
Критический ответ
Кнут был награжден Премией Тьюринга 1974 года «за большой вклад в анализ алгоритмов […] и, в частности, за вклад в «искусство компьютерного программирования» посредством своих хорошо известных книг из непрерывной серии под этим названием». [9] Американский ученый включил эту работу в число «100 или около того книг, сформировавших век науки», имея в виду двадцатый век, [10] . На обложке третьего издания первого тома цитируются слова Билла Гейтса : «Если вы думаете, что вы действительно хороший программист… прочтите книгу (Кнута) « Искусство компьютерного программирования »… Вам обязательно следует прислать мне резюме, если вы сможете прочитать ее целиком. " [11] The New York Times назвала его «определяющим трактатом профессии». [12]
7.2.2.9. Оценка затрат на возврат (глава 6 «Избранных статей по анализу алгоритмов» и глава 5, стр. 44–47, под заголовком «Оценки времени выполнения»)
7.2.3. Генерация неэквивалентных шаблонов (включая обсуждение теоремы перечисления Полиа ) (см. «Методы отклонения изоморфов», главу 4 книги «Алгоритмы классификации кодов и проектов» Каски и Остергарда)
Искусство компьютерного программирования, коробочный набор томов 1–4B . (Ридинг, Массачусетс: Аддисон-Уэсли, 2023), 3904 стр. ISBN 978-0-13-793510-9 , 0-13-793510-2
Том 1: Фундаментальные алгоритмы . Третье издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1997), xx+650 стр. ISBN 978-0-201-89683-1 , 0-201-89683-4 . Ошибки: [1] (08 января 2011 г.), [2] (2022 г., 49-е издание ). Приложение: [3] (2011).
Том 2: Получисловые алгоритмы . Третье издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1997), xiv+762 стр. ISBN 978-0-201-89684-8 , 0-201-89684-2 . Ошибки: [4] (08 января 2011 г.), [5] (2022 г., 45-е издание). Приложение: [6] (2011).
Том 3: Сортировка и поиск . Второе издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1998), xiv+780 стр.+раскладной. ISBN 978-0-201-89685-5 , 0-201-89685-0 . Ошибки: [7] (08 января 2011 г.), [8] (2022 г., 45-е издание). Приложение: [9] (2011).
Том 4А: Комбинаторные алгоритмы, Часть 1 . Первое издание (Аппер-Сэддл-Ривер, Нью-Джерси: Аддисон-Уэсли, 2011), xv+883 стр. ISBN 978-0-201-03804-0 , 0-201-03804-8 . Ошибки: [10] (2011 г.), [11] (2022 г., 22-е издание).
Том 4B: Комбинаторные алгоритмы, часть 2 . Первое издание (Аппер-Сэддл-Ривер, Нью-Джерси: Аддисон-Уэсли, 2023), xviii+714 стр. ISBN 978-0-201-03806-4 , 0-201-03806-4 . Опечатки: [12] (2023 г., 1-е издание).
Том 1, выпуск 1: MMIX — RISC-компьютер нового тысячелетия . (Аддисон-Уэсли, 14 февраля 2005 г.) ISBN 0-201-85392-2 . Исправления: [13] (16 марта 2020 г.) (будет в четвертом издании тома 1)
Предыдущие выпуски
Полные тома
Эти тома были заменены более новыми изданиями и упорядочены по дате.
Том 1: Фундаментальные алгоритмы . Первое издание, 1968 г., xxi+634pp, ISBN 0-201-03801-3 . [15]
Том 2: Получисловые алгоритмы . Первое издание, 1969 г., xi+624pp, ISBN 0-201-03802-1 . [15]
Том 3: Сортировка и поиск . Первое издание, 1973 г., xi+723 стр.+раскладной, ISBN 0-201-03803-X . Ошибки: [14].
Том 1: Фундаментальные алгоритмы . Второе издание, 1973 г., xxi+634pp, ISBN 0-201-03809-9 . Ошибки: [15].
Том 2: Получисловые алгоритмы . Второе издание, 1981 г., xiii+ 688 стр., ISBN 0-201-03822-6 . Ошибки: [16].
Искусство компьютерного программирования, тома 1–3 в коробочном наборе . Второе издание (Рединг, Массачусетс: Аддисон-Уэсли, 1998), стр. ISBN 978-0-201-48541-7 , 0-201-48541-9 .
Искусство компьютерного программирования, коробочный набор томов 1–4А . Третье издание (Ридинг, Массачусетс: Аддисон-Уэсли, 2011), 3168 стр. ISBN 978-0-321-75104-1 , 0-321-75104-3
Выпуски
Том 4, выпуски 0–4 были переработаны и опубликованы как Том 4A.
Том 4, выпуск 0: Введение в комбинаторные алгоритмы и логические функции . (Addison-Wesley Professional, 28 апреля 2008 г.) vi+240pp, ISBN 0-321-53496-4 . Ошибки: [17] (1 января 2011 г.).
Том 4, глава 1: Побитовые приемы и методы; Бинарные диаграммы решений . (Addison-Wesley Professional, 27 марта 2009 г.) viii+260pp, ISBN 0-321-58050-8 . Ошибки: [18] (1 января 2011 г.).
Том 4, глава 2: Генерация всех кортежей и перестановок . (Аддисон-Уэсли, 14 февраля 2005 г.) v+127pp, ISBN 0-201-85393-0 . Ошибки: [19] (1 января 2011 г.).
Том 4, глава 3: Создание всех комбинаций и разделов . (Аддисон-Уэсли, 26 июля 2005 г.) vi+150pp, ISBN 0-201-85394-9 . Ошибки: [20] (1 января 2011 г.).
Том 4, выпуск 4: Создание всех деревьев; История комбинаторной генерации . (Аддисон-Уэсли, 06 февраля 2006 г.) vi+120pp, ISBN 0-321-33570-8 . Ошибки: [21] (1 января 2011 г.).
Том 4, выпуски 5–6 были переработаны и опубликованы как Том 4B.
Том 4, выпуск 5: Математические предварительные сведения; Возврат; Танцевальные ссылки . (Аддисон-Уэсли, 22 ноября 2019 г.) xiii+382pp, ISBN 978-0-13-467179-6 . Ошибки: [22] (27 марта 2020 г.)
Том 4, глава 6: Выполнимость . (Аддисон-Уэсли, 08 декабря 2015 г.) xiii+310pp, ISBN 978-0-13-439760-3 . Ошибки: [23] (26 марта 2020 г.)
Предварительные выпуски
Том 1
Предисловие 1 было переработано и опубликовано как Том 1, глава 1.
^ «GNU MDK - Проект GNU - Фонд свободного программного обеспечения» . www.gnu.org . Проверено 23 октября 2022 г.
^ "Дональд Э. Кнут - обладатель премии А. М. Тьюринга" . А. М. Тьюринг . Проверено 25 января 2017 г.
^ Моррисон, Филип ; Моррисон, Филис (ноябрь – декабрь 1999 г.). «Приблизительно 100 книг, сформировавших век науки». Американский учёный . Сигма Си, Общество научных исследований. 87 (6). Архивировано из оригинала 20 августа 2008 г. Проверено 11 января 2008 г.
^ Вайнбергер, Мэтт. «Билл Гейтс однажды сказал: «Обязательно пришлите мне резюме», если закончите эту чертовски трудную книгу». Бизнес-инсайдер . Проверено 13 июня 2016 г.
^ Лор, Стив (17 декабря 2001 г.). «Фрэнсис Э. Холбертон, 84 года, один из первых программистов». Нью-Йорк Таймс . Проверено 17 мая 2010 г.
^ Д'Агостино, Сьюзен (16 апреля 2020 г.). «Ученый-компьютерщик, который не может перестать рассказывать истории». Журнал Кванта . Проверено 26 июня 2023 г. Сейчас ему 82 года, он усердно работает над частью B четвёртого тома и ожидает, что в книге будут как минимум части от A до F.
^ «TAOCP - Планы на будущее» .
^ Аб Уэллс, Марк Б. (1973). «Обзор: Искусство компьютерного программирования, Том 1. Фундаментальные алгоритмы и Том 2. Получисловые алгоритмы Дональда Э. Кнута» (PDF) . Бюллетень Американского математического общества . 79 (3): 501–509. дои : 10.1090/s0002-9904-1973-13173-8 .
Источники
Слейтер, Роберт (1987). Портреты из кремния. МТИ Пресс. ISBN 0-262-19262-4.
Шаша, Деннис ; Лазер, Кэти (1995). Они сошли с ума: жизнь и открытия 15 великих ученых-компьютерщиков . Коперник. ISBN 0-387-97992-1.
Внешние ссылки
Обзор тем (личная домашняя страница Кнута)
Устное историческое интервью с Дональдом Э. Кнутом в Институте Чарльза Бэббиджа , Университет Миннесоты, Миннеаполис, 2001 год. Кнут обсуждает патентование программного обеспечения, структурированное программирование , сотрудничество и свою разработку TeX . В устной истории обсуждается написание «Искусства компьютерного программирования» .
«Роберт В. Флойд, Памяти», Дональд Э. Кнут, 2003 г. - (под влиянием Боба Флойда )
