А.Ахо, Дж.Хопкрофт, Дж.Ульман, 1979 (Rus)
Построение и анализ вычислительных алгоритмов
ОГЛАВЛЕНИЕ
1. МОДЕЛИ ВЫЧИСЛЕНИЙ
1.1 Алгоритмы и их сложность
1.2 Машины с произвольным доступом к памяти
1.3 Вычислительная сложность РАМ-программ
1.4 Модель с хранимой программой
1.5 Модификация РАМ
1.6 Простейшая модель вычислений: машина Тьюринга
1.7 Связь машин Тьюринга и РАМ
1.8 Язык высокого уровня - Упрощенный Алгол
Упражнения
Замечания по литературе
2. РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ
2.1 Структуры данных: списки, очереди и стеки
2.2 Представления множеств
2.3 Графы
2.4 Деревья
2.5 Рекурсия
2.6 Разделяй и властвуй
2.7 Балансировка
2.8 Динамическое программирование
2.9 Эпилог
Упражнения
Замечания по литературе
3. СОРТИРОВКА И ПОРЯДКОВЫЕ СТАТИСТИКИ
3.1 Задача сортировки
3.2 цифровая сортировка
3.3 Сортировка с помощью сравнений
3.4 Сортировка деревом - упорядочение с помощью O(N·LogN) сравнений
3.5 Быстрая сортировка - упорядочение за среднее время O(N·LogN)
3.6 Порядковые статистики
3.7 Среднее время для порядковых статистик
Упражнения
Замечания по литературе
4. СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ, КАСАЮЩИХСЯ РАБОТЫ С МНОЖЕСТВАМИ
4.1 Основные операции над множествами
4.2 Метод расстановки
4.3 Двоичный поиск
4.4 Деревья двоичного поиска
4.5 Оптимальное дерево двоичного поиска
4.6 Простой алгоритм для нахождения объединения непересекающихся множеств
4.7 Древовидные структуры для задач ОБЪЕДИНИТЬ - НАЙТИ
4.8 Приложения и обобщения алгоритма ОБЪЕДИНИТЬ - НАЙТИ
4.9 Схемы сбалансированных деревьев
4.10 Словари и очереди с приоритетами
4.11 Сливаемые деревья
4.12 Сцепляемые очереди
4.13 Разбиение
4.14 Резюме
Упражнения
Замечания по литературе
5. АЛГОРИТМЫ НА ГРАФАХ
5.1 Остовное дерево наименьшей стоимости
5.2 Метод поиска в глубину
5.3 Двусвязность
5.4 Поиск в глубину в ориентированном графе
5.5 Сильная связность
5.6 Задача нахождения путей
5.7 Алгоритм транзитивного замыкания
5.8 Алгоритм нахождения кратчайшего пути
5.9 Задача о путях и умножение матриц
5.10 Задача с одним источником
5.11 Доминаторы в ориентированных ациклических графах: комбинирование понятий
Упражнения
Замечания по литературе
6. УМНОЖЕНИЕ МАТРИЦ И СВЯЗАННЫЕ С НИМ ОПЕРАЦИИ
6.1 Основные понятия
6.2 Алгоритм Штрассена для умножения матриц
6.3 Обращение матриц
6.4 НВП-разложение матриц
6.5 Приложения НВП-разложения
6.6 Умножение булевых матриц
Умножение
Замечания по литературе
7. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ
7.1 Дискретное преобразование Фурье и обратное к нему
7.2 Алгоритм быстрого преобразования Фурье
7.3 БПФ при использовании битовых операций
7.4 Произведение полиномов
7.5 Алгоритм Шёнхаге-Штрассена для умножения целых чисел
Упражнения
Замечания по литературе
8. АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦЕЛЫМИ ЧИСЛАМИ И ПОЛИНОМАМИ
8.1 Аналогии между целыми числами и полиномами
8.2 Умножение и деление целых чисел
8.3 Умножение и деление полиномов
8.4 Модульная арифметика
8.5 Модульная арифметика полиномов т вычисление их значений
8.6 Применение китайской теоремы об остатках
8.7 Китайская теорема об остатках и интерполяция полиномов
8.8 Наибольшие общие делители и алгоритм Евклида
8.9 Асимптотически быстрый алгоритм нахождения НОД полиномов
8.10 НОД целых чисел
8.11 Еще раз о применении китайской теоремы об остатках
8.12 Разреженные полиномы
Упражнения
Замечания по литературе
9. АЛГОРИТМЫ ИДЕНТИФИКАЦИИ
9.1 Конечные автоматы и регулярные выражения
9.2 Распознавание образов, задаваемых регулярными выражениями
9.3 Распознавание подцепочек
9.4 Двусторонний детерминированный магазинный автомат
9.5 Позиционные деревья и идентификаторы позиций
Упражнения
Замечания по литературе
10. NP-ПОЛНЫЕ ЗАДАЧИ
10.1 Недетерминированные машины Тьюринга
10.2 Классы Р и NP
10.3 Языки и задачи
10.4 NP-полнгота задачи выполнимости
10.5 Еще несколько NP-полных задач
10.6 Задача с полиномиально ограниченной памятью
Упражнения
Замечания по литературе
11. НЕКОТОРЫЕ ДОКАЗУЕМЫЕ ТРУДНОРАЗРЕШИМЫЕ ЗАДАЧИ
11.1 Иерархии по сложности
11.2 Иерархия по емкостной сложности для детерминированных машин Тьюринга
11.3 Задача, требующая экспоненциальных времени и памяти
11.4 Неэлементарная задача
Упражнения
Замечания по литературе
12. НИЖНИЕ ОЦЕНКИ ЧИСЛА АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ
12.1 Поля
12.2 Еще раз о неветвящихся программах
12.3 Матричная формулировка задачи
12.4 Нижняя граница для числа умножений, связанная с рангом по строкам
12.5 Нижняя граница для числа умножений, связанная с рангом по столбцам
12.6 Граница для числа умножений, связанная с рассмотрением строк и столбцов
12.7 Предварительная обработка
Упражнения
Замечания по литературе
СПИСОК ЛИТЕРАТУРЫ
ГЛОССАРИЙ
ИМЕННОЙ УКАЗАТЕЛЬ
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ