Эффективные алгоритмы и сложность вычислений (12 июня 2011 г.)

Description

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