Город: Санкт-Петербург Казань Язык: Русский English

Основы вычислимости и теории сложности
Санкт-Петербург / осень 2012, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

Дата и время Название Место Материалы
12 сентября
18:30–19:50
Разрешимые и перечислимые множества. Классы P и NP, лекция ПОМИ РАН видео
12 сентября
18:30–19:50
Разрешимые и перечислимые множества. Классы P и NP, лекция ПОМИ РАН Нет
19 сентября
18:30–19:50
Вычислимые функции, лекция ФМЛ 239, Актовый зал видео
19 сентября
18:30–19:50
Вычислимые функции, лекция ПОМИ РАН Нет
03 октября
18:30–19:50
Теорема о неподвижной точке. Машины Тьюринга, лекция ПОМИ РАН Нет
03 октября
18:30–19:50
Теорема о неподвижной точке. Машины Тьюринга, лекция ПОМИ РАН видео
10 октября
18:30–19:50
Вычислимость и выразимость в арифметике, лекция ПОМИ РАН Нет
10 октября
18:30–19:50
Вычислимость и выразимость в арифметике, лекция ПОМИ РАН видео
17 октября
18:30–19:50
Арифметическая иерархия. Колмогоровская сложность, лекция ФМЛ 239, Актовый зал видео
17 октября
18:30–19:50
Арифметическая иерархия. Колмогоровская сложность, лекция ПОМИ РАН Нет
24 октября
18:30–19:50
Моделирование машин Тьюринга. Недетерминированные машины Тьюринга, лекция ПОМИ РАН Нет
24 октября
18:30–19:50
Моделирование машин Тьюринга. Недетерминированные машины Тьюринга, лекция ПОМИ РАН видео
31 октября
18:30–19:50
О классе NP, лекция ПОМИ РАН Нет
31 октября
18:30–19:50
О классе NP, лекция ПОМИ РАН видео
07 ноября
18:30–19:50
P vs NP с оракулами. Иерархии по времени, лекция ПОМИ РАН Нет
07 ноября
18:30–19:50
P vs NP с оракулами. Иерархии по времени, лекция ПОМИ РАН видео
14 ноября
18:30–19:50
Вычисления с ограничениями по памяти, лекция ПОМИ РАН видео
14 ноября
18:30–19:50
Вычисления с ограничениями по памяти, лекция ПОМИ РАН Нет
21 ноября
18:30–19:50
Полиномиальная иерархия, лекция ПОМИ РАН видео
21 ноября
18:30–19:50
Полиномиальная иерархия, лекция ПОМИ РАН Нет
28 ноября
18:30–19:50
Нижние оценки для SAT. Схемная сложность, лекция ПОМИ РАН видео
28 ноября
18:30–19:50
Нижние оценки для SAT. Схемная сложность, лекция ПОМИ РАН Нет
05 декабря
18:30–19:50
Схемы и параллельные вычисления, лекция ПОМИ РАН видео
05 декабря
18:30–19:50
Схемы и параллельные вычисления, лекция ПОМИ РАН Нет