Искусство компьютерного программирования
-
История создания
- Дональд Кнут начал работу над «Искусством компьютерного программирования» в 1962 году.
- Изначально планировалось семь томов, но первые три были опубликованы в 1968-1973 годах.
- Работа над четвертым томом началась в 1973 году, но была приостановлена в 1977 году.
- Окончательная версия тома 4А была написана в 2001 году, а первая часть тома 4 вышла в 2005 году.
-
Структура и содержание
- Тома 1-5 охватывают основные алгоритмы программирования для последовательных машин.
- Том 4 включает разделы 0-4, 6, 5 и 7.
- Том 4B включает материалы из глав 5 и 6.
- Том 4C запланирован, но пока не опубликован.
-
Особенности и инновации
- Кнут использовал язык ассемблера MIXAL для оценки скорости алгоритмов и использования памяти.
- В книге представлены различные сложности упражнений, включая числовую оценку.
- Кнут предложил вознаграждение за обнаружение ошибок, что способствовало безупречности работы.
-
Признание и влияние
- В 1974 году Кнут получил премию Тьюринга за вклад в анализ алгоритмов.
- Книга включена в список «Около 100 книг, сформировавших столетие науки».
- Билл Гейтс назвал книгу «трактатом, определяющим профессию».
-
Точность арифметики с плавающей запятой
- Вычисления с двойной точностью
- Распределение чисел с плавающей запятой
-
Классические алгоритмы
- Модульная арифметика
- Как Быстро Мы Можем Размножаться?
-
Преобразование по основанию
- Дроби
- Наибольший общий делитель
- Анализ алгоритма Евклида
- Разложение на простые числа
-
Деление многочленов
- Разложение многочленов на множители
- Оценка степеней (возведение в степень по цепочке сложения)
- Вычисление многочленов
-
Манипулирование степенными рядами
- Том 3 – Сортировка и поиск
- Инверсии
- Перестановки в мультимножестве
- Бежит
- Таблицы и инволюции
- Сортировка по вставке
- Сортировка путем обмена
- Сортировка по выборке
- Сортировка путем слияния
- Сортировка по распределению
- Сортировка по минимальному сравнению
- Слияние с минимальным сравнением
- Выбор для минимального сравнения
- Сети для сортировки
- Многоходовое объединение и выбор замены
- Многофазное слияние
- Каскадное слияние
- Чтение ленты в обратном направлении
- Колеблющийся тип
- Практические рекомендации по объединению магнитных лент
- Внешняя сортировка по основанию
- Сортировка с использованием двух лент
- Диски и барабаны
-
Последовательный поиск
- Поиск в упорядоченной таблице
- Поиск по бинарному дереву
- Сбалансированные деревья
- Многоходовые деревья
- Цифровой поиск
- Хеширование
- Поиск по вторичным ключам
-
Комбинаторные алгоритмы, часть 1
- Логические основы
- Логическая оценка
- Побитовые приемы и техники
- Бинарные диаграммы принятия решений
- Генерация всех n-кортежей
- Генерирование всех перестановок
- Генерирование всех комбинаций
- Генерирование всех целочисленных разделов
- Создание всех заданных разделов
- Генерирование всех деревьев
- История и дополнительные ссылки
-
Комбинаторные алгоритмы, часть 2
- Танцевальные ссылки
- Выполнимость
- Удовлетворение ограничений
- Гамильтоновы пути и циклы
- Группировки
- Обложки
- Квадраты
- Попурри из головоломок
- Оценка затрат на обратный путь
- Генерация неэквивалентных шаблонов
- Кратчайшие пути
- Алгоритмы поиска объединений
- Поиск в глубину
- Связность вершин и ребер
- Специальные классы графов
- Расширяющие графики
- Случайные графики
- Двустороннее сопоставление
- Проблема присвоения
- Сетевые потоки
- Оптимальные поддеревья
- Оптимальное соответствие
- Оптимальные заказы
- Структуры независимости
- Эффективные матроидные алгоритмы
- Дискретное динамическое программирование
- Методы ветвления и привязки
- Геркулесовы задачи
- Близкая к оптимизации
-
Рекурсия
- Глава 8 – Рекурсия
-
Синтаксические алгоритмы
- Глава 9 – Лексическое сканирование
- Глава 10 – Методы синтаксического анализа
-
Теория контекстно-свободных языков
- Глава 11 – Математическая лингвистика
-
Методы компиляции
- Глава 12 – Перевод на язык программирования
-
Издания на английском языке
- Текущие выпуски
- Предыдущие издания
- Брошюры
- Предварительные пакеты
-
Смотрите также
- Введение в алгоритмы
- Рекомендации
- Записи
- Цитаты
- Источники
- Внешние ссылки