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