| | |
| ПРЕДИСЛОВИЕ | 7 |
| Глава 1. ПРОЕКТИРОВАНИЕ И АНАЛИЗ АЛГОРИТМОВ | |
| 1.1. Трудоемкость алгоритма | 9 |
| 1.2. Понятие рекуррентного соотношения | 19 |
| 1.3. Решение рекуррентных соотношений | 21 |
| 1.4. Примеры рекуррентных уравнений | 33 |
| Глава 2. БАЗОВЫЕ АЛГОРИТМЫ ПОИСКА И СОРТИРОВКИ | |
| 2.1. Поиск элемента | 43 |
| 2.2. Внутренняя сортировка | 45 |
| 2.2.1. Сортировка с помощью включения | 46 |
| 2.2.2. Сортировка выбором | 47 |
| 2.2.3. Сортировки с помощью обменов | 48 |
| 2.2.4. Сортировка слиянием | 51 |
| 2.2.5. Сортировка с помощью разделения | 52 |
| 2.3. Внешняя сортировка | 55 |
| 2.4. Алгоритмы выборки | 61 |
| Глава 3. СТРУКТУРЫ ДАННЫХ | |
| 3.1. Элементарные структуры данных | 64 |
| 3.1.1. Массивы | 64 |
| 3.1.2. Линейные списки | 65 |
| 3.1.3. Стеки | 70 |
| 3.1.4. Очереди | 71 |
| 3.2. Множества | 76 |
| 3.2.1. Представление множеств с помощью списков | 77 |
| 3.2.2. Представление множеств с помощью деревьев | 80 |
| 3.3. Приоритетные очереди | 83 |
| 3.3.1. Бинарные кучи | 83 |
| 3.3.2. Биномиальные кучи | 91 |
| 3.3.3. Кучи Фибоначчи | 97 |
| 3.3.4. Применение приоритетных очередей | 109 |
| 3.4. Задачи для самостоятельного решения | 110 |
| Глава 4. ОСНОВНЫЕ АЛГОРИТМЫ НА ГРАФАХ | |
| 4.1. Графы. Основные определения | 113 |
| 4.2. Поиск в глубину | 117 |
| 4.3. Поиск в ширину | 121 |
| 4.4. Пути в орграфах. Маршруты в графах | 123 |
| 4.4.1. Кратчайший элементарный путь | 123 |
| 4.4.2. Кратчайшие пути (маршруты) | 132 |
| 4.4.3. Максимальный путь в бесконтурном орграфе | 134 |
| 4.4.4. Эйлеров цикл | 135 |
| 4.4.5. Наибольшее число маршрутов между заданной парой вершин, не пересекающихся по ребрам | 138 |
| 4.4.6. к кратчайших ( v , w ) маршрутов, не пересекающихся по ребрам | 140 |
| 4.5. Максимальный поток в сети и его приложения | 143 |
| 4.6. Циклы отрицательной стоимости | 155 |
| 4.6.1. Наибольшее паросочетание максимального веса в двудольном графе | 155 |
| 4.6.2. Максимальный поток минимальной стоимости | 157 |
| 4.6.3. Минимальный средний контур в орграфе с положительными стоимостями дуг | 160 |
| 4.7. Минимальное остовное дерево графа | 162 |
| 4.8. Кратчайший маршрут с нечетным числом ребер | 167 |
| 4.9. Задача китайского почтальона | 169 |
| 4.10. Задачи для самостоятельного решения | 171 |
| Глава 5. ОРГАНИЗАЦИЯ ПОИСКА | |
| 5.1. Деревья. Основные определения | 174 |
| 5.2. Бинарные поисковые деревья | 178 |
| 5.3. Сбалансированные деревья | 180 |
| 5.3.1. АВЛ-дерево | 180 |
| 5.3.2. 2-3- дерево | 190 |
| 5.4. Хеш-таблицы | 195 |
| 5.4.1. Открытое хеширование | 195 |
| 5.4.2. Закрытое хеширование | 197 |
| 5.5. Задачи для самостоятельного решения | 200 |
| Глава 6. СТРАТЕГИИ РЕШЕНИЯ ЗАДАЧ | |
| 6.1. Метод «разделяй и властвуй» | 201 |
| 6.2. Динамическое программирование | 204 |
| 6.3. Организация перебора | 211 |
| 6.3.1. Построение дерева решений | 212 |
| 6.3.2. Способы обхода дерева решений | 214 |
| 6.3.3. Сокращение числа необходимых для решения подзадач: отсев возможных вариантов ветвления | 217 |
| 6.4. Задачи для самостоятельного решения | 228 |
| ПРИЛОЖЕНИЕ | 231 |
| ЛИТЕРАТУРА | 265 |