Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Книги об алгоритмах Дональда Кнута
Books about algorithms by Donald Knuth
«Искусство компьютерного программирования» (TAOCP) — это всеобъемлющая монография, написанная ученым-компьютерщиком Дональдом Кнутом, представляющая алгоритмы программирования и их анализ. Тома 1–5 предназначены для представления центрального ядра компьютерного программирования для последовательных машин. Когда Кнут начал работу над проектом в 1962 году, он изначально задумывал его как одну книгу из двенадцати глав. Первые три тома серии, которая тогда планировалась из семи томов, были опубликованы в 1968, 1969 и 1973 годах. Работа над 4-м томом началась в 1973 году, но была приостановлена в 1977 году для работы над набором текста, вызванной вторым изданием 2-го тома. Написание окончательного варианта тома 4А началось от руки в 2001 году, а первый онлайн-предварительный выпуск, 2А, появился позже в 2001 году. Первый опубликованный выпуск 4-го тома вышел в мягкой обложке как Fascicle 2 в 2005 году. Том 4А в твердой обложке, объединяющий том 4 и Fascicles 0–4, был опубликован в 2011 году. Fascicle 6 тома 4 («Satisfiability») был выпущен в декабре 2015 года; Fascicle 5 тома 4 («Mathematical Preliminaries Redux; Backtracking; Dancing Links») был выпущен в ноябре 2019 года. Том 4B состоит из материалов, развитых из Fascicles 5 и 6. Рукопись была отправлена издателю 1 августа 2022 года, а том был опубликован в сентябре 2022 года. Fascicle 7, запланированный для тома 4C, был темой доклада Кнута 3 августа 2022 года.
The Art of Computer Programming (TAOCP) is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of computer programming for sequential machines. When Knuth began the project in 1962, he originally conceived of it as a single book with twelve chapters. The first three volumes of what was then expected to be a seven volume set were published in 1968, 1969, and 1973. Work began in earnest on Volume 4 in 1973, but was suspended in 1977 for work on typesetting prompted by the second edition of Volume 2. Writing of the final copy of Volume 4A began in longhand in 2001, and the first online pre fascicle, 2A, appeared later in 2001. The first published installment of Volume 4 appeared in paperback as Fascicle 2 in 2005. The hardback Volume 4A, combining Volume 4, Fascicles 0–4, was published in 2011. Volume 4, Fascicle 6 ("Satisfiability") was released in December 2015; Volume 4, Fascicle 5 ("Mathematical Preliminaries Redux; Backtracking; Dancing Links") was released in November 2019. Volume 4B consists of material evolved from Fascicles 5 and 6. The manuscript was sent to the publisher on August 1, 2022, and the volume was published in September 2022. Fascicle 7, planned for Volume 4C, was the subject of Knuth's talk on August 3, 2022.
Язык собрания в книге
Все примеры в книгах используют язык программирования "ассемблер MIX", который работает на гипотетическом компьютере MIX. В настоящее время компьютер MIX заменяется компьютером MMIX, являющимся RISC-версией. Существует программное обеспечение, такое как GNU MDK, для эмуляции архитектуры MIX. Кнут считает, что использование языка ассемблера необходимо для оценки быстродействия и потребления памяти алгоритмами.
All examples in the books use a language called "MIX assembly language", which runs on the hypothetical MIX computer. Currently, the MIX computer is being replaced by the MMIX computer, which is a RISC version. Software such as GNU MDK exists to provide emulation of the MIX architecture. Knuth considers the use of assembly language necessary for the speed and memory usage of algorithms to be judged.
Критический отклик
Кнут был удостоен премии Тьюринга 1974 года «за его значительный вклад в анализ алгоритмов [ ], и в особенности за вклад в «искусство программирования» благодаря его известным книгам, выходящим непрерывной серией под этим названием». Журнал American Scientist включил эту работу в список «примерно ста книг, сформировавших столетие науки», подразумевая двадцатый век. На обложке третьего издания первого тома приводится цитата Билла Гейтса: «Если вы считаете себя действительно хорошим программистом, прочитайте «Искусство программирования» (Knuth’s). Вам обязательно стоит прислать мне резюме, если вы сможете прочитать все книги». Газета The New York Times назвала эту работу «определяющим трудом профессии».
Knuth was awarded the 1974 Turing Award "for his major contributions to the analysis of algorithms [ ], and in particular for his contributions to the 'art of computer programming' through his well known books in a continuous series by this title." American Scientist has included this work among "100 or so Books that shaped a Century of Science", referring to the twentieth century,. Covers of the third edition of Volume 1 quote Bill Gates as saying, "If you think you're a really good programmer read (Knuth's) Art of Computer Programming You should definitely send me a résumé if you can read the whole thing." The New York Times referred to it as "the profession's defining treatise".
Фасциклы
Том 4, "Фасциклы 0–4" были пересмотрены и опубликованы как том 4А. Том 4, Фасцикл 0: Введение в комбинаторные алгоритмы и булевые функции. (Addison Wesley Professional, 2008 04 28) vi+240pp, Errata: (2011 01 01). Том 4, Фасцикл 1: Битовые трюки и методы; Диаграммы бинарных решений. (Addison Wesley Professional, 2009 03 27) viii+260pp, Errata: (2011 01 01). Том 4, Фасцикл 2: Создание всех кортежей и перестановок. (Addison Wesley, 2005 02 14) v+127pp, Errata: (2011 01 01). Том 4, Фасцикл 3: Создание всех комбинаций и разбиений. (Addison Wesley, 2005 07 26) vi+150pp, Errata: (2011 01 01). Том 4, Фасцикл 4: Генерирование всех деревьев; История комбинированного генерирования. (Addison Wesley, 2006 02 06) vi+120pp, Errata: (2011 01 01). Том 4, "Фасциклы 5–6" были пересмотрены и опубликованы как том 4B. Том 4, Фасцикл 5: Математические основы (повторное рассмотрение); Метод обратного хода; Танцующие связи. (Addison Wesley, 2019 11 22) xiii+382pp, Errata: (2020 03 27) Том 4, Фасцикл 6: Выполнимость. (Addison Wesley, 2015 12 08) xiii+310pp, Errata: (2020 03 26)
Volume 4, Fascicles 0–4 were revised and published as Volume 4A. Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. (Addison Wesley Professional, 2008 04 28) vi+240pp, Errata: (2011 01 01). Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams. (Addison Wesley Professional, 2009 03 27) viii+260pp, Errata: (2011 01 01). Volume 4, Fascicle 2: Generating All Tuples and Permutations. (Addison Wesley, 2005 02 14) v+127pp, Errata: (2011 01 01). Volume 4, Fascicle 3: Generating All Combinations and Partitions. (Addison Wesley, 2005 07 26) vi+150pp, Errata: (2011 01 01). Volume 4, Fascicle 4: Generating All Trees; History of Combinatorial Generation. (Addison Wesley, 2006 02 06) vi+120pp, Errata: (2011 01 01). Volume 4, Fascicles 5–6 were revised and published as Volume 4B. Volume 4, Fascicle 5: Mathematical Preliminaries Redux; Backtracking; Dancing Links. (Addison Wesley, 2019 11 22) xiii+382pp, Errata: (2020 03 27)
Volume 4, Fascicle 6: Satisfiability. (Addison Wesley, 2015 12 08) xiii+310pp, Errata: (2020 03 26)