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

Description

Предисловие Введение Глава Алгоритмы и их сложность Примеры задач и алгоритмов Теоретико-числовые задачи: «НОД», «факториал», «возведение в степень», «дискретный логарифм» Задачи на графах: «Коммивояжер», «Кратчайшие пути», «Остовные деревья» Приближенные алгоритмы: «Составление расписаний» «Сортировка слиянием» «Быстрая сортировка» Формально об алгоритмах. Несложно о сложности «RAM»: машины с произвольным доступом Сложность в худшем случае Сложность в среднем Полиномиальные алгоритмы Полиномиальность и эффективность Глава Аппроксимация с гарантированной точностью Алгоритмы с оценками точности Жадные алгоритмы для «Покрытия множеств» Приближенные алгоритмы для «Вершинного покрытия» Жадный алгоритм для «Рюкзака» Алгоритм Кристофидеса Аппроксимация с заданной точностью «Рюкзак»: динамическое программирование Полностью полиномиальная приближенная схема для «Рюкзака» Глава Вероятностный анализ алгоритмов Сложность и полиномиальность в среднем Задача упаковки Выполнимость КНФ Точность алгоритма для почти всех входов «Рюкзак»: полиномиальность в среднем Глава Вероятностные алгоритмы и их анализ Вероятностная проверка тождеств Вероятностные методы в перечислительных задачах Вероятностные методы в параллельных вычислениях Максимальное по включению независимое множество в графе Протокол византийского соглашения Вероятностное округление Вероятностное округление для задачи Максимальный разрез в графе Глава Методы дерандомизации Метод условных вероятностей Метод малых вероятностных пространств Глава Основы теории сложности вычислений Сложность вычислений Машины Тьюринга и вычислимость Классы DTIME, DSPACE Полиномиальные сводимости и NP-полнота Сводимость по Куку Недетерминированные алгоритмы Сводимость по Карпу Вероятностные вычисления Классы RP/coRP. «Односторонние ошибки» Класс BPP. «Двусторонние ошибки» Класс PP Класс ZPP. «Алгоритмы без ошибок» Вероятностно проверяемые доказательства PCP и неаппроксимируемость Класс APX. Сводимости, сохраняющие аппроксимации Схемы и схемная сложность Коммуникационная сложность Диаграмма классов сложности Глава Приложения Введение в Python Глоссарий Глава Сборник упражнений (ИСПРАН-2008-весна) Список литературы Списки иллюстраций Список алгоритмов