Наверх

Р.Сэджвик, 2001 (Rus)
Фундаментальные алгоритмы на С++. Части 1-4
| Анализ | Структуры данных | Сортировка | Поиск |

Эта книга посвящена глубокому исследованию всех основных концепций и алгоритмов, которые можно отнести к разряду "вечных". Изучив их, вы получите знания, которые никогда не устареют и которыми вы будете пользоваться всегда. Краткость, точность, выверенность, актуальность, изобилие примеров и учебных заданий - вот лишь краткий перечень очевидных достоинств книги. Иллюстрация алгоритмов на одном из наиболее эффективных языков C++ лишний раз подчеркивает их популярность

Поскольку книга построена в виде курса лекций, ее можно использовать в учебном процессе


ОГЛАВЛЕНИЕ

ЧАСТЬ 1. АНАЛИЗ
ГЛАВА 1. ВВЕДЕНИЕ
1.1 Алгоритмы
1.2 Примеры задачи: связность
1.3 Алгоритмы объединение-поиск
1.4 перспектива
1.5 Обзор тем

ГЛАВА 2. ПРИНЦИПЫ АНАЛИЗА АЛГОРИТМОВ
2.1 Разработка и эмпирический анализ
2.2 Анализ алгоритмов
2.3 Рост функций
2.4 О-нотация
2.5 Простейшие рекурсии
2.6 Примеры алгоритмического анализа
2.7 Гарантии, предсказания и ограничения

ЧАСТЬ 2. СТРУКТУРЫ ДАННЫХ
ГЛАВА 3. ЭЛЕМЕНТАРНЫЕ СТРУКТУРЫ ДАННЫХ
3.1 Строительные блоки
3.2 Массивы
3.3 Связные списки
3.4 Обработка простых списков
3.5 Распределение памяти под списки
3.6 Строки
3.7 Составные структуры данных

ГЛАВА 4. АБСТРАКТНЫЕ ТИПЫ ДАННЫХ
4.1 Абстрактные объекты и коллекции объектов
4.2 АТД для стека магазинного типа
4.3 примеры программ-клиентов, использующих АTD стека
4.4 Реализация АТД стека
4.5 Создание нового АТД
4.6 Очереди FIFO и обобщенные очереди
4.7 Повторяющиеся и индексные элементы
4.8 АТД первого класса
4.9 Пример использования АТД
4.10 Перспективы

ГЛАВА 5. РЕКУРСИЯ И ДЕРЕВЬЯ
5.1 Рекурсивные алгоритмы
5.2 Разделяй и властвуй
5.3 Динамическое программирование
5.4 Деревья
5.5 Математические свойства бинарных деревьев
5.6 Обход дерева
5.7 Рекурсивные алгоритмы на бинарных деревьях
5.8 Обход графа
5.9 Перспективы

ЧАСТЬ 3.СОРТИРОВКА
ГЛАВА 6. ЭЛЕМЕНТАРНЫЕ МЕТОДЫ СОРТИРОВКИ
6.1 Правила игры
6.2 Сортировка выбором
6.3 Сортировка вставками
6.4 Пузырьковая сортировка
6.5 Характеристики производительности элементарных методов сортировки
6.6 Сортировка методом Шелла
6.7 Сортировка других типов данных
6.8 Сортировка по индексам и указателям
6.9 Сортировка связных списков
6.10 Метод распределяющего подсчета

ГЛАВА 7. БЫСТРАЯ СОРТИРОВКА
7.1 Базовый алгоритм
7.2 Характеристики производительности быстрой сортировки
7.3 Размер стека
7.4 Подфайлы небольших размеров
7.5 Метод разделения с вычислением медианы из трех элементов
7.6 Дублированные ключи
7.7 Строки и векторы
7.8 Выборка

ГЛАВА 8. СЛИЯНИЕ И СОРТИРОВКА СЛИЯНИЕМ
8.1 Двухпутевое слияние
8.2 Абстрактное обменное слияние
8.3 Нисходящая сортировка слиянием
8.4 Усовершенствования базового алгоритма
8.5 Восходящая сортировка слиянием
8.6 Производительность сортировки слиянием
8.7 реализация сортировки слиянием, ориентированной на связные списки
8.8 Возврат к рекурсии

ГЛАВА 9. ОЧЕРЕДИ ПО ПРИОРИТЕТАМ И ПИРАМИДАЛЬНАЯ СОРТИРОВКА
9.1 Элементарные реализации
9.2 Пирамидальная структура данных
9.3 Алгоритмы для сортирующих деревьев
9.4 Пирамидальная сортировка
9.5 Абстрактный тип данных очереди по приоритетам
9.6 Очередь по приоритетам для индексных элементов
9.7 Биномиальные очереди

ГЛАВА 10. ПОРАЗРЯДНАЯ СОРТИРОВКА
10.1 Биты, байты и слова
10.2 Двоичная быстрая сортировка
10.3 Поразрядная сортировка MSD
10.4 Трехпутевая поразрядная быстрая сортировка
10.5 Поразрядная сортировка LSD
10.6 Рабочие характеристики поразрядных сортировок
10.7 Сортировки с сублинейным временем выполнения

ГЛАВА 11. МЕТОДЫ СОРТИРОВКИ СПЕЦИАЛЬНОГО НАЗНАЧЕНИЯ
11.1 Четно-нечетная сортировка слиянием Бэтчера
11.2 Сети сортировки
11.3 Внешняя сортировка
11.4 Различные реализации сортировки-слияния
11.5 Параллельная процедура сортировки-слияния

ЧАСТЬ 4. ПОИСК
ГЛАВА 12. ТАБЛИЦЫ СИМВОЛОВ И ДЕРЕВЬЯ БИНАРНОГО ПОИСКА
12.1 Абстрактный тип данных таблицы символов
12.2 Поиск с использование индексации по ключам
12.3 Последовательный поиск
12.4 Бинарный поиск
12.5 Деревья бинарного поиска
12.6 Характеристики производительности деревьев бинарного поиска
12.7 Реализация индексов при использовании таблиц символов
12.8 Вставка в корень в деревьях бинарного поиска
12.9 Реализация других функций АТД с помощью BST-деревьев

ГЛАВА 13. СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ
13.1 Рандомизованные BST-деревья
13.2 Расширенные деревья бинарного поиска
13.3 Нисходящие 2-3-4-деревья
13.4 Красно-черные деревья или RB-деревья
13.5 Списки пропусков
13.6 Характеристики производительности

ГЛАВА 14. ХЕШИРОВАНИЕ
14.1 Хеш-функции
14.2 Раздельное связывание
14.3 Линейное зондирование
14.4 Двойное хеширование
14.5 Динамические хеш-таблицы
14.6 перспективы

ГЛАВА 15. ПОРАЗРЯДНЫЙ ПОИСК
15.1 Деревья цифрового поиска
15.2 Trie-деревья
15.3 Patricia-деревья
15.4 Многопутевые trie-деревья и TST-деревья
15.5 Алгоритмы индексирования текстовых строк

ГЛАВА 16. ВНЕШНИЙ ПОИСК
16.1 Правила игры
16.2 Индексированный последовательный доступ
16.3 B-деревья
16.4 Расширяемое хеширование
16.5 Перспективы