ПРЕДИСЛОВИЕ К РУССКОМУ ПЕРЕВОДУ
ПРЕДИСЛОВИЕ

1. МОДЕЛИ ВЫЧИСЛЕНИЙ

1.1. Алгоритмы и их сложности
1.2. Машины с произвольным доступом к памяти
1.3. Вычислительная сложность РАМ-программ
1.4. Модель с хранимой программой
1.5. Модификация РАМ
1.6. Простейшая модель вычислений: машина Тьюринга
1.7. Связь машин Тьюринга и РАМ
1.8. Язык высокого уровня — Упрощенный Алгол
Упражнения
Замечания по литературе

2.1. Структуры данных: списки, очереди истеки
2.2. Представления множеств
2.3. Графы
2.4. Деревья
2.5. Рекурсия
2.6. Разделяй и властвуй
2.7. Балансировка
2.8. Динамическое программирование
2.9. Эпилог
Упражнения
Замечания по литературе

3.1. Задача сортировки
3.2. Цифровая сортировка
3.3. Сортировка с помощью сравнений
3.4. Сортдеревом — упорядочение с помощью O(n log n) сравнений
3.5. Быстрсорт — упорядочение за среднее время O(n log n)
3.6. Порядковые статистики
3.7. Среднее время для порядковых статистик
Упражнения
Замечания по литературе

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.1. Остовное дерево наименьшей стоимости
5.2. Метод поиска в глубину
5.3. Двусвязность
5.4. Поиск в глубину в ориентированном графе
5.5. Сильная связность
5.6. Задачи нахождения путей
5.7. Алгоритм транзитивного замыкания
5.8. Алгоритм нахождения кратчайшего пути
5.9. Задачи о путях и умножение матриц
5.10. Задачи с одним источником
5.11. Доминаторы в ориентированных ациклических графах: комбинирование понятий
Упражнения
Замечания по литературе

6.1. Основные понятия
6.2. Алгоритм Штрассена для умножения матриц
6.3. Обращение матриц
6.4. НВП-разложение матрицы
6.5. Приложения НВП-разложения
6.6. Умножение булевых матриц
Упражнения
Замечания по литературе

7.1. Дискретное преобразование Фурье и обратное к нему
7.2. Алгоритм быстрого преобразования Фурье
7.3. БПФ при использовании битовых операций
7.4. Произведение полиномов
7.5. Алгоритм Шёнхаге—Штрассена для умножения целых чисел
Упражнения
Замечания по литературе

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.1. Конечные автоматы и регулярные выражения
9.2. Распознавание образов, задаваемых регулярными выражениями
9.3. Распознавание подцепочек
9.4. Двусторонний детерминированный магазинный автомат
9.5. Позиционные деревья и идентификаторы позиций
Упражнения
Замечания по литературе

10.1. Недетерминированные машины Тьюринга
10.2. Классы P и NP
10.3. Языки и задачи
10.4. NР-полнота задачи выполнимости
10.5. Еще несколько NP-полных задач
10.6. Задачи с полиномиально ограниченной памятью
Упражнения
Замечания по литературе

11.1. Иерархии по сложности
11.2. Иерархия по емкостной сложности для детерминированных машин Тьюринга
11.3. Задача, требующая экспоненциальных времени и памяти
11.4. Неэлементарная задача
Упражнения
Замечания по литературе

12.1. Поля
12.2. Еще раз о неветвящихся программах
12.3. Матричная формулировка задач
12.4. Нижняя граница для числа умножений, связанная с рангом по строкам
12.5. Нижняя граница для числа умножений, связанная с рангом по столбцам
12.6. Граница для числа умножений, связанная с рассмотрением строк и столбцов
12.7. Предварительная обработка
Упражнения
Замечания по литературе