Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов

М.: Мир, 1979. — 536 с.В монографии с единых позиций излагаются результаты теоретических и прикладных исследований по построению быстрых алгоритмов и доказательству их отсутствия. Рассмотрены задачи перебора, упорядочения массивов данных, умножения чисел, умножения матриц, обсуждаются алгоритмы на графах. Многие результаты ранее были рассеяны в труднодоступных источниках и в монографическом виде публикуются впервые.
Книга рассчитана на специалистов по современному программированию, разработчиков вычислительных систем и алгоритмов, она может быть использована как учебное пособие студентами и аспирантами, специализирующимися в области вычислительной математики.Предисловие к русскому переводу
ПредисловиеМодели вычислений
Алгоритмы и их сложности
Машины с произвольным доступом к памяти
Вычислительная сложность РАМ-программ
Модель с хранимой программой
Модификация РАМ
Простейшая модель вычислений: машина Тьюринга
Связь машин Тьюринга и РАМ
Язык высокого уровняóУпрощенный Алгол
Упражнения
Замечания по литературеРазработка эффективных алгоритмов
Структуры данных: списки, очереди и стеки
Представления множеств
Графы
Деревья
Рекурсия
Разделяй и властвуй
Балансировка
Динамическое программирование
Эпилог
Упражнения
Замечания по литературеСортировка и порядковые статистики
Задача сортировки
Цифровая сортировка
Сортировка с помощью сравнений
Сортдеревомóупорядочение с помощью O(n log n) сравнений 106
Быстрcopтóупорядочение за среднее время O(n log n)
Порядковые статистики
Среднее время для порядковых статистик
Упражнения
Замечания по литературеСтруктуры данных для задач, касающихся работы с множествами
Основные операции над множествами
Метод расстановки
Двоичный поиск
Деревья двоичного поиска
Оптимальные деревья двоичного поиска
Простой алгоритм для нахождения объединения непересекающихся множеств
Древовидные структуры для задачи ОБЪЕДИНИТЬóНАЙТИ
Приложения и обобщения алгоритма ОБЪЕДИНИТЬóНАЙТИ
Схемы сбалансированных деревьев
Словари и очереди с приоритетами
Сливаемые деревья
Сцепляемые очереди
Разбиение
Резюме
Упражнения
Замечания по литературеАлгоритмы на графах
Остовное дерево наименьшей стоимости
Метод поиска в глубину
Двусвязность
Поиск в глубину в ориентированном графе
Сильная связность
Задачи нахождения путей
Алгоритм транзитивного замыкания
Алгоритм нахождения кратчайшего пути
Задачи о путях и умножение матриц
Задачи с одним источником
Доминаторы в ориентированных ациклических графах: комбинирование понятий
Упражнения
Замечания по литературеУмножение матриц и связанные с ним операции
Основные понятия
Алгоритм Штрассена для умножения матриц
Обращение матриц
НВП-разложение матрицы
Приложения НВП-разложения
Умножение булевых матриц
Упражнения
Замечания по литературеБыстрое преобразование фурье и его приложения
Дискретное преобразование Фурье и обратное к нему
Алгоритм быстрого преобразования Фурье
БПФ при использовании битовых операций
Произведение полиномов
Алгоритм Шёнхаге ó Штрассена для умножения целых чисел
Упражнения
Замечания по литературеАрифметические операции над целыми числами и полиномами
Аналогии между целыми числами и полиномами
Умножение и деление целых чисел
Умножение и деление полиномов
Модульная арифметика
Модульная арифметика полиномов и вычисление их значений
Применение китайской теоремы об остатках
Китайская теорема об остатках и интерполяция полиномов
Наибольшие общие делителя и алгоритм Евклида
Асимптотически быстрый алгоритм нахождения НОД полиномов
НОД целых чисел
Еще раз о применении китайской теоремы об остатках
Разреженные полиномы
Упражнения
Замечания по литературеАлгоритмы идентификации
Конечные автоматы и регулярные выражения
Распознавание образов, задаваемых регулярными выражениями
Распознавание подцепочек
Двусторонний детерминированный магазинный автомат
Позиционные деревья и идентификаторы позиций
Упражнения
Замечания по литературеNP-полные задачи
Недетерминированные машины Тьюринга
Классы P и NP
Языки и задачи
NP-полнота задачи выполнимости
Еще несколько NP-полных задач
Задачи с полиномиально ограниченной памятью
Упражнения
Замечания по литературеНекоторые доказуемо трудно разрешимые задачи
Иерархии по сложности
Иерархия по емкостной сложности для детерминированных машин Тьюринга
Задача, требующая экспоненциальных времени и памяти
Неэлементарная задача
Упражнения
Замечания по литературеНижние оценки числа арифметических операций
Поля
Еще раз о неветвящихся программах
Матричная формулировка задач
Нижняя граница для числа умножений, связанная с рангом по строкам
Нижняя граница для числа умножений, связанная с рангом по столбцам
Граница для числа умножений, связанная с рассмотрением строк и столбцов
Предварительная обработка
Упражнения
Замечания по литературеСписок литературы
Глоссарии
Именной указатель
Предметный указатель