eng
Содержание
Предисловие
1.
Основы анализа алгоритмов
1.1.
Что такое анализ?
1.1.1.
Классы входных данных
1.1.2.
Сложность по памяти
1.1.3.
Упражнения
1.2.
Что подсчитывать и что учитывать
1.2.1.
Упражнения
1.3.
Необходимые математические сведения
1.3.1.
Логарифмы
1.3.2.
Бинарные деревья
1.3.3.
Вероятности
1.3.4.
Упражнения
1.4.
Скорости роста
1.4.1.
Классификация скоростей роста
1.4.2.
Упражнения
1.5.
Алгоритмы вида “разделяй и властвуй”
1.5.1.
Метод турниров
1.5.2.
Нижние границы
1.5.3.
Упражнения
1.6.
Рекуррентные соотношения
1.6.1.
Упражнения
1.7.
Анализ программ
2.
Алгоритмы поиска и выборки
2.1.
Последовательный поиск
2.1.1.
Анализ наихудшего случая
2.1.2.
Анализ среднего случая
2.1.3.
Упражнения
2.2.
Двоичный поиск
2.2.1.
Анализ наихудшего случая
2.2.2.
Анализ среднего случая
2.2.3.
Упражнения
2.3.
Выборка
2.3.1.
Упражнения
2.4.
Упражнение по программированию
3.
Алгоритмы сортировки
3.1.
Сортировка вставками
3.1.1.
Анализ наихудшего случая
3.1.2.
Анализ среднего случая
3.1.3.
Упражнения
3.2.
Пузырьковая сортировка
3.2.1.
Анализ наилучшего случая
3.2.2.
Анализ наихудшего случая
3.2.3.
Анализ среднего случая
3.2.4.
Упражнения
3.3.
Сортировка Шелла
3.3.1.
Анализ алгоритма
3.3.2.
Влияние шага на эффективность
3.3.3.
Упражнения
3.4.
Корневая сортировка
3.4.1.
Анализ
3.4.2.
Упражнения
3.5.
Пирамидальная сортировка
3.5.1.
Анализ наихудшего случая
3.5.2.
Анализ среднего случая
3.5.3.
Упражнения
3.6.
Сортировка слиянием
3.6.1.
Анализ алгоритма MergeLists
3.6.2.
Анализ алгоритма MergeSort
3.6.3.
Упражнения
3.7.
Быстрая сортировка
3.7.1.
Анализ наихудшего случая
3.7.2.
Анализ среднего случая
3.7.3.
Упражнения
3.8.
Внешняя многофазная сортировка слиянием
3.8.1.
Число сравнений при построении отрезков
3.8.2.
Число сравнений при слиянии отрезков
3.8.3.
Число операций чтения блоков
Упражнения
3.9.
Дополнительные упражнения
3.10.
Упражнения по программированию
4.
Численные алгоритмы
4.1.
Вычисление значений многочленов
4.1.1.
Схема Горнера
4.1.2.
Предварительная обработка коэффициентов
4.1.3.
Упражнения
4.2.
Умножение матриц
4.2.1.
Умножение матриц по Винограду
4.2.2.
Умножение матриц по Штрассену
4.2.3.
Упражнения
4.3.
Решение линейных уравнений
4.3.1.
Метод Гаусса-Жордана
4.3.2.
Упражнения
5.
Алгоритмы сравнения с образцом
5.1.
Сравнение строк
5.1.1.
Конечные автоматы
5.1.2.
Алгоритм Кнута-Морриса-Пратта
5.1.3.
Алгоритм Бойера-Мура
5.1.4.
Упражнения
5.2.
Приблизительное сравнение строк
5.2.1.
Анализ
5.2.2.
Упражнения
5.3.
Упражнения по программированию
6.
Алгоритмы на графах
6.1.
Основные понятия теории графов
6.1.1.
Терминология
6.1.2.
Упражнения
6.2.
Структуры данных для представления графов
6.2.1.
Матрица примыканий
6.2.2.
Список примыканий
6.2.3.
Упражнения
6.3.
Алгоритмы обхода в глубину и по уровням
6.3.1.
Обход в глубину
6.3.2.
Обход по уровням
6.3.3.
Анализ алгоритмов обхода
6.3.4.
Упражнения
6.4.
Алгоритм поиска минимального остовного дерева
6.4.1.
Алгоритм Дейкстры-Прима
6.4.2.
Алгоритм Крускала
6.4.3.
Упражнения
6.5.
Алгоритм поиска кратчайшего пути
6.5.1.
Алгоритм Дейкстры
6.5.2.
Упражнения
6.6.
Алгоритм определения компонент двусвязности
6.6.1.
Упражнения
6.7.
Разбиения множеств
6.8.
Упражнения по программированию
7.
Параллельные алгоритмы
7.1.
Введение в параллелизм
7.1.1.
Категории компьютерных систем
7.1.2.
Параллельные архитектуры
7.1.3.
Принципы анализа параллельных алгоритмов
7.1.4.
Упражнения
7.2.
Модель PRAM
7.2.1.
Упражнения
7.3.
Простые параллельные операции
7.3.1.
Распределение данных в модели CREW PRAM
7.3.2.
Распределение данных в модели EREW PRAM
7.3.3.
Поиск максимального элемента списка
7.3.4.
Упражнения
7.4.
Параллельный поиск
7.4.1.
Упражнения
7.5.
Параллельная сортировка
7.5.1.
Сортировка на линейных сетях
7.5.2.
Четно-нечетная сортировка перестановками
7.5.3.
Другие параллельные сортировки
7.5.4.
Упражнения
7.6.
Параллельные численные алгоритмы
7.6.1.
Умножение матриц в параллельных сетях
7.6.2.
Умножение матриц в модели CRCW PRAM
7.6.3.
Решение систем линейных уравнений алгоритмом SIMD 225
7.6.4.
Упражнения
7.7.
Параллельные алгоритмы на графах
7.7.1.
Параллельный алгоритм поиска кратчайшего пути
7.7.2.
Параллельный алгоритм поиска минимального остовного дерева
Упражнения
8.
Недетерминированные алгоритмы
8.1.
Что такое NP?
8.1.1.
Сведение задачи к другой задаче
8.1.2.
NP-полные задачи
8.2.
Типичные NP задачи
8.2.1.
Раскраска графа
8.2.2.
Раскладка по ящикам
8.2.3.
Упаковка рюкзака
8.2.4.
Задача о суммах элементов подмножеств
8.2.5.
Задача об истинности КНФ-выражения
8.2.6.
Задача планирования работ
8.2.7.
Упражнения
8.3.
Какие задачи относятся к классу NP?
8.3.1.
Выполнено ли равенство P=NP?
8.3.2.
Упражнения
8.4.
Проверка возможных решений
8.4.1.
Задача о планировании работ
8.4.2.
Раскраска графа
8.4.3.
Упражнения
9.
Другие алгоритмические инструменты
9.1.
Жадные приближенные алгоритмы
9.1.1.
Приближения в задаче о коммивояжере
9.1.2.
Приближения в задаче о раскладке по ящикам
9.1.3.
Приближения в задаче об упаковке рюкзака
9.1.4.
Приближения в задаче о сумме элементов подмножества
9.1.5.
Приближения в задаче о раскраске графа
9.1.6.
Упражнения
9.2.
Вероятностные алгоритмы
9.2.1.
Численные вероятностные алгоритмы
9.2.2.
Алгоритмы Монте Карло
9.2.3.
Алгоритмы Лас Вегаса
9.2.4.
Шервудские алгоритмы
9.2.5.
Сравнение вероятностных алгоритмов
9.2.6.
Упражнения
9.3.
Динамическое программирование
9.3.1.
Программирование на основе массивов
9.3.2.
Динамическое умножение матриц
9.3.3.
Упражнения
9.4.
Упражнения по программированию
А. Таблица случайных чисел
Б. Генерация псевдослучайных чисел
Б.1. Случайная последовательность в произвольном интервале
Б.2. Пример применения
Б.2.1. Первый способ
Б.2.2. Второй способ
Б.2.3. Третий способ
Б.3. Итоги
В. Ответы к упражнениям
Литература
Дополнение
Д.1. Элементы теории алгоритмов
Д.1.1. Введение в теорию алгоритмов
Д.1.2. Формализация понятия алгоритма
Д.1.3. Машина Поста
Д.1.4. Машина Тьюринга
Д.1.5. Алгоритмически неразрешимые проблемы
Д.1.6. Сложностные классы задач и проблема P=NP
Д.1.7. Классы открытых и закрытых задач и теоретическая нижняя граница временной сложности
Д.2. Оценки трудоемкости
Д.2.1. Функция трудоемкости и система обозначений
Д.2.2. Классификация алгоритмов на основе функции трудоемкости
Д.2.3. Элементарные операции в процедурном языке высокого уровня
Д.2.4. Методика анализа основных алгоритмических конструкций
Д.2.5. Примеры анализа трудоемкости алгоритмов
Д.2.6. Анализ сложности рекурсивных алгоритмов
Д.2.7. Трудоемкость рекурсивной реализации алгоритмов
Д.2.8. Методика подсчета вершин рекурсивного дерева
Д.2.9. Переход к временным оценкам
Д.2.10. Оценка ресурсной эффективности алгоритмов
Д.3. Идеи современных алгоритмов
Д.3.1. Алгоритмы и простые числа
Д.3.2. Генетические алгоритмы
Д.3.3. Муравьиные алгоритмы