В гостях у Грёблина

Предисловие

1. Основы анализа алгоритмов

Что такое анализ?
Что подсчитывать и что учитывать
Необходимые математические сведения
Скорости роста
Алгоритмы вида «разделяй и властвуй»
Рекуррентные соотношения
Анализ программ

2. Алгоритмы поиска и выборки

Последовательный поиск
Двоичный поиск
Выборка
Упражнение по программированию

3. Алгоритмы сортировки

Сортировка вставками
Пузырьковая сортировка
Сортировка Шелла
Корневая сортировка
Пирамидальная сортировка
Сортировка слиянием
Быстрая сортировка
Внешняя многофазная сортировка слиянием
Дополнительные упражнения
Упражнения по программированию

4. Численные алгоритмы

Вычисление значений многочленов
Умножение матриц
Решение линейных уравнений

5. Алгоритмы сравнения с образцом

Сравнение строк
Приблизительное сравнение строк
Упражнения по программированию

6. Алгоритмы на графах

Основные понятия теории графов
Структуры данных для представления графов
Алгоритмы обхода в глубину и по уровням
Алгоритм поиска минимального остовного дерева
Алгоритм поиска кратчайшего пути
Алгоритм определения компонент двусвязности
Разбиения множеств
Упражнения по программированию

7. Параллельные алгоритмы

Введение в параллелизм
Модель PRAM
Простые параллельные операции
Параллельный поиск
Параллельная сортировка
Параллельные численные алгоритмы
Параллельные алгоритмы на графах

8. Недетерминированные алгоритмы

Что такое NP?
Типичные NP задачи
Какие задачи относятся к классу NP?
Проверка возможных решений

9. Другие алгоритмические инструменты

Жадные приближенные алгоритмы
Вероятностные алгоритмы
Динамическое программирование
Упражнения по программированию

А. Таблица случайных чисел

Б. Генерация псевдослучайных чисел

Случайная последовательность в произвольном интервале
Пример применения
Итоги

В. Ответы к упражнениям

Литература

Дополнение

Элементы теории алгоритмов
Оценки трудоемкости
Идеи современных алгоритмов