Ешь, двигайся, спи Жесткий подход Дэна Кеннеди Телефоны Бизбук - c 10 до 18 по будним дням
 
Наши проекты:
Вход для зарегистрированных пользователей
Регистрация нового пользователя
Каталог книг Новинки Анонсы Заказы / Корзина Рассылка Оплата и Доставка Контакты
Вы находитесь в разделе каталога:
• Алгоритмы: разработка и применение. Классика Computers Science, Клейнберг Д., Тардос Е.


Алгоритмы: разработка и применение. Классика Computers Science
Алгоритмы: разработка и применение. Классика Computers Science
Клейнберг Д., Тардос Е.
Год выпуска: 2016
Изд-во: Питер
ISBN: 978-5-496-01545-5
Переплёт: твердый
800 страниц
Цена: 944.00 грн.
Временно отсутствует     Оставить заявку
Алгоритмы - это основа программирования, определяющая, каким образом программное обеспечение будет использовать структуры данных.
Впервые на русском языке выходит одна из самых авторитетных книг по разработке и использованию алгоритмов.
В книге "Алгоритмы: разработка и применение. Классика Computers Science" вы познакомитесь с базовыми аспектами построения алгоритмов, основными понятиями и определениями, структурами данных, затем перейдете к основным методам построения алгоритмов, неразрешимости и методам решения неразрешимых задач, и, наконец, изучите рандомизацию при проектировании алгоритмов.
Самые сложные темы объясняются на четких и простых примерах, поэтому книга может использоваться как для самостоятельного изучения студентами, так и учеными-исследователями или профессионалами в области компьютерных технологий, которые хотят получить представление о применении тех или иных методов проектирования алгоритмов.
Алгоритмический анализ состоит из двух фундаментальных компонентов: выделения математически чистого ядра задачи и выявления методов проектирования подходящего алгоритма на основании структуры задачи. И чем лучше аналитик владеет полным арсеналом возможных методов проектирования, тем быстрее он начинает распознавать "чистые" формулировки, лежащие в основе запутанных задач реального мира.




Оглавление книги "Алгоритмы: разработка и применение. Классика Computers Science"




Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Общие сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Учебные аспекты и дополнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Краткое содержание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Как пользоваться книгой . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Глава 1. Введение: некоторые типичные задачи . . . . . . . . . . . . . . . . . . . . . . . 27
1.1. Первая задача: устойчивые паросочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Проектирование алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Расширения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
1.2. Пять типичных задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Интервальное планирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Взвешенное интервальное планирование . . . . . . . . . . . . . . . . . . . . . . . . . 41
Двудольные паросочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Независимое множество . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Задача конкурентного размещения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Глава 2. Основы анализа алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.1. Вычислительная разрешимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Первые попытки определения эффективности . . . . . . . . . . . . . . . . . . . . . 57
Худшее время выполнения и поиск методом "грубой силы" . . . . . . . . . 58
Полиномиальное время как показатель эффективности . . . . . . . . . . . . . 60
2.2. Асимптотический порядок роста . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
O, ? и ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Свойства асимптотических скоростей роста . . . . . . . . . . . . . . . . . . . . . . . 66
Асимптотические границы для некоторых
распространенных функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.3. Реализация алгоритма устойчивых паросочетаний
со списками и массивами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Массивы и списки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
Реализация алгоритма устойчивых паросочетаний . . . . . . . . . . . . . . . . . 73
2.4. Обзор типичных вариантов времени выполнения . . . . . . . . . . . . . . . . . . . . . . 74
Линейное время . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Время O(n log n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
Квадратичное время . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Кубическое время . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Время O(nk) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
За границами полиномиального времени . . . . . . . . . . . . . . . . . . . . . . . . . 81
Сублинейное время . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.5. Более сложная структура данных: приоритетная очередь . . . . . . . . . . . . . . . 83
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Структура данных для реализации приоритетной очереди . . . . . . . . . . . 85
Реализация операций с кучей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Реализация приоритетной очереди на базе кучи . . . . . . . . . . . . . . . . . . . 90
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Глава 3. Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.1. Основные определения и применения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.2. Связность графа и обход графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
Поиск в ширину . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Связная компонента . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
Поиск в глубину . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Набор всех компонент связности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.3. Реализация перебора графа с использованием очередей и стеков . . . . . 111
Представление графов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Очереди и стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
Реализация поиска в ширину . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
Реализация поиска в глубину . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
Определение всех компонент связности . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.4. Проверка двудольности: практическое применение поиска в ширину . . . 118
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Проектирование алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.5. Связность в направленных графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Представление направленных графов . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Алгоритмы поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Сильная связность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.6. Направленные ациклические графы и топологическое упорядочение . . . 123
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Проектирование и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Глава 4. Жадные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.1. Интервальное планирование: жадный алгоритм опережает . . . . . . . . . . . . 138
Проектирование жадного алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Расширения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Взаимосвязанная задача: планирование всех интервалов . . . . . . . . . . 143
4.2. Планирование для минимизации задержки: метод замены . . . . . . . . . . . . 147
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Проектирование алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Расширения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.3. Оптимальное кэширование: более сложный пример замены . . . . . . . . . . . 153
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
Расширения: кэширование в реальных рабочих условиях . . . . . . . . . . 157
4.4. Кратчайшие пути в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.5. Задача нахождения минимального остовного дерева . . . . . . . . . . . . . . . . . 163
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
Анализ алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
Реализация алгоритма Прима . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
Расширения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
4.6. Реализация алгоритма Крускала: структура Union-Find . . . . . . . . . . . . . . . . 172
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
Простая структура данных для структуры Union-Find . . . . . . . . . . . . . . . 173
Усовершенствованная структура данных Union-Find . . . . . . . . . . . . . . . 175
Дальнейшие улучшения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
Реализация алгоритма Крускала . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
4.7. Кластеризация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.8. Коды Хаффмана и сжатие данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
Расширения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.9.* Ориентированные деревья с минимальной стоимостью:
многофазный жадный алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Упражнение с решением 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Глава 5. Разделяй и властвуй . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
5.1. Первое рекуррентное отношение: алгоритм сортировки слиянием . . . . . 227
Методы разрешения рекуррентности . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Раскрутка рекуррентности в алгоритме сортировки слиянием . . . . . . 229
Подстановка решения в рекуррентное отношение сортировки
слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
Использование частичной подстановки . . . . . . . . . . . . . . . . . . . . . . . . . . 230
5.2. Другие рекуррентные отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
Случай q > 2 подзадач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Случай одной подзадачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
Похожее рекуррентное отношение: T(n) ? 2T(n/2) + O(n2) . . . . . . . . . . . 236
5.3. Подсчет инверсий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
5.4. Поиск ближайшей пары точек . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
5.5. Целочисленное умножение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
5.6. Свертки и быстрое преобразование Фурье . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Разработка и анализа алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
Глава 6. Динамическое программирование . . . . . . . . . . . . . . . . . . . . . . . . . 266
6.1. Взвешенное интервальное планирование: рекурсивная процедура . . . . . 267
Разработка рекурсивного алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Мемоизация рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Анализ мемоизированной версии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Вычисление решения помимо его значения . . . . . . . . . . . . . . . . . . . . . . 272
6.2. Принципы динамического программирования: мемоизация
или итерации с подзадачами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
Основная схема динамического программирования . . . . . . . . . . . . . . . 274
6.3. Сегментированные наименьшие квадраты: многовариантный выбор . . . 275
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
6.4. Задача о сумме подмножеств и задача о рюкзаке:
добавление переменной . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
6.5. Вторичная структура РНК: динамическое программирование
по интервалам . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
6.6. Выравнивание последовательностей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
6.7. Выравнивание последовательностей в линейном пространстве
по принципу "разделяй и властвуй" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
6.8. Кратчайшие пути в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
Расширения: основные усовершенствования алгоритма . . . . . . . . . . . 308
6.9. Кратчайшие пути и дистанционно-векторные протоколы . . . . . . . . . . . . . . 311
Недостатки дистанционно-векторного протокола . . . . . . . . . . . . . . . . . 313
6.10. Отрицательные циклы в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
Расширения: улучшенные алгоритмы нахождения кратчайшего
пути и отрицательного цикла . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
Глава 7. Нахождение потока в сети . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
7.1. Задача о максимальном потоке и алгоритм Форда-Фалкерсона . . . . . . . 348
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
Анализ алгоритма: завершение и время выполнения . . . . . . . . . . . . . . 355
7.2. Максимальные потоки и минимальные разрезы . . . . . . . . . . . . . . . . . . . . . . 356
Анализ алгоритма: потоки и разрезы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
Анализ алгоритма: максимальный поток равен
минимальному разрезу . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
Дальнейший анализ: целочисленные потоки . . . . . . . . . . . . . . . . . . . . . . 360
7.3. Выбор хороших увеличивающих путей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
Разработка ускоренного алгоритма потока . . . . . . . . . . . . . . . . . . . . . . . 362
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
Расширения: сильные полиномиальные алгоритмы . . . . . . . . . . . . . . . 366
7.4.* Алгоритм проталкивания предпотока . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
Расширения: улучшенная версия алгоритма . . . . . . . . . . . . . . . . . . . . . . 374
Реализация алгоритма проталкивания предпотока . . . . . . . . . . . . . . . . 375
7.5. Первое применение: задача о двудольном паросочетании . . . . . . . . . . . . . 377
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
Расширения: структура двудольных графов
без идеального паросочетания . . . . . . . . . . . . . . . . . . . . . . . . . . . . 380
7.6. Непересекающиеся пути в направленных и ненаправленных графах . . . . 383
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
Расширения: непересекающиеся пути в ненаправленных графах . . . 387
7.7. Расширения задачи о максимальном потоке . . . . . . . . . . . . . . . . . . . . . . . . . 388
Задача: циркуляция с потреблением . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
Разработка и анализ алгоритма для циркуляций . . . . . . . . . . . . . . . . . . 390
Задача: циркуляция с потреблением и нижние границы . . . . . . . . . . . . 392
Разработка и анализ алгоритма с нижними границами . . . . . . . . . . . . . 392
7.8. Планирование опроса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
7.9. Планирование авиаперелетов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 399
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
Расширения: моделирование других аспектов задачи . . . . . . . . . . . . . 400
7.10. Сегментация изображений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
7.11. Выбор проекта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
7.12. Выбывание в бейсболе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
Характеристика выбывания команды . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
7.13.* Добавление стоимостей в задачу паросочетаний . . . . . . . . . . . . . . . . . . . 414
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
Расширения: экономическая интерпретация цен . . . . . . . . . . . . . . . . . . 419
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
Глава 8. NP-полнота и вычислительная неразрешимость . . . . . . . . . . . . . . 458
8.1. Полиномиальное сведение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
Первое сведение: независимое множество и вершинное покрытие . . 461
Сведение к более общему случаю: вершинное покрытие
к покрытию множества . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
8.2. Сведение с применением "регуляторов": задача выполнимости . . . . . . . . 466
Задачи SAT и 3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
Сведение задачи 3-SAT к задаче о независимом множестве . . . . . . . . 467
Транзитивность сведения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
8.3. Эффективная сертификация и определение NP . . . . . . . . . . . . . . . . . . . . . . 470
Задачи и алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
Эффективная сертификация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
NP: класс задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
8.4. NP-полные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
Выполнимость булевой схемы: первая NP-полная задача . . . . . . . . . . 473
Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
Доказательство NP-полноты других задач . . . . . . . . . . . . . . . . . . . . . . . . 476
Общая стратегия доказательства NP-полноты новых задач . . . . . . . . . 479
8.5. Задачи упорядочения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
Задача коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
Задача о гамильтоновом цикле . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481
Доказательство NP-полноты задачи о гамильтоновом цикле . . . . . . . . 482
Доказательство NP-полноты задачи коммивояжера . . . . . . . . . . . . . . . 485
Расширения: задача о гамильтоновом пути . . . . . . . . . . . . . . . . . . . . . . . 486
8.6. Задачи о разбиении . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
Задача о трехмерном сочетании . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 487
Доказательство NP-полноты трехмерного сочетания . . . . . . . . . . . . . . 488
8.7. Задача о раскраске графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
Задача о раскраске графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
Вычислительная сложность задачи о раскраске графа . . . . . . . . . . . . . 493
Доказательство NP-полноты задачи о 3-раскраске . . . . . . . . . . . . . . . . 494
Заключение: о проверке гипотезы четырех цветов . . . . . . . . . . . . . . . . 497
8.8. Численные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
Задача о суммировании подмножеств . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
Доказательство NP-полноты задачи о суммировании подмножеств . . 498
Расширения: сложность некоторых задач планирования . . . . . . . . . . . 500
Внимание: суммирование подмножеств с полиномиально
ограничиваемыми числами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
8.9. Co-NP и асимметрия NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
Хорошая характеризация: класс NP??co-NP . . . . . . . . . . . . . . . . . . . . . . 503
8.10. Частичная классификация сложных задач . . . . . . . . . . . . . . . . . . . . . . . . . . 504
Задачи упаковки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Задачи покрытия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Задачи разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
Задачи упорядочения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
Численные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
Задачи соблюдения ограничений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 509
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
Глава 9. PSPACE: класс задач за пределами?NP . . . . . . . . . . . . . . . . . . . . . 534
9.1. PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
9.2. Некоторые сложные задачи из PSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
Задачи построения плана . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
Кванторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537
Игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538
9.3. Решение задач с кванторами и игровых задач в полиномиальном
пространстве . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
Разработка алгоритма для QSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540
Расширения: алгоритм для задачи конкурентного размещения . . . . . 540
9.4. Решение задачи построения плана с полиномиальным пространством . . 541
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545
9.5. Доказательство PSPACE-полноты задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
Связь задач с кванторами с игровыми задачами . . . . . . . . . . . . . . . . . . 546
Доказательство PSPACE-полноты задачи конкурентного
размещения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553
Глава 10. Расширение пределов разрешимости . . . . . . . . . . . . . . . . . . . . . 555
10.1. Поиск малых вершинных покрытий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
10.2. Решение NP-сложных задач для деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . 559
Жадный алгоритм для задачи о независимом множестве
для деревьев . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560
Независимое множество с максимальным весом для деревьев . . . . . 562
10.3. Раскраска множества дуг . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572
10.4.* Декомпозиция графа в дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
Определение древовидной ширины . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574
Свойства декомпозиции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
Динамическое программирование и древовидная декомпозиция . . . 580
10.5.* Построение древовидной декомпозиции . . . . . . . . . . . . . . . . . . . . . . . . . . 584
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 591
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
Глава 11. Аппроксимирующие алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . 599
11.1. Жадные алгоритмы и ограничения оптимума:
задача распределения нагрузки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
Расширения: улучшенный аппроксимирующий алгоритм . . . . . . . . . . . 604
11.2. Задача о выборе центров . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606
11.3. Покрытие множества: обобщенная жадная эвристика . . . . . . . . . . . . . . . . 611
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
11.4. Метод назначения цены: вершинное покрытие . . . . . . . . . . . . . . . . . . . . . . 616
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617
Разработка алгоритма: метод назначения цены . . . . . . . . . . . . . . . . . . . 618
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
11.5. Максимизация методом назначения цены:
задача о непересекающихся путях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
Разработка и анализ жадного алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . 624
Разработка и анализ алгоритма назначения цены . . . . . . . . . . . . . . . . . 626
11.6. Линейное программирование и округление: применение к задаче
о вершинном покрытии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
Линейное программирование как обобщенный метод . . . . . . . . . . . . . 629
Задача о вершинном покрытии как целочисленная программа . . . . . . 632
Использование линейного программирования для задачи
вершинного покрытия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634
11.7.* Снова о распределении нагрузки: более сложное применение LP . . . . . 635
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
11.8. Аппроксимации с произвольной точностью: задача о рюкзаке . . . . . . . . 642
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
Новый алгоритм динамического программирования для задачи
о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
Решение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
Глава 12. Локальный поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659
12.1. Задача оптимизации в перспективе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660
Потенциальная энергия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660
Связь с оптимизацией . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662
Локальный поиск в задаче о вершинном покрытии . . . . . . . . . . . . . . . . 663
12.2. Алгоритм Метрополиса и имитация отжига . . . . . . . . . . . . . . . . . . . . . . . . . 665
Алгоритм Метрополиса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
Имитация отжига . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
12.3. Применение локального поиска в нейронных сетях Хопфилда . . . . . . . . . 669
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
12.4. Аппроксимация задачи о максимальном разрезе
с применением локального поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675
12.5. Выбор соседского отношения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
Алгоритмы локального поиска при разбиении графов . . . . . . . . . . . . . 678
12.6.* Классификация на базе локального поиска . . . . . . . . . . . . . . . . . . . . . . . . 679
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686
12.7. Динамика наилучших ответов и равновесия Нэша . . . . . . . . . . . . . . . . . . . 688
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688
Динамика наилучших ответов и равновесия Нэша:
определения и примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
Связь с локальным поиском . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691
Два основных вопроса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
Поиск хорошего равновесия Нэша . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
Глава 13. Рандомизированные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . 704
13.1. Первое применение: разрешение конфликтов . . . . . . . . . . . . . . . . . . . . . . 705
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
Разработка рандомизированного алгоритма . . . . . . . . . . . . . . . . . . . . . 706
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706
13.2. Нахождение глобального минимального разреза . . . . . . . . . . . . . . . . . . . . 711
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 711
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 713
Дальнейший анализ: количество глобальных
минимальных разрезов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715
13.3. Случайные переменные и ожидания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716
Пример: ожидание первого успеха . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
Линейность ожидания . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
Пример: угадывание карт . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718
Пример: сбор купонов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719
Последнее определение: условное ожидание . . . . . . . . . . . . . . . . . . . . 721
13.4. Рандомизированный аппроксимирующий алгоритм
для задачи MAX 3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
Разработка и анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 722
Дальнейший анализ: поиск хорошего присваивания . . . . . . . . . . . . . . . 723
13.5. Рандомизация принципа ""разделяй и властвуй":
нахождение медианы и быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . 725
Задача: нахождение медианы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728
Второй пример: быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . 729
13.6. Хеширование: рандомизированная реализация словарей . . . . . . . . . . . . 731
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732
Разработка структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733
Универсальные классы хеш-функций . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735
Анализ структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
13.7. Нахождение ближайшей пары точек: рандомизированный метод . . . . . . 738
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 739
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740
Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743
13.8. Рандомизация кэширования . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747
Разработка класса алгоритмом маркировки . . . . . . . . . . . . . . . . . . . . . . 748
Анализ алгоритмов маркировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749
Разработка рандомизированного алгоритма маркировки . . . . . . . . . . 751
Анализ рандомизированного алгоритма маркировки . . . . . . . . . . . . . . 752
13.9. Границы Чернова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
13.10. Распределение нагрузки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756
Анализ случайного распределения заданий . . . . . . . . . . . . . . . . . . . . . . 757
13.11. Маршрутизация пакетов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 759
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763
13.12. Основные вероятностные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . 765
Конечные вероятностные пространства . . . . . . . . . . . . . . . . . . . . . . . . . . 765
Условная вероятность и независимость . . . . . . . . . . . . . . . . . . . . . . . . . . 767
Бесконечные пространства выборки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770
Упражнения с решениями . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
Упражнение с решением 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772
Упражнение с решением 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778
Примечания и дополнительная литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 789
Эпилог: алгоритмы, которые работают бесконечно . . . . . . . . . . . . . . . . . . 791
Задача . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 792
Разработка алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795
Анализ алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 799
Об авторах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800

С этой книгой чаще всего покупают:
Искусство программирования, Том 1. Основные алгоритмы

Искусство программирования, Том 1. Основные алгоритмы

рекомендуем
Кнут Дональд
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
 
Алгоритмы: построение и анализ, 3-е издание

Алгоритмы: построение и анализ, 3-е издание

рекомендуем
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
Цена: 1050.00 грн. 
 
Цена: 1400.00 грн. 
Конкретная математика. Математические основы информатики

Конкретная математика. Математические основы информатики

рекомендуем
Рональд Л. Грэхем, Дональд Э. Кнут, Орен Паташник
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
 
Введение в теорию автоматов, языков и вычислений. 2-е издание

Введение в теорию автоматов, языков и вычислений. 2-е издание

Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
Цена: 1050.00 грн. 
 
Цена: 800.00 грн. 
Алгоритмы: вводный курс

Алгоритмы: вводный курс

рекомендуем
Томас Х. Кормен
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
 
Алгоритмы на Java

Алгоритмы на Java

рекомендуем
Роберт Седжвик, Кевин Уэйн
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
Цена: 485.00 грн. 
 
Цена: 1050.00 грн. 
Алгоритмы на C++

Алгоритмы на C++

рекомендуем
Роберт Седжвик
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
 
Алгоритмические трюки для программистов

Алгоритмические трюки для программистов

рекомендуем
Генри С. Уоррен
Год выпуска: 2016
Изд-во: Диалектика-Вильямс
в корзину
Только на 1 книгу
Цена: 1050.00 грн. 
 
Цена: 485.00 грн. 
Структуры данных и алгоритмы

Структуры данных и алгоритмы

рекомендуем
Альфред Ахо, Джон Хопкрофт, Джеффри Ульман
Год выпуска: 2018
Изд-во: Диалектика-Вильямс

в корзину

Instant Purshare Только на 1 книгу
 
   
Цена: 310.00 грн. 
   

Хотите оставить отзыв? У Вас возникли вопросы о книге "Алгоритмы: разработка и применение. Классика Computers Science, Клейнберг Д., Тардос Е." ? Пишите:

* Текст сообщения:
 
  Отправить
Поиск по каталогу
 поиск в аннотациях
Искать

* Подробнее об условиях доставки смотрите в разделе "Оплата и Доставка" нашего магазина.
Если у Вас возникли вопросы как подобрать и купить книги в нашем интернет-магазине звоните с 9 до 18 по будним дням: Киев 331-04-53, Водафон (050) 809-56-66, Киевстар (067) 408-26-36, Лайф (063) 227-24-47, Интертелеком (094) 831-04-53 или пишите нам

 
   
  Programming - Dmitriy Kotov & Andrey Kotov