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

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

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

Курс состоит из нескольких тем, относящихся к теории игр и алгоритмической сложности решения игр. Предварительного знания основных определений и фактов в теории игр не требуется: они будут, хотя бы кратко, рассказаны.

В начале будут рассказаны классические результаты о решении конечных игр и приведены примеры PSPACE-полных игр. Далее будет обсуждено (не-)существование выигрышных стратегий для бесконечных игр и дано доказательство существования особо простых стратегий (позиционные стратегии, стратегии с конечной памятью) для игр из нескольких интересных классов: игры чётности, циклические игры, простые стохастические игры. Существование таких стратегий имеет важные следствия для алгоритмической сложности решения таких игр, помещая эту задачу в пересечение классов NP и coNP. Основной темой курса является изложение недавно придуманных квазиполиномиальных алгоритмов для решения игр чётности. Для циклических игр будут рассказаны вероятностные субэкспоненциальные алгоритмы (лучше пока не получается).

Для понимания курса желательно знакомство с основными понятиями теории сложности вычислений: машины Тьюринга, основные сложностные классы, понятие сводимости. Текст содержит лишь короткие напоминания по этим вопросам. Для более подробного ознакомления с теорией сложности рекомендуются стандартные учебники, например, Сипсера или Ароры и Барака. Желательно также знакомство с базовыми алгоритмами (топологическая сортировка, построение кратчайших путей и т.п.).

Дата и время Занятие Место Материалы
09 ноября
17:15–18:45
Лекция 1, Лекция ПОМИ РАН слайды,  видеофайлы
09 ноября
19:00–20:30
Лекция 2, Лекция ПОМИ РАН слайды,  видео
10 ноября
11:15–12:45
Лекция 3, Лекция ПОМИ РАН слайды,  видео
10 ноября
13:00–14:30
Лекция 4, Лекция ПОМИ РАН слайды,  видео
10 ноября
15:30–17:00
Лекция 5, Лекция ПОМИ РАН слайды,  видео
16 ноября
17:15–18:45
Лекция 6, Лекция ПОМИ РАН слайды,  видео
16 ноября
19:00–20:30
Лекция 7, Лекция ПОМИ РАН слайды,  видео
17 ноября
11:15–12:45
Лекция 8, Лекция ПОМИ РАН слайды,  видео
17 ноября
13:00–14:30
Лекция 9, Лекция ПОМИ РАН слайды,  видео
17 ноября
15:30–17:00
Лекция 10, Лекция ПОМИ РАН слайды,  видео