Анализ алгоритмов. Активный обучающий подход

Предисловие редактора перевода
Предисловие
Педагогические принципы
Алгоритмы
Изменения, внесенные во второе издание
Планирование курса
Благодарности
Глава 1
Основы анализа алгоритмов
Необходимые предварительные знания
Цели
Советы по изучению
1.1. Что такое анализ?
1.1.1. Классы входных данных
1.1.2. Сложность по памяти
1.1.3. Упражнения
1.2. Что подсчитывать и что учитывать
1.2.1. Классы входных данных
1.2.2. Упражнения
1.3. Необходимые математические сведения
1.3.1. Логарифмы
1.3.2. Бинарные деревья
1.3.3. Вероятности
1.3.4. Формулы суммирования
1.3.5. Упражнения
1.4. Скорости роста
1.4.1. Классификация скоростей роста
1.4.2. Упражнения
1.5. Метод турниров
1.5.1. Нижние границы
1.5.2. Упражнения
1.6. Анализ программ
Глава 2
Рекурсивные алгоритмы
Необходимые предварительные знания
Цели
Советы по изучению
2.1. Анализ рекурсивных алгоритмов
2.1.1. Упражнения
2.2. Рекуррентные соотношения
2.2.1. Аппроксимация порядка роста
рекуррентных соотношений
2.2.2. Упражнения
2.3. Ближайшая пара
2.3.1. Упражнения
2.4. Выпуклая оболочка
2.4.1. Упражнения
2.5. Генерирование перестановок
2.5.1. Упражнения
2.6. Рекурсии и стеки
2.7. Упражнения по программированию
Глава 3
Алгоритмы поиска и выборки
Необходимые предварительные знания
Цели
Советы по изучению
3.1. Последовательный поиск
3.1.1. Анализ наихудшего случая
3.1.2. Анализ среднего случая
3.1.3. Упражнения
3.2. Двоичный поиск
3.2.1. Анализ наихудшего случая
3.2.2. Анализ среднего случая
3.2.3. Упражнения
3.3. Выборка
3.3.1. Упражнения
3.4. Упражнение по программированию
Глава 4
Алгоритмы сортировки
Необходимые предварительные знания
Цели
Советы по изучению
4.1. Сортировка вставками
4.1.1. Анализ наихудшего случая
4.1.2. Анализ среднего случая
4.1.3. Упражнения
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. Корневая сортировка
4.4.1. Анализ
4.4.2. Упражнения
4.5. Пирамидальная сортировка
4.5.1. Анализ наихудшего случая
4.5.2. Анализ среднего случая
4.5.3. Упражнения
4.6. Сортировка слиянием
4.6.1. Анализ алгоритма McrgcLists
4.6.2. Анализ алгоритма McrgcSort
4.6.3. Упражнения
4.7. Быстрая сортировка
4.7.1. Анализ наихудшего случая
4.7.2. Анализ среднего случая
4.7.3. Упражнения
4.8. Внешняя многофазная сортировка
слиянием
4.8.1. Число сравнений при построении отрезков
4.8.2. Число сравнений при слиянии отрезков
4.8.3. Число операций чтения блоков
4.8.4. Упражнения
4.9. Дополнительные упражнения
4.10. Упражнения по программированию
Глава 5
Численные алгоритмы
Необходимые предварительные знания
Цели
Советы по изучению
5.1. Вычисление значений многочленов
5.1.1. Схема Горнера
5.1.2. Предварительная обработка
коэффициентов
5.1.3. Упражнения
5.2. Умножение матриц
5.2.1. Умножение матриц по Винограду
5.2.2. Умножение матриц по Штраеесну
5.2.3. Упражнения
5.3. Решение линейных уравнений
5.3.1. Метод Жордана Гаусса
5.3.2. Упражнения
Глава 6
Алгоритмы формальных языков
Необходимые предварительные знания
Цели
Советы по изучению
6.1. Основы формального языка
6.1.1. Лексикографический порядок
6.1.2. Классификация языков
6.1.3. Упражнения
6.2. Конечные автоматы
6.2.1. Регулярные языки
6.2.2. Регулярные выражения
6.2.3. Регулярные грамматики
6.2.4. Детерминированные и
недетерминированные конечные
автоматы
6.2.5. Конвертирование детерминированного
конечного автомата в программу
6.2.6. Упражнения
6.3. Проектирование конечных автоматов
6.3.1. Ограничения возможностей конечных
автоматов
6.3.2. Проектирование конечных автоматов
6.3.3. Проектирование регулярной грамматики
6.3.4. Упражнения
6.4. Эквивалентность и пределы
возможностей конечных автоматов
6.4.1. Возможности конечных автоматов
6.4.2. Упражнения
6.5. Магазинные автоматы
6.5.1. Проектирование детерминированных
магазинных автоматов
6.5.2. Детерминированные контекстно-
свободные языки
6.5.3. Недетерминированные магазинные
автоматы
6.5.4. Упражнения
6.6. Контекстно-свободные грамматики
6.6.1. Возможности контекстно-свободной
грамматики
6.6.2. Проектирование контекстно-свободной
грамматики
6.6.3. Преобразование грамматики
6.6.4. Нормальная форма Грсйбаха
6.6.5. Конвертирование контекстно-свободной
грамматики
в магазинный автомат
6.6.6. Упражнения
6.7. Пределы возможностей магазинных
автоматов
6.7.1. Упражнения
6.8. Компиляция языков программирования
6.8.1. Упражнения
Глава 7
Алгоритмы сравнения с образцом
Необходимые предварительные знания
Цели
Советы по изучению
7.1. Сравнение строк
7.1.1. Конечные автоматы
7.1.2. Алгоритм Кнута Морриса Пратта
7.1.3. Упражнения
7.2. Приблизительное сравнение строк
7.2.1. Анализ
7.2.2. Упражнения
7.3. Упражнения по программированию
Глава 8
Алгоритмы на графах
Необходимые предварительные знания
Цели
Советы по изучению
8.1. Основные понятия теории графов
8.1.1. Терминология
8.1.2. Упражнения
8.2. Структуры данных для представления
графов
8.2.1. Матрица смежности
8.2.2. Список смежности
8.2.3. Упражнения
8.3. Алгоритмы обхода в глубину и по уровням
8.3.1. Обход в глубину
8.3.2. Обход по уровням
8.3.3. Анализ алгоритмов обхода
8.3.4. Упражнения
8.4. Алгоритм поиска минимального остовного
дерева
8.4.1. Алгоритм Дейкстры Прима
8.4.2. Алгоритм Круекала
8.4.3. Упражнения
8.5. Алгоритм поиска кратчайшего пути
8.5.1. Алгоритм Дейкстры
8.5.2. Упражнения
8.6. Алгоритм определения компонент
двусвязности
8.6.1. Упражнения
8.7. Разбиения множеств
8.8. Упражнения по программированию
Глава 9
Параллельные алгоритмы
Необходимые предварительные знания
Цели
Советы по изучению
9.1. Введение в параллелизм
9.1.1. Категории компьютерных систем
9.1.2. Параллельные архитектуры
9.1.3. Принципы анализа параллельных
алгоритмов
9.1.4. Упражнения
9.2. Модель PRAM
9.2.1. Упражнения
9.3. Простые параллельные операции
9.3.1. Распределение данных в модели CREW
PRAM
9.3.2. Распределение данных в модели EREW
PRAM
9.3.3. Поиск максимального элемента списка
9.3.4. Упражнения
9.4. Параллельный поиск
9.4.1. Упражнения
9.5. Параллельная сортировка
9.5.1. Сортировка на линейных сетях
9.5.2. Четно-нечетная сортировка
перестановками
9.5.3. Другие параллельные сортировки
9.5.4. Упражнения
9.6. Параллельные численные алгоритмы
9.6.1. Умножение матриц в параллельных сетях
9.6.2. Умножение матриц в модели CRCW PRAM
9.6.3. Решение систем линейных уравнений
алгоритмом SIMD
9.6.4. Упражнения
9.7. Параллельные алгоритмы на графах
9.7.1. Параллельный алгоритм поиска
кратчайшего пути
9.7.2. Параллельный алгоритм поиска
минимального остовно-
го дерева
9.7.3. Упражнения
Глава 10
Вычислимое и невычислимое
Необходимые предварительные знания
Цели
Советы по изучению
10.1. Машина Тьюринга
10.1.1. Машина Тьюринга как акцептор языка
10.1.2. Машина Тьюринга как вычислитель
функций
10.1.3. Проектирование машин Тьюринга
10.1.4. Упражнения
10.2. Тезис Чёрча Тьюринга
10.3. Разновидности машины Тьюринга
10.3.1. Машина Тьюринга с бесконечной в обе
стороны лентой
10.3.2. Машины Тьюринга с несколькими лентами
10.3.3. Двумерные машины Тьюринга
10.3.4. Недетерминированные машины Тьюринга
10.3.5. Универсальная машина Тьюринга
10.3.6. Упражнения
10.4. Возможности машины Тьюринга
10.4.1. Языки, не относящиеся к рекурсивно
перечислимым
10.4.2. Проблема остановки
10.4.3. Упражнения
10.5. Что такое NP?
10.5.1. Сведение задачи к другой задаче
10.5.2. NP-полные задачи
10.6. Типичные NP задачи
10.6.1. Раскраска графа
10.6.2. Раскладка по ящикам
10.6.3. Упаковка рюкзака
10.6.4. Задача о суммах элементов подмножеств
10.6.5. Задача об истинности КНФ выражения
10.6.6. Задача планирования работ
10.6.7. Упражнения
10.7. Какие задачи относятся к классу NP?
10.7.1. Выполнено ли равенство P = NP?
10.7.2. Упражнения
10.8. Проверка возможных решений
10.8.1. Задача о планировании работ
10.8.2. Раскраска графа
10.8.3. Упражнения
Глава 11
Другие алгоритмические инструменты
Необходимые предварительные знания
Цели
Советы по изучению
11.1. Жадные приближенные алгоритмы
11.1.1. Приближения в задаче о коммивояжере
11.1.2. Приближения в задаче о раскладке по
ящикам
11.1.3. Приближения в задаче об упаковке
рюкзака
11.1.4. Приближения в задаче о сумме элементов
подмножества
11.1.5. Приближения в задаче о раскраске графа
11.1.6. Упражнения
11.2. Алгоритм с возвратом
11.2.1. Упражнения
11.3. Алгоритм ветвей и границ
11.3.1. Упражнения
11.4. Вероятностные алгоритмы
11.4.1. Численные вероятностные алгоритмы
11.4.2. Алгоритмы Монте-Карло
11.4.3. Алгоритмы Лас-Вегаса
11.4.4. Шервудские алгоритмы
11.4.5. Сравнение вероятностных алгоритмов
11.4.6. Упражнения
11.5. Динамическое программирование
11.5.1. Вычисление чисел Фибоначчи и
биномиальных коэффициентов
11.5.2. Динамическое умножение матриц
11.5.3. Алгоритм Флойда нахождения
кратчайших расстояний
между всеми вершинами нагруженного
ориентированного графа
11.5.4. Динамический алгоритм, решающий
задачу об укладке
рюкзака
11.5.5. Упражнения
11.6. Упражнения по программированию
Приложение А
Таблица случайных чисел
Приложение Б
Генерирование псевдослучайных чисел
Б.1. Случайная последовательность в
произвольном интервале
Б. 2. Пример применения
Б.2.1. Первый способ
Б.2.2. Второй способ
Б.2.3. Третий способ
Приложение В
Ответы к упражнениям
Приложение Г
Литература
Предметный указатель