Основы вычислимости и теории сложности

Санкт-Петербург, осень 2012

Описание

Курс дает ответы на такие вопросы: Что такое алгоритм? Что такое эффективный алгоритм? Что такое доказательство? Как доказать, что нет алгоритма, который решит данную задачу? Как доказать, что что-то нельзя доказать? Как понять, что нет эффективного алгоритма для данной задачи? Что такое сложность объекта? Из курса можно узнать, что такое вычислимые функции, арифметическая иерархия, колмогоровская сложность, классы P, NP, PSPACE и пр., полиномиальная иерархия, схемная сложность, сложность с ограничением по памяти и многие другие интересные вещи.

Преподаватели

Список лекций

Разрешимые и перечислимые множества. Классы P и NP
Разрешимые и перечислимые множества. Классы P и NP
Вычислимые функции
Вычислимые функции
Теорема о неподвижной точке. Машины Тьюринга
Теорема о неподвижной точке. Машины Тьюринга
Вычислимость и выразимость в арифметике
Вычислимость и выразимость в арифметике
Арифметическая иерархия. Колмогоровская сложность
Арифметическая иерархия. Колмогоровская сложность
Моделирование машин Тьюринга. Недетерминированные машины Тьюринга
Моделирование машин Тьюринга. Недетерминированные машины Тьюринга
О классе NP
О классе NP
P vs NP с оракулами. Иерархии по времени
P vs NP с оракулами. Иерархии по времени
Вычисления с ограничениями по памяти
Вычисления с ограничениями по памяти
Полиномиальная иерархия
Полиномиальная иерархия
Нижние оценки для SAT. Схемная сложность
Нижние оценки для SAT. Схемная сложность
Схемы и параллельные вычисления
Схемы и параллельные вычисления