⇐ Назад

О чем эта книга..........................................................................................13
Навыки, которые вы приобретете.................................................................14
В чем особенность книг этой серии..........................................................16
Для кого эта книга?...................................................................................17
Дополнительные ресурсы.........................................................................18
Благодарности...........................................................................................20
От издательства...........................................................................................20
Глава 13. Введение в жадные алгоритмы...............................................21
13.1. Парадигма проектирования жадных алгоритмов..................................22
13.1.1. Парадигмы алгоритмов.............................................................22
13.1.2. Темы жадной парадигмы..........................................................23
13.2. Задача планирования...........................................................................25
13.2.1. Постановка...............................................................................25
13.2.2. Сроки завершения....................................................................26
13.2.3. Целевая функция......................................................................27
13.2.4. Решение упражнения 13.1........................................................28
13.3. Разработка жадного алгоритма............................................................28
13.3.1. Два частных случая..................................................................29
13.3.2. Дуэльные жадные алгоритмы....................................................29
13.3.3. Решения упражнений 13.2–13.3................................................33
13.4. Доказательство правильности..............................................................34
13.4.1. Случай отсутствия совпадающих значений:
высокоуровневый план........................................................................35
13.4.2. Обмен работами при последовательной инверсии....................36
13.4.3. Анализ стоимости и преимущества............................................38
13.4.4. Обработка совпадений значений..............................................40
13.4.5. Решения упражнений 13.4–13.5................................................41
Задачи на закрепление материала...............................................................44
Задачи по программированию......................................................................45
Глава 14. Коды Хаффмана........................................................................46
14.1. Коды....................................................................................................47
14.1.1. Двоичные коды фиксированной длины.....................................47
14.1.2. Коды переменной длины...........................................................47
14.1.3. Беспрефиксные коды................................................................49
14.1.4. Преимущества беспрефиксных кодов........................................50
14.1.5. Определение задачи.................................................................51
14.1.6. Решения упражнений 14.1–14.2................................................52
14.2. Коды в виде деревьев..........................................................................52
14.2.1. Три примера.............................................................................53
14.2.2. Какие деревья представляют беспрефиксные коды?.................55
14.2.3. Определение задачи (в новой формулировке)..........................56
14.3. Жадный алгоритм Хаффмана...............................................................57
14.3.1. Построение деревьев путем последовательных слияний...........57
14.3.2. Жадный критерий Хаффмана....................................................60
14.3.3. Псевдокод.................................................................................61
14.3.4. Пример.....................................................................................63
14.3.5. Более крупный пример.............................................................64
14.3.6. Время выполнения....................................................................66
14.3.7. Решение упражнения 14.3.........................................................67
*14.4. Доказательство правильности..............................................................67
14.4.1. Высокоуровневый план.............................................................68
14.4.2. Подробности.............................................................................69
Задачи на закрепление материала...............................................................76
Сложные задачи...........................................................................................78
Задачи по программированию......................................................................78
Глава 15. Минимальные остовные деревья............................................79
15.1. Определение задачи............................................................................80
15.1.1. Графы.......................................................................................80
15.1.2. Остовные деревья.....................................................................81
15.1.3. Решение упражнения 15.1........................................................84
15.2. Алгоритм Прима...................................................................................85
15.2.1. Пример.....................................................................................85
15.2.2. Псевдокод.................................................................................88
15.2.3. Простая реализация..................................................................90
*15.3. Ускорение алгоритма Prim посредством куч.........................................91
15.3.1. В поисках времени выполнения, близкого к линейному............91
15.3.2. Кучевая структура данных........................................................92
15.3.3. Как использовать кучи в алгоритме Прима...............................93
15.3.4. Псевдокод.................................................................................95
15.3.5. Анализ времени выполнения....................................................97
15.3.6. Решение упражнения 15.3........................................................98
*15.4. Алгоритм Прима: доказательство правильности...................................98
15.4.1. Свойство минимального узкого места.......................................99
15.4.2. Интересные факты об остовных деревьях...............................102
15.4.3. Доказательство теоремы 15.6 (из свойства минимального
узкого места следует минимальное остовное дерево)........................105
15.4.4. Сводя все воедино..................................................................107
15.5. Алгоритм Краскала............................................................................107
15.5.1. Пример...................................................................................107
15.5.2. Псевдокод...............................................................................110
15.5.3. Простая реализация................................................................111
*15.6. Ускорение алгоритма Краскала с помощью структуры
данных Union-Find......................................................................................112
15.6.1. Структура данных Union-Find..................................................113
15.6.2. Псевдокод...............................................................................115
15.6.3. Анализ времени выполнения..................................................116
15.6.4. Быстрая и приближенная реализация структуры
данных Union-Find..............................................................................117
15.6.5. Решения упражнений 15.5–15.7..............................................123
*15.7. Алгоритм Краскала: доказательство правильности.............................124
15.8. Применение: кластеризация с одиночной связью...............................126
15.8.1. Кластеризация........................................................................127
15.8.2. Восходящая кластеризация.....................................................128
Задачи на закрепление материала.............................................................132
Задачи повышенной сложности..................................................................134
Задачи по программированию....................................................................136
Глава 16. Введение в динамическое программирование.....................137
16.1. Задача о взвешенном независимом множестве..................................138
16.1.1. Определение задачи...............................................................139
16.1.2. Естественный жадный алгоритм оказывается безуспешным....141
16.1.3. Подход «разделяй и властвуй»?..............................................142
16.1.4. Решения упражнений 16.1–16.2..............................................143
16.2. Линейно-временной алгоритм для взвешенного независимого множества на путях......144
16.2.1. Оптимальная подструктура и рекуррентное соотношение.......144
16.2.2. Наивный рекурсивный подход.................................................147
16.2.3. Рекурсия с кэшем....................................................................148
16.2.4. Восходящая итеративная реализация.....................................149
16.2.5. Решения упражнений 16.3–16.4..............................................151
16.3. Алгоритм реконструкции....................................................................152
16.4. Принципы динамического программирования....................................155
16.4.1. Трехшаговый рецепт...............................................................155
16.4.2. Желаемые свойства подзадач.................................................156
16.4.3. Повторяемый мыслительный процесс.....................................157
16.4.4. Динамическое программирование против
«разделяй и властвуй».......................................................................157
16.4.5. Почему «динамическое программирование»?.........................159
16.5. Задача о ранце..................................................................................160
16.5.1. Определение задачи...............................................................160
16.5.2. Оптимальная подструктура и рекурренция.............................161
16.5.3. Подзадачи..............................................................................164
16.5.4. Алгоритм динамического программирования..........................165
16.5.5. Пример...................................................................................167
16.5.6. Реконструкция........................................................................168
16.5.7. Решения упражнений 16.5–16.6..............................................169
Задачи на закрепление материала.............................................................171
Задачи повышенной сложности..................................................................173
Задачи по программированию....................................................................174
Глава 17. Расширенное динамическое программирование.................175
17.1. Выравнивание последовательностей..................................................176
17.1.1. Актуальность...........................................................................176
17.1.2. Определение задачи...............................................................177
17.1.3. Оптимальная подструктура.....................................................179
17.1.4. Рекуррентное соотношение.....................................................182
17.1.5. Подзадачи...............................................................................183
17.1.6. Алгоритм динамического программирования...........................184
17.1.7. Реконструкция.........................................................................185
17.1.8. Решение упражнений 17.1–17.3...............................................186
*17.2. Оптимальные бинарные деревья поиска............................................187
17.2.1. Обзор бинарного дерева поиска..............................................188
17.2.2. Среднее время поиска.............................................................190
17.2.3. Определение задачи...............................................................192
17.2.4. Оптимальная подструктура.....................................................193
17.2.5. Рекуррентные соотношения....................................................197
17.2.6. Подзадачи...............................................................................198
17.2.7. Алгоритм динамического программирования...........................199
17.2.8. Улучшение времени выполнения.............................................202
17.2.9. Решения упражнений 17.4–17.5...............................................203
Задачи на закрепление материала.............................................................204
Задачи повышенной сложности..................................................................206
Задачи по программированию....................................................................207
Глава 18. Кратчайшие пути повторно....................................................208
18.1. Кратчайшие пути с отрицательными длинами ребер..........................209
18.1.1. Задача о кратчайшем пути с единственным истоком...............209
18.1.2. Отрицательные циклы............................................................211
18.1.3. Решение упражнения 18.1......................................................214
18.2. Алгоритм Беллмана—Форда...............................................................214
18.2.1. Подзадачи..............................................................................215
18.2.2. Оптимальная подструктура.....................................................217
18.2.3. Рекурренция...........................................................................219
18.2.4. Когда следует остановиться?..................................................220
18.2.5. Псевдокод...............................................................................222
18.2.6. Пример...................................................................................223
18.2.7. Время выполнения..................................................................226
18.2.8. Маршрутизация интернета......................................................227
18.2.9. Решения упражнений 18.2–18.3..............................................228
18.3. Задача о кратчайшем пути для всех пар............................................229
18.3.1. Определение задачи...............................................................229
18.3.2. Сведение до кратчайших путей с единственным истоком........230
18.3.3. Решение упражнения 18.4......................................................231
18.4. Алгоритм Флойда—Уоршелла.............................................................231
18.4.1. Подзадачи..............................................................................231
18.4.2. Оптимальная подструктура.....................................................233
18.4.3. Псевдокод...............................................................................236
18.4.4. Обнаружение отрицательного цикла.......................................239
18.4.5. Резюме и открытые вопросы...................................................240
18.4.6. Решения упражнений 18.5–18.6..............................................241
Задачи на закрепление материала.............................................................243
Задачи повышенной сложности..................................................................244
Задачи по программированию....................................................................245
Эпилог: руководство по разработке алгоритмов..................................246
Подсказки и решения избранных задач................................................248

Оглавление