Искусство программирования -The Art of Computer Programming
Автор | Дональд Кнут |
---|---|
Страна | Соединенные Штаты |
Язык | английский |
Жанр |
Научно-популярная монография |
Издатель | Эддисон-Уэсли |
Дата публикации |
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 года, что оказалось неверным.
История
Выиграв стипендию 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 - Основные алгоритмы
- Глава 1 - Основные понятия
- Глава 2 - Информационные структуры
- Том 2 - Получисленные алгоритмы
- Глава 3 - Случайные числа
- Глава 4 - Арифметика
- Том 3 - Сортировка и поиск
- Глава 5 - Сортировка
- Глава 6 - Поиск
- Том 4A - Комбинаторные алгоритмы
- Глава 7 - Комбинаторный поиск (часть 1)
Планируется
- Том 4B ... - Комбинаторные алгоритмы (главы 7 и 8 выпущены в нескольких подтомах)
- Глава 7 - Комбинаторный поиск (продолжение)
- Глава 8 - Рекурсия
- Том 5 - Синтаксические алгоритмы
- Глава 9 - Лексическое сканирование (также включает поиск по строке и сжатие данных )
- Глава 10 - Методы синтаксического анализа
- Том 6 - Теория контекстно-свободных языков
- Том 7 - Compiler Techniques
Краткое содержание главы
Завершенный
Том 1 - Основные алгоритмы
- Глава 1 - Основные понятия
- 1.1. Алгоритмы
- 1.2. Математические предварительные сведения
- 1.2.1. Математическая индукция
- 1.2.2. Числа, степени и логарифмы
- 1.2.3. Суммы и продукты
- 1.2.4. Целочисленные функции и элементарная теория чисел
- 1.2.5. Перестановки и факториалы
- 1.2.6. Биномиальные коэффициенты
- 1.2.7. Гармонические числа
- 1.2.8. Числа Фибоначчи
- 1.2.9. Генерация функций
- 1.2.10. Анализ алгоритма
- 1.2.11. Асимптотические представления
- 1.2.11.1. О-нотация
- 1.2.11.2. Формула суммирования Эйлера
- 1.2.11.3. Некоторые асимптотические вычисления
- 1.3 MMIX ( MIX в твердом переплете, но обновлен в главе 1)
- 1.3.1. Описание MMIX
- 1.3.2. Язык ассемблера MMIX
- 1.3.3. Приложения к перестановкам
- 1.4. Некоторые фундаментальные методы программирования
- 1.4.1. Подпрограммы
- 1.4.2. Сопрограммы
- 1.4.3. Процедуры интерпретации
- 1.4.3.1. Симулятор MIX
- 1.4.3.2. Процедуры трассировки
- 1.4.4. Вход и выход
- 1.4.5. История и библиография
- Глава 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 - Случайные числа
- 3.1. Вступление
- 3.2. Генерация однородных случайных чисел
- 3.2.1. Линейный конгруэнтный метод
- 3.2.1.1. Выбор модуля
- 3.2.1.2. Выбор множителя
- 3.2.1.3. Сила
- 3.2.2. Другие методы
- 3.2.1. Линейный конгруэнтный метод
- 3.3. Статистические тесты
- 3.3.1. Общие процедуры тестирования для изучения случайных данных
- 3.3.2. Эмпирические тесты
- 3.3.3. Теоретические тесты
- 3.3.4. Спектральный тест
- 3.4. Другие типы случайных величин
- 3.4.1. Числовые распределения
- 3.4.2. Случайная выборка и перемешивание
- 3.5. Что такое случайная последовательность ?
- 3.6. Резюме
- Глава 4 - Арифметика
- 4.1. Позиционные системы счисления
- 4.2. Арифметика с
плавающей запятой
- 4.2.1. Расчеты с одинарной точностью
- 4.2.2. Точность арифметики с плавающей запятой
- 4.2.3. Расчеты с двойной точностью
- 4.2.4. Распределение чисел с плавающей запятой
- 4.3. Арифметика с множественной точностью
- 4.3.1. Классические алгоритмы
- 4.3.2. Модульная арифметика
- 4.3.3. Как быстро мы можем размножаться?
- 4.4. Преобразование Radix
- 4.5. Рациональная арифметика
- 4.5.1. Фракции
- 4.5.2. Наибольший общий делитель
- 4.5.3. Анализ алгоритма Евклида.
- 4.5.4. Факторинг в простые числа
- 4.6. Полиномиальная арифметика
- 4.6.1. Деление многочленов
- 4.6.2. Факторизация многочленов
- 4.6.3. Оценка способностей ( возведение в степень сложения-цепочки )
- 4.6.4. Оценка полиномов
- 4.7. Манипулирование степенными рядами
Том 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. Резюме, история и библиография
- 5.1. Комбинаторные свойства перестановок.
- Глава 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
- Глава 7 - Комбинаторный поиск
- 7.1. Нули и единицы
- 7.1.1. Логические основы
- 7.1.2. Логическая оценка
- 7.1.3. Побитовые приемы и методы
- 7.1.4. Диаграммы двоичных решений
- 7.2. Создание всех возможностей
- 7.2.1. Генерация базовых комбинаторных паттернов
- 7.2.1.1. Генерация всех n- кортежей
- 7.2.1.2. Генерация всех перестановок
- 7.2.1.3. Создание всех комбинаций
- 7.2.1.4. Создание всех разделов
- 7.2.1.5. Создание всех установленных разделов
- 7.2.1.6. Создание всех деревьев
- 7.2.1.7. История и другие ссылки
- 7.2.1. Генерация базовых комбинаторных паттернов
- 7.1. Нули и единицы
Планируется
Том 4B, 4C, 4D - Комбинаторные алгоритмы
- Глава 7 - Комбинаторный поиск (продолжение)
- 7.2. Создание всех возможностей (продолжение)
- 7.2.2. Программирование с возвратом (опубликовано в Fascicle 5)
- 7.2.2.1. Ссылки на танцы (опубликовано в Fascicle 5)
- 7.2.2.2. Удовлетворенность (опубликовано в Fascicle 6)
- 7.2.2.3. Удовлетворение ограничений
- 7.2.2.4. Гамильтоновы пути и циклы (онлайн-черновик в вводной части 8A)
- 7.2.2.5. Клики
- 7.2.2.6. Обложки ( Vertex cover , Set cover problem , Exact cover , Clique cover )
- 7.2.2.7. Квадраты
- 7.2.2.8. Попурри из головоломок (онлайн-проект в пре-главе 9B) (включает в себя идеальный цифровой инвариант )
- 7.2.2.9. Оценка затрат на возврат (глава 6 «Избранных статей по анализу алгоритмов» и брошюра 5, стр. 44–47, под заголовком «Оценка времени выполнения»)
- 7.2.3. Генерация неэквивалентных паттернов (включает обсуждение теоремы перечисления Полиа ) (см. «Методы отклонения изоморфов», гл. 4 «Классификационных алгоритмов для кодов и схем» Каски и Остергарда)
- 7.2.2. Программирование с возвратом (опубликовано в Fascicle 5)
- 7.3. Кратчайшие пути
- 7.4. Алгоритмы графа
- 7.4.1. Компоненты и обход
- 7.4.2. Специальные классы графов
- 7.4.3. Графики расширителей
- 7.4.4. Случайные графики
- 7.5. Графики и оптимизация
- 7.5.1. Двустороннее сопоставление (в том числе сопоставление максимальной мощности , проблема стабильного брака , брачные конюшни )
- 7.5.2. Проблема присвоения
- 7.5.3. Сетевые потоки
- 7.5.4. Оптимальные поддеревья
- 7.5.5. Оптимальное соответствие
- 7.5.6. Оптимальные заказы
- 7.6. Теория независимости
- 7.6.1. Структуры независимости
- 7.6.2. Эффективные алгоритмы матроидов
- 7.7. Дискретное динамическое программирование (см. Также метод трансфер-матрицы )
- 7.8. Методы ветвей и границ
- 7.9. Геракловы задачи (также известные как NP-трудные задачи)
- 7.10. Почти оптимизация
- 7.2. Создание всех возможностей (продолжение)
- Глава 8 - Рекурсия (глава 22 «Избранных статей по анализу алгоритмов»)
Том 5 - Синтаксические алгоритмы
- Глава 9 - Лексическое сканирование (включает также поиск по строке и сжатие данных)
- Глава 10 - Методы синтаксического анализа
Том 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.
Смотрите также
использованная литература
Примечания
Цитаты
Источники
- Слейтер, Роберт (1987). Портреты в кремнии . MIT Press . ISBN 0-262-19262-4.
- Шаша, Деннис ; Лазер, Кэти (1995). Из их разума: жизни и открытия 15 великих ученых-компьютерщиков . Коперник. ISBN 0-387-97992-1.
внешние ссылки
- Обзор тем (личная домашняя страница Кнута)
- Устное интервью истории с Дональдом Э. Кнутом в Институте Чарльза Бэббиджа , Университет Миннесоты, Миннеаполис. Кнут обсуждает патентование программного обеспечения, структурированное программирование , сотрудничество и разработку TeX . Устная история обсуждает написание искусства компьютерного программирования .
- Дональд Э. Кнут "Памяти Роберта Флойда" (о влиянии Боба Флойда )
- TAoCP и его влияние на компьютерные науки (Softpanorama)