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

Кузюрин Н.Н., Фомин С.А.

Table of contents :
Введение……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