Введение в анализ алгоритмов

Содержание книги "Введение в анализ алгоритмов "

Предисловие
Глава 1. Предварительные условия
1.1. Что такое правильность?
1.2. Алгоритмы ранжирования
1.3. Ответы к избранным задачам
1.4. Примечания
Глава 2. Жадный алгоритм
2.1. Остовные деревья минимальной стоимости
2.2. Задания с предельными сроками и прибылями
2.3. Дальнейшие примеры и задачи
2.4. Ответы к избранным задачам
2.5. Примечания
Глава 3. Разделяй и властвуй
3.1. Сортировка слиянием
3.2. Умножение двоичных чисел
3.3. Алгоритм Савича
3.4. Дальнейшие примеры и задачи
3.5. Ответы к избранным задачам
3.6. Примечания
Глава 4. Динамическое программирование
4.1. Задача о наибольшей монотонной подпоследовательности
4.2. Задача кратчайшего пути для всех пар
4.3. Простая задача о рюкзаке
4.4. Задача выбора мероприятий
4.5. Задания с указанием предельных сроков, длительностей и прибылей
4.6. Дальнейшие примеры и задачи
4.7. Ответы к избранным задачам
4.8. Примечания
Глава 5. Онлайновые алгоритмы
5.1. Задача доступа к списку
5.2. Замещение страниц
5.3. Ответы к избранным задачам
5.4. Примечания
Глава 6. Рандомизированные алгоритмы
6.1. Идеальное паросочетание
6.2. Сопоставление с образцом
6.3. Проверка простоты
6.4. Шифрование с публичным ключом
6.5. Дальнейшие задачи
6.6. Ответы к избранным задачам
6.7. Примечания
Глава 7. Алгоритмы в линейной алгебре
7.1. Введение
7.2. Гауссово исключение
7.3. Алгоритм Грама-Шмидта
7.4. Гауссова редукция решетки
7.5. Вычисление характеристического многочлена
7.6. Ответы к избранным задачам
7.7. Примечания
Глава 8. Вычислительные основы
8.1. Введение
8.2. Алфавиты, строки и язык
8.3. Регулярные языки
8.4. Контекстно-свободные языки
8.5. Машины Тьюринга
8.6. Ответы к избранным задачам
8.7. Примечания
Глава 9. Математическая основа
9.1. Индукция и инвариантность
9.2. Теория чисел
9.3. Отношения
9.4. Логика
9.5. Ответы к избранным задачам
9.6. Примечания
Библиография
Предметный указатель