Антти Лааксонен - Олимпиадное программирование

расписания.................................................................................................61
4.2.3. Работы и сроки исполнения..........................................................................................62
4.3. Двоичный поиск............................................................................................................... 63
4.3.1. Реализация поиска............................................................................................................63
4.3.2. Нахождение оптимальных решений..........................................................................65

Глава 5. Структуры данных.......................................................................................... 68
5.1. Динамические массивы................................................................................................ 68

5.1.1. Векторы..................................................................................................................................68
5.1.2. Итераторы и диапазоны..................................................................................................69
5.1.3. Другие структуры данных...............................................................................................71
5.2. Множества.......................................................................................................................... 72
5.2.1. Множества и мультимножества....................................................................................72
5.2.2. Отображения........................................................................................................................74
5.2.3. Очереди с приоритетом..................................................................................................75
5.2.4. Множества, основанные на политиках......................................................................76
5.3. Эксперименты................................................................................................................... 77
5.3.1. Сравнение множества и сортировки......................................................................... 77
5.3.2. Сравнение отображения и массива...........................................................................78
5.3.3. Сравнение очереди с приоритетом и мультимножества...................................78

Глава 6. Динамическое программирование............................................................. 80
6.1. Основные понятия.......................................................................................................... 80

6.1.1. Когда жадный алгоритм не работает.........................................................................80
6.1.2. Нахождение оптимального решения.........................................................................81
6.1.3. Подсчет решений...............................................................................................................85
6.2. Другие примеры............................................................................................................... 86
6.2.1. Наибольшая возрастающая подпоследовательность..........................................86
6.2.2. Пути на сетке........................................................................................................................ 87
6.2.3. Задачи о рюкзаке...............................................................................................................89
6.2.4. От перестановок к подмножествам............................................................................91
6.2.5. Подсчет количества замощений..................................................................................92

Глава 7. Алгоритмы на графах..................................................................................... 95
7.1. Основы теории графов.................................................................................................. 95

7.1.1.Терминология........................................................................................................................96
7.1.2. Представление графа.......................................................................................................98
7.2. Обход графа..................................................................................................................... 101

Оглавление  7
7.2.1. Поиск в глубину................................................................................................................ 101
7.2.2. Поиск в ширину................................................................................................................ 103
7.2.3. Применения....................................................................................................................... 104
7.3. Кратчайшие пути............................................................................................................ 105
7.3.1. Алгоритм Беллмана–Форда........................................................................................ 106
7.3.2. Алгоритм Дейкстры......................................................................................................... 108
7.3.3. Алгоритм Флойда–Уоршелла...................................................................................... 110
7.4. Ориентированные ациклические графы.............................................................. 112
7.4.1. Топологическая сортировка........................................................................................ 113
7.4.2. Динамическое программирование.......................................................................... 114
7.5. Графы преемников........................................................................................................ 116
7.5.1. Нахождение преемников..............................................................................................117
7.5.2. Обнаружение циклов..................................................................................................... 118
7.6. Минимальные остовные деревья............................................................................ 119
7.6.1. Алгоритм Краскала.......................................................................................................... 120
7.6.2. Система непересекающихся множеств.................................................................. 122
7.6.3. Алгоритм Прима............................................................................................................... 124

Глава 8. Избранные вопросы проектирования алгоритмов................................ --">