Author(s): Кузюрин Н.Н., Фомин С.А.
Year: 2008
Language: Russian
Commentary: 51417
Pages: 326
Введение......Page 5
Теоретико-числовые задачи: «НОД», «факториал», «возведение в степень», «дискретный логарифм»......Page 16
Задачи на графах: «Коммивояжер», «Кратчайшие пути», «Остовные деревья»......Page 22
Приближенные алгоритмы: «Составление расписаний»......Page 37
«Сортировка слиянием»......Page 41
«Быстрая сортировка»......Page 44
«RAM»: машины с произвольным доступом......Page 49
Сложность в худшем случае......Page 55
Полиномиальные алгоритмы......Page 58
Полиномиальность и эффективность......Page 63
Алгоритмы с оценками точности......Page 65
Жадные алгоритмы для «Покрытия множеств»......Page 66
Приближенные алгоритмы для «Вершинного покрытия»......Page 72
Жадный алгоритм для «Рюкзака»......Page 79
Алгоритм Кристофидеса......Page 83
«Рюкзак»: динамическое программирование......Page 91
Полностью полиномиальная приближенная схема для «Рюкзака»......Page 99
Сложность и полиномиальность в среднем......Page 106
Задача упаковки......Page 109
Выполнимость КНФ......Page 115
Точность алгоритма для почти всех входов......Page 122
«Рюкзак»: полиномиальность в среднем......Page 127
Вероятностная проверка тождеств......Page 136
Вероятностные методы в перечислительных задачах......Page 140
Максимальное по включению независимое множество в графе......Page 147
Протокол византийского соглашения......Page 156
Вероятностное округление для задачи <>......Page 161
Максимальный разрез в графе......Page 167
Метод условных вероятностей......Page 176
Метод малых вероятностных пространств......Page 180
Машины Тьюринга и вычислимость......Page 198
Классы DTIME, DSPACE......Page 216
Сводимость по Куку......Page 221
Недетерминированные алгоритмы......Page 224
Сводимость по Карпу......Page 229
Вероятностные вычисления......Page 240
Классы RP/coRP. «Односторонние ошибки»......Page 243
Класс BPP. «Двусторонние ошибки»......Page 249
Класс PP......Page 253
Класс ZPP. «Алгоритмы без ошибок»......Page 257
Вероятностно проверяемые доказательства......Page 259
PCP и неаппроксимируемость......Page 267
Класс APX. Сводимости, сохраняющие аппроксимации......Page 273
Схемы и схемная сложность......Page 284
Коммуникационная сложность......Page 292
Диаграмма классов сложности......Page 297
Введение в Python......Page 300
Глоссарий......Page 305
Список литературы......Page 307
Предметный указатель......Page 314
Списки иллюстраций......Page 323
Список алгоритмов......Page 325
