Искусство программирования -The Art of Computer Programming

Искусство программирования
ArtOfComputerProgramming.jpg
Искусство программирования, Том 1: Фундаментальные алгоритмы
Автор Дональд Кнут
Страна Соединенные Штаты
Язык английский
Жанр Научно-популярная
монография
Издатель Эддисон-Уэсли
Дата публикации
 1968– (книга еще не закончена)
Тип СМИ Печать (в твердом переплете )
ISBN 0-201-03801-3
519
Класс LC QA76.75

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

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

Ожидается, что пучки 5 и 6 составят первые две трети тома 4B. Кнут не объявил какую-либо предполагаемую дату выпуска тома 4B, хотя его метод, использованный для тома 4A, заключается в том, чтобы выпустить том в твердом переплете через некоторое время после выпуска содержащихся в нем брошюр в мягкой обложке. По ближайшим оценкам издателей, дата выпуска - май или июнь 2019 года, что оказалось неверным.

История

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

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

В январе 1962 года, когда он был аспирантом математического факультета Калифорнийского технологического института, Аддисон-Уэсли обратился к Кнуту с предложением написать книгу о проектировании компиляторов, и он предложил более широкие возможности. В тот же день он составил список из 12 названий глав. Летом 1962 года он работал над компилятором FORTRAN для UNIVAC. За это время он также разработал математический анализ линейного зондирования , который убедил его представить материал с количественным подходом. Получив докторскую степень в июне 1963 года, он начал работу над своей рукописью, первый черновой вариант которой он закончил в июне 1965 года.3000 рукописных страниц. Он предполагал, что около пяти рукописных страниц можно будет перевести в одну печатную страницу, но его издатель вместо этого сказал, что около 1+1 ⁄ 2 рукописных страниц переведены на одну печатную страницу. Это означало, что у него было примерно2000 печатных страниц материала, что почти соответствует размеру первых трех опубликованных томов. Издатель нервничал, принимая такой проект от аспиранта. На этом этапе Кнут получил поддержку от Ричарда С. Варги, научного консультанта издателя. Варга был в гостях у Ольги Таусски-Тодд и Джона Тодда в Калтехе . При восторженной поддержке Варги издатель принял расширенные планы Кнута. В расширенной версии книга будет опубликована в семи томах, в каждом из которых будет всего одна или две главы. Из-за увеличения объема главы 7, которая составляла менее 100 страниц рукописи 1965 года, в каждом томе. 4А стр. vi, план для тома 4 с тех пор был расширен за счет включения томов 4A, 4B, 4C, 4D и, возможно, других.

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

Предложение так называемого чека Кнута на сумму "один шестнадцатеричный доллар" (100 шестнадцатеричных центов с основанием 16 в десятичной системе - это 2,56 доллара США) за любые обнаруженные ошибки и исправление этих ошибок в последующих печатных изданиях способствовало высокому качеству работы. и по-прежнему авторитетный характер работы даже спустя долгое время после ее первой публикации. Еще одна характеристика объемов - различная сложность упражнений. Кнут даже имеет числовую шкалу сложности для оценки этих упражнений, варьирующуюся от 0 до 50, где 0 - тривиально, а 50 - открытый вопрос в современных исследованиях.

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

Эта серия книг любовно посвященный
к 650 Тип компьютера после установки в
Case технологическом институте ,
с которым я провел немало приятных вечеров.

Ассемблер в книге

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

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

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

Объемы

Завершенный

Планируется

Краткое содержание главы

Завершенный

Том 1 - Основные алгоритмы

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

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

  • Глава 5 - Сортировка
    • 5.1. Комбинаторные свойства перестановок.
      • 5.1.1. Инверсии
      • 5.1.2. Перестановки мультимножества
      • 5.1.3. Бежит
      • 5.1.4. Таблицы и инволюции
    • 5.2. Внутренняя сортировка
      • 5.2.1. Сортировка по вставке
      • 5.2.2. Сортировка по обмену
      • 5.2.3. Сортировка по выделению
      • 5.2.4. Сортировка по объединению
      • 5.2.5. Сортировка по распределению
    • 5.3. Оптимальная сортировка
      • 5.3.1. Сортировка по минимальному сравнению
      • 5.3.2. Слияние минимального сравнения
      • 5.3.3. Выбор минимального сравнения
      • 5.3.4. Сети для сортировки
    • 5.4. Внешняя сортировка
      • 5.4.1. Многостороннее объединение и выбор замены
      • 5.4.2. Полифазное слияние
      • 5.4.3. Каскадное слияние
      • 5.4.4. Чтение ленты в обратном направлении
      • 5.4.5. Осциллирующая сортировка
      • 5.4.6. Практические соображения по объединению лент
      • 5.4.7. Внешняя сортировка по основанию
      • 5.4.8. Двухленточная сортировка
      • 5.4.9. Диски и барабаны
    • 5.5. Резюме, история и библиография
  • Глава 6 - Поиск
    • 6.1. Последовательный поиск
    • 6.2. Поиск по сравнению ключей
      • 6.2.1. Поиск в упорядоченной таблице
      • 6.2.2. Поиск двоичного дерева
      • 6.2.3. Сбалансированные деревья
      • 6.2.4. Многонаправленные деревья
    • 6.3. Цифровой поиск
    • 6.4. Хеширование
    • 6.5. Получение вторичных ключей

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

Планируется

Том 4B, 4C, 4D - Комбинаторные алгоритмы

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

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

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

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

Текущие редакции

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

  • Искусство программирования, Коробка Тома 1-4А . Третье издание (Ридинг, Массачусетс: Аддисон-Уэсли, 2011 г.), 3168 стр. ISBN  978-0-321-75104-1 , 0-321-75104-3
    • Том 1: Основные алгоритмы . Третье издание (Reading, Massachusetts: Addison-Wesley, 1997), xx + 650pp. ISBN  978-0-201-89683-1 , 0-201-89683-4 . Исправления: [1] (2011-01-08), [2] (2020-03-26, 27-е издание ). Приложение: [3] (2011).
    • Том 2: получисловые алгоритмы . Третье издание (Reading, Massachusetts: Addison-Wesley, 1997), xiv + 762pp. ISBN  978-0-201-89684-8 , 0-201-89684-2 . Исправления: [4] (2011-01-08), [5] (2020-03-26, 26-е издание). Приложение: [6] (2011).
    • Том 3: Сортировка и поиск . Второе издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1998 г.), xiv + 780 стр. + Расклад. ISBN  978-0-201-89685-5 , 0-201-89685-0 . Исправления: [7] (2011-01-08), [8] (2020-03-26, 27-е издание). Приложение: [9] (2011).
    • Том 4A: Комбинаторные алгоритмы, часть 1 . Первое издание (Ридинг, Массачусетс: Аддисон-Уэсли, 2011 г.), xv + 883pp. ISBN  978-0-201-03804-0 , 0-201-03804-8 . Исправление: [10] (2020-03-26,? Печать).
  • Том 1, выпуск 1: MMIX - RISC-компьютер нового тысячелетия . (Аддисон-Уэсли, 2005-02-14) ISBN  0-201-85392-2 . Исправление: [11] (2020-03-16) (будет в четвертом издании тома 1)
  • Том 4, Часть 5: Предварительные математические упражнения Redux; Возврат; Танцы Ссылки . (Аддисон-Уэсли, 2019-11-22) xiii + 382pp, ISBN  978-0-13-467179-6 . Исправление: [12] (2020-03-27) (станет частью тома 4B)
  • Том 4, Часть 6: Удовлетворение . (Аддисон-Уэсли, 2015-12-08) xiii + 310pp, ISBN  978-0-13-439760-3 . Исправление: [13] (2020-03-26) (станет частью тома 4B)

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

Полные тома

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

  • Том 1: Основные алгоритмы . Первое издание, 1968 г., xxi + 634pp, ISBN  0-201-03801-3 .
  • Том 2: получисловые алгоритмы . Первое издание, 1969 г., xi + 624pp, ISBN  0-201-03802-1 .
  • Том 3: Сортировка и поиск . Первое издание, 1973 г., xi + 723pp + раскладушка, ISBN  0-201-03803-X . Исправление: [14] .
  • Том 1: Основные алгоритмы . Второе издание, 1973 г., xxi + 634pp, ISBN  0-201-03809-9 . Исправление: [15] .
  • Том 2: получисловые алгоритмы . Второе издание, 1981 г., xiii + 688pp, ISBN  0-201-03822-6 . Исправление: [16] .
  • Искусство программирования, Коробка Тома 1-3 . Второе издание (чтение, Массачусетс: Addison-Wesley, 1998), стр. ISBN  978-0-201-48541-7 , 0-201-48541-9

Пучки

Том 4 «сек пучки 0-4 были пересмотрены и опубликованы в томе 4A:

  • Том 4, Часть 0: Введение в комбинаторные алгоритмы и булевы функции . (Addison-Wesley Professional, 2008-04-28) vi + 240pp, ISBN  0-321-53496-4 . Исправления: [17] (01.01.2011).
  • Том 4, Часть 1: Побитовые уловки и методы; Диаграммы двоичных решений . (Addison-Wesley Professional, 2009-03-27) viii + 260pp, ISBN  0-321-58050-8 . Исправление: [18] (01.01.2011).
  • Том 4, Часть 2: Генерация всех кортежей и перестановок . (Аддисон-Уэсли, 2005-02-14) v + 127pp, ISBN  0-201-85393-0 . Исправление: [19] (01.01.2011).
  • Том 4, Часть 3: Создание всех комбинаций и разделов . (Аддисон-Уэсли, 2005-07-26) vi + 150pp, ISBN  0-201-85394-9 . Исправление: [20] (01.01.2011).
  • Том 4, Часть 4: Создание всех деревьев; История комбинаторной генерации . (Аддисон-Уэсли, 06.02.2006) vi + 120pp, ISBN  0-321-33570-8 . Исправление: [21] (01.01.2011).

Том 4 «s пучки 5-6 станет частью тома 4B:

  • Том 4, Часть 5: Предварительные математические упражнения Redux; Возврат; Танцы Ссылки . (Аддисон-Уэсли, 2019-11-22) xiii + 382pp, ISBN  978-0-13-467179-6 . Исправление: [22] (27.03.2020)
  • Том 4, Часть 6: Удовлетворение . (Аддисон-Уэсли, 2015-12-08) xiii + 310pp, ISBN  978-0-13-439760-3 . Исправление: [23] (26.03.2020)

Предварительные пучки

Том 4 «с предварительно пучках 5А, 5В и 5С были пересмотрены и опубликованы в виде брошюры 5.

Том 4 «с предварительно пучками 6A был пересмотрен и опубликован в пучках 6.

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

использованная литература

Примечания

Цитаты

Источники

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