City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Foundations of computability and complexity theory
Saint Petersburg / autumn 2012, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

Date and time Class|Name Venue|short Materials
12 September
18:30–19:50
Разрешимые и перечислимые множества. Классы P и NP, Lecture ПОМИ РАН video
12 September
18:30–19:50
Разрешимые и перечислимые множества. Классы P и NP, Lecture ПОМИ РАН No
19 September
18:30–19:50
Вычислимые функции, Lecture ФМЛ 239, Актовый зал video
19 September
18:30–19:50
Вычислимые функции, Lecture ПОМИ РАН No
03 October
18:30–19:50
Теорема о неподвижной точке. Машины Тьюринга, Lecture ПОМИ РАН video
03 October
18:30–19:50
Теорема о неподвижной точке. Машины Тьюринга, Lecture ПОМИ РАН No
10 October
18:30–19:50
Вычислимость и выразимость в арифметике, Lecture ПОМИ РАН video
10 October
18:30–19:50
Вычислимость и выразимость в арифметике, Lecture ПОМИ РАН No
17 October
18:30–19:50
Арифметическая иерархия. Колмогоровская сложность, Lecture ПОМИ РАН No
17 October
18:30–19:50
Арифметическая иерархия. Колмогоровская сложность, Lecture ФМЛ 239, Актовый зал video
24 October
18:30–19:50
Моделирование машин Тьюринга. Недетерминированные машины Тьюринга, Lecture ПОМИ РАН video
24 October
18:30–19:50
Моделирование машин Тьюринга. Недетерминированные машины Тьюринга, Lecture ПОМИ РАН No
31 October
18:30–19:50
О классе NP, Lecture ПОМИ РАН No
31 October
18:30–19:50
О классе NP, Lecture ПОМИ РАН video
07 November
18:30–19:50
P vs NP с оракулами. Иерархии по времени, Lecture ПОМИ РАН video
07 November
18:30–19:50
P vs NP с оракулами. Иерархии по времени, Lecture ПОМИ РАН No
14 November
18:30–19:50
Вычисления с ограничениями по памяти, Lecture ПОМИ РАН video
14 November
18:30–19:50
Вычисления с ограничениями по памяти, Lecture ПОМИ РАН No
21 November
18:30–19:50
Полиномиальная иерархия, Lecture ПОМИ РАН video
21 November
18:30–19:50
Полиномиальная иерархия, Lecture ПОМИ РАН No
28 November
18:30–19:50
Нижние оценки для SAT. Схемная сложность, Lecture ПОМИ РАН No
28 November
18:30–19:50
Нижние оценки для SAT. Схемная сложность, Lecture ПОМИ РАН video
05 December
18:30–19:50
Схемы и параллельные вычисления, Lecture ПОМИ РАН No
05 December
18:30–19:50
Схемы и параллельные вычисления, Lecture ПОМИ РАН video