| Глава 1. ПРОЕКТИРОВАНИЕ И АНАЛИЗ | |
| 1.1. Трудоемкость алгоритма | 3 |
| 1.2. Понятие рекуррентного уравнения | 10 |
| 1.3. Решение рекуррентных уравнений | 11 |
| 1.4. Примеры рекуррентных уравнений | 21 |
| Глава 2. СОРТИРОВКА | |
| 2.1. Внутренняя сортировка | 24 |
| 2.1.1. Сортировка с помощью включения | 25 |
| 2.1.2. Сортировка выбором | 27 |
| 2.1.3. Сортировка с помощью обменов | 28 |
| 2.1.4. Сортировка слиянием | 31 |
| 2.1.5. Сортировка с помощью разделения | 33 |
| 2.2. Внешняя сортировка | 35 |
| 2.2.1. Алгоритм сортировки слиянием | 36 |
| 2.2.2. Минимизация полного времени выполнения | 42 |
| Глава 3. СТРУКТУРЫ ДАННЫХ | |
| 3.1. Элементарные структуры данных | 45 |
| 3.1.1. Массивы | 45 |
| 3.1.2. Линейные списки | 47 |
| 3.1.3. Стеки | 53 |
| 3.1.4. Очереди | 54 |
| 3.2. Графы. Основные определения | 59 |
| 3.3. Деревья. Основные определения | 64 |
| 3.4. Множества | 68 |
| 3.4.1. Представление множеств с помощью списков | 69 |
| 3.4.2. Представление множеств с помощью деревьев | 73 |
| 3.5. Приоритетные очереди | 78 |
| 3.5.1. Бинарные кучи | 78 |
| 3.5.2. Биномиальные кучи | 87 |
| 3.5.3. Кучи Фибоначчи | 96 |
| 3.5.4. Применение приоритетных очередей | 112 |
| Глава 4. ОРГАНИЗАЦИЯ ПОИСКА | |
| 4.1. Бинарные поисковые деревья | 117 |
| 4.2. Сбалансированные деревья | 122 |
| 4.2.1. АВЛ-дерево | 122 |
| 4.2.2. 2-3-дерево | 133 |
| 4.2.3. Красно-черное дерево | 141 |
| 4.3. Хеш-таблицы | 153 |
| 4.3.1. Открытое хеширование | 153 |
| 4.3.2. Закрытое хеширование | 156 |
| Глава 5. ОСНОВНЫЕ АЛГОРИТМЫ НА ГРАФАХ | |
| 5.1. Поиск в глубину в графе | 160 |
| 5.2. Поиск в ширину в графе | 164 |
| 5.3. Пути в графах | 168 |
| 5.3.1. Кратчайший элементарный путь | 168 |
| 5.3.2. Кратчайшие пути (маршруты) | 179 |
| 5.3.3. Кратчайший элементарный маршрут с нечетным числом ребер | 183 |
| 5.3.4. Эйлеров цикл | 185 |
| 5.3.5. Задача китайского почтальона | 190 |
| 5.4. Максимальный поток в графе и его приложения | 192 |
| 5.5. Циклы отрицательной стоимости | 203 |
| 5.5.1. Максимальное взвешенное паросочетание в двудольном графе | 204 |
| 5.5.2. Максимальный поток минимальной стоимости | 208 |
| 5.5.3. Минимальный средний контур в орграфе с положительными стоимостями дуг | 212 |
| 5.6. Минимальное остовное дерево графа | 216 |
| Глава 6. СТРАТЕГИИ РЕШЕНИЯ ЗАДАЧ | |
| 6.1. Метод "разделяй и властвуй" | 222 |
| 6.2. Динамическое программирование | 225 |
| 6.3. "Жадный" алгоритм | 232 |
| 6.4. Организация перебора | 244 |
| 6.4.1. Построение дерева решений | 244 |
| 6.4.2. Способы обхода дерева решений | 248 |
| 6.4.3. Применение границ | 249 |
| 6.4.4. Функции ветвления | 251 |
| ЛИТЕРАТУРА | 253 |