Читать онлайн «Эффективные алгоритмы и сложность вычислений»

Эффективные алгоритмы и сложность вычислений Н. Н. Кузюрин С. А. Фомин 29 февраля 2016 г. Оглавление Предисловие 6 Введение 8 1 Алгоритмы и их сложность 15 1. 1 Примеры задач и алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1. 1. 1 Теоретико-числовые задачи: «НОД», «факториал», «возведение в степень», «дис- кретный логарифм» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1. 1. 2 Задачи на графах: «Коммивояжер», «Кратчайшие пути», «Остовные деревья» . . . 22 1. 1. 3 Приближенные алгоритмы: «Составление расписаний» . . . . . . . . . . . . . . . . 37 1. 1. 4 «Сортировка слиянием» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 1. 1. 5 «Быстрая сортировка» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 1. 2 Формально об алгоритмах. Несложно о сложности . . . . . . . . . . . . . . . . . . . . . . . 47 1. 2. 1 «RAM»: машины с произвольным доступом . . . . . . . . . . . . . . . . . . . . . . 47 1. 2. 2 Сложность в худшем случае . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2 ОГЛАВЛЕНИЕ 3 1. 2. 3 Сложность в среднем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 1. 2. 4 Полиномиальные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 1. 2. 5 Полиномиальность и эффективность . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2 Аппроксимация с гарантированной точностью 72 2. 1 Алгоритмы с оценками точности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2. 1. 1 Жадные алгоритмы для «Покрытия множеств» . . . . . . . . . . . . . . . . . . . . . 74 2. 1. 2 Приближенные алгоритмы для «Вершинного покрытия» . . . . . . . . . . . . . . . 79 2. 1. 3 Жадный алгоритм для «Рюкзака» . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2. 1. 4 Алгоритм Кристофидеса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 2. 2 Аппроксимация с заданной точностью . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 2. 2. 1 «Рюкзак»: динамическое программирование . . . . . . . . . . . . . . . . . . . . . 94 2. 2. 2 Полностью полиномиальная приближенная схема для «Рюкзака» . . . . . . . . . . 100 3 Вероятностный анализ детерминированных алгоритмов 122 3. 1 Сложность и полиномиальность в среднем . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 3. 2 Задача упаковки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 3. 3 Выполнимость КНФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 3. 4 Точность алгоритма для почти всех входов . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 3. 5 «Рюкзак»: полиномиальность в среднем . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 4 Вероятностные алгоритмы и их анализ 161 4. 1 Вероятностная проверка тождеств . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 4. 2 Вероятностные методы в перечислительных задачах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 4 ОГЛАВЛЕНИЕ 4. 3 Вероятностные методы в параллельных вычислениях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 4. 3. 1 Максимальное по включению независимое множество в графе . . . . . . . . . . . 174 4. 3. 2 Протокол византийского соглашения . . . . . . . . . . . . . . . . . . . . . . . . . . 184 4. 4 Вероятностное округление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 4. 4. 1 Вероятностное округление для задачи «MAX-SAT» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 4. 4. 2 Максимальный разрез в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 5 Методы дерандомизации 207 5. 1 Метод условных вероятностей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207 5. 2 Метод малых вероятностных пространств . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 5. 3 Полиномиальная проверка простоты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 6 Основы теории сложности вычислений 232 6. 1 Сложность вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 6. 1. 1 Машины Тьюринга и вычислимость . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 6. 1. 2 Классы DT IME, DSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 6. 2 Полиномиальные сводимости и N P-полнота . . . . . . . . . . . . . . . . . . . . . . . . . . 252 6. 2. 1 Сводимость по Куку . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 6. 2. 2 Недетерминированные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . 255 6. 2. 3 Сводимость по Карпу . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 6. 3 Вероятностные вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 6. 3. 1 Классы RP/coRP.