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

Description

Титульный лист Оглавление Предисловие Введение 1 Алгоритмы и их сложность 1.1 Примеры задач и алгоритмов 1.1.1 Теоретико-числовые задачи: «НОД», «факториал», «возведение в степень», «дискретный логарифм» 1.1.2 Задачи на графах: «Коммивояжер», «Кратчайшие пути», «Остовные деревья» 1.1.3 Приближенные алгоритмы: «Составление расписаний» 1.1.4 «Сортировка слиянием» 1.1.5 «Быстрая сортировка» 1.2 Формально об алгоритмах. Несложно о сложности 1.2.1 «RAM»: машины с произвольным доступом 1.2.2 Сложность в худшем случае 1.2.3 Сложность в среднем 1.2.4 Полиномиальные алгоритмы 1.2.5 Полиномиальность и эффективность 2 Аппроксимация с гарантированной точностью 2.1 Алгоритмы с оценками точности 2.1.1 Жадные алгоритмы для «Покрытия множеств» 2.1.2 Приближенные алгоритмы для «Вершинного покрытия» 2.1.3 Жадный алгоритм для «Рюкзака» 2.1.4 Алгоритм Кристофидеса 2.2 Аппроксимация с заданной точностью 2.2.1 «Рюкзак»: динамическое программирование 2.2.2 Полностью полиномиальная приближенная схема для «Рюкзака» 3 Вероятностный анализ детерминированных алгоритмов 3.1 Сложность и полиномиальность в среднем 3.2 Задача упаковки 3.3 Выполнимость КНФ 3.4 Точность алгоритма для почти всех входов 3.5 «Рюкзак»: полиномиальность в среднем 4 Вероятностные алгоритмы и их анализ 4.1 Вероятностная проверка тождеств 4.2 Вероятностные методы в перечислительных задачах 4.3 Вероятностные методы в параллельных вычислениях 4.3.1 Максимальное по включению независимое множество в графе 4.3.2 Протокол византийского соглашения 4.4 Вероятностное округление 4.4.1 Вероятностное округление для задачи «MAX-SAT» 4.4.2 Максимальный разрез в графе 5 Методы дерандомизации 5.1 Метод условных вероятностей 5.2 Метод малых вероятностных пространств 5.3 Полиномиальная проверка простоты 6 Основы теории сложности вычислений 6.1 Сложность вычислений 6.1.1 Машины Тьюринга и вычислимость 6.1.2 Классы DTIME, DSPACE 6.2 Полиномиальные сводимости и NP-полнота 6.2.1 Сводимость по Куку 6.2.2 Недетерминированные алгоритмы 6.2.3 Сводимость по Карпу 6.3 Вероятностные вычисления 6.3.1 Классы RP/coRP. «Односторонние ошибки» 6.3.2 Класс BPP. «Двусторонние ошибки» 6.3.3 Класс PP 6.3.4 Класс ZPP. «Алгоритмы без ошибок» 6.3.5 Вероятностно проверяемые доказательства 6.3.6 PCP и неаппроксимируемость 6.3.7 Класс APX. Сводимости, сохраняющие аппроксимации 6.4 Схемы и схемная сложность 6.5 Коммуникационная сложность 6.6 Диаграмма классов сложности 7 Приложения 7.1 Введение в Python 7.2 Глоссарий Предметный указатель Списки иллюстраций Список алгоритмов