Альфапедия

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

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

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

Кнут начал этот проект, первоначально задуманный как отдельная книга с двенадцатью главами, в 1962 году. Первые три тома того, что тогда ожидалось, будет семитомником, были издавался в 1968, 1969 и 1973 годах. Серьезно работа над томом 4 началась в 1973 году, но была приостановлена ​​в 1977 году из-за работы по набору текста. Написание последней копии тома 4A началось от руки в 2001 году, а первая пре-брошюра в сети, 2A, появилась позже в 2001 году. Первая опубликованная часть тома 4 появилась в мягкой обложке как Fascicle 2 в 2005 году. Том 4A в твердом переплете, объединяющий Том 4, Части 0–4, был опубликован в 2011 году. Том 4, Раздел 6 («Удовлетворенность») был выпущен в декабре 2015 года; Том 4, Fascicle 5 («Mathematical Preliminaries Redux; Backtracking; Dancing Links») был выпущен в ноябре 2019 года.

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

Содержание

  • 1 История
  • 2 Язык ассемблера в книге
  • 3 Критический ответ
  • 4 Тома
    • 4.1 Завершено
    • 4.2 Запланировано
  • 5 Краткое содержание главы
    • 5.1 Завершено
      • 5.1.1 Том 1 - Основные алгоритмы
      • 5.1.2 Том 2 - Получисленные алгоритмы
      • 5.1.3 Том 3 - Сортировка и поиск
      • 5.1.4 Том 4A - Комбинаторные алгоритмы, часть 1
    • 5.2 Планируемые
      • 5.2.1 Том 4B, 4C, 4D - Комбинаторные алгоритмы
      • 5.2.2 Том 5 - Синтаксис Алгоритмы
      • 5.2.3 Том 6 - Теория контекстно-свободных языков
      • 5.2.4 Том 7 - Методы компиляции
  • 6 английских изданий
    • 6.1 Текущие редакции
    • 6.2 Предыдущие редакции
      • 6.2.1 Полные тома
      • 6.2.2 Части
      • 6.2.3 Предварительные главы
  • 7 См. Также
  • 8 Ссылки
  • 9 Внешние ссылки

История

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

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

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

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

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

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

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

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

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

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

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

Тома

Завершено

  • Том 1 - Фундаментальные алгоритмы
  • Глава 1 - Основные понятия
  • Глава 2 - Информационные структуры
  • Том 2 - Получисленные алгоритмы
  • Глава 7 - Комбинаторный поиск (часть 1)

Планируемый

  • Том 4B... - Комбинаторные алгоритмы (главы 7 и 8 выпущены в нескольких подтомах)
  • Глава 7 - Комбинаторный поиск (продолжение)
  • Глава 8 - Рекурсия
  • Том 5 - Синтаксические алгоритмы (по состоянию на 2017 год, ожидается выпуск в 2025 году)

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

Завершено

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

  • Глава 1 - Основные понятия
  • Глава 2 - Информационные структуры
    • 2.1. Введение
    • 2.2. Линейные списки
      • 2.2.1. Стеки, очереди и дек
      • 2.2.2. Последовательное размещение
      • 2.2.3. Связанное размещение
      • 2.2.4. Циркулярные списки
      • 2.2.5. Двусвязные списки
      • 2.2.6. Массивы и ортогональные списки
    • 2.3. Деревья
      • 2.3.1. Обход двоичных деревьев
      • 2.3.2. Представление деревьев в виде двоичного дерева
      • 2.3.3. Другие изображения деревьев
      • 2.3.4. Основные математические свойства деревьев
        • 2.3.4.1. Бесплатные деревья
        • 2.3.4.2. Ориентированные деревья
        • 2.3.4.3. «Лемма о бесконечности»
        • 2.3.4.4. Перечисление деревьев
        • 2.3.4.5. Длина пути
        • 2.3.4.6. История и библиография
      • 2.3.5. Списки и сборка мусора
    • 2.4. Многосвязные структуры
    • 2.5. Динамическое распределение памяти
    • 2.6. История и библиография

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

  • Глава 3 - Случайные числа
  • Глава 4 - Арифметика

Том 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 - Синтаксические алгоритмы

по состоянию на 2017 год, ориентировочно для выпуска в 2025 году

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

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

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

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

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

  • Искусство компьютерного программирования, Тома 1–4A в штучной упаковке. Третье издание (Ридинг, Массачусетс: Addison-Wesley, 2011), 3168pp.. ISBN 978-0-321-75104-1, 0-321-75104-3
    • Том 1: Основные алгоритмы. Третий E dition (Reading, Massachusetts: Addison-Wesley, 1997), xx + 650 стр. ISBN 978-0-201-89683-1, 0-201-89683-4. Ошибки: [1] (2011-01-08), [2] (2020-03-26, 27-е печать ). Дополнение: [3pting (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 impression (2011).
    • Том 3: Сортировка и поиск. Второе издание (Ридинг, Массачусетс: Аддисон-Уэсли, 1998 г.), xiv + 780 стр. + Расклад. ISBN 978-0-201-89685-5, 0-201-89685-0. Исправления: [7] (2011-01-08), [8] (2020-03-26, 27-е издание). Дополнение: [9pting (2011).
    • Том 4A: Комбинаторные алгоритмы, часть 1. Первое издание (чтение, Массачусетс: Addison-Wesley, 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 + foldout, 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. Второе издание (Reading, Massachusetts: Addison-Wesley, 1998), стр. ISBN 978-0-201-48541-7, 0-201-48541 -9

Части

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

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

Главы 5–6 тома 4 станут частью тома 4B:

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

Пре-брошюры

пре-брошюры 5A, 5B и 5C тома 4 были пересмотрены и опубликовано в качестве главы 5.

Пре-брошюра 6А тома 4 была пересмотрена и опубликована как глава 6.

См. Также

Ссылки

Примечания

Цитаты

Источники

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

Последняя правка сделана 2021-06-10 04:55:52
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте