2011/2012 — Весенний семестр

Разделы

Алгоритмическая теория игр

Спецкурс (нет информации о том, что курс засчитывается как курс по выбору).

Кафедра анализа данных (ФИВТ).

Проходит: по четвергам с 18:30 до 20:00, первое занятие 16 февраля. Аудитория: 416 ГК.

Лектор: асс. Д. В. Мусатов.

Курс рассчитан на студентов 2 — 6 курсов, аспирантов и всех желающих. Для понимания курса необходимо знать основы теории вероятностей, теории графов и теории алгоритмов. Знакомство с теорией сложности вычислений и с теорией игр желательно, но не обязательно.

Почему от постройки новой дороги пробки могут вырасти? Как организовать аукцион, чтобы получить максимальный доход? Почему от запрета на рекламу сигарет прибыли табачных фирм растут? Как формируются цены на рынке? Почему в развитых демократических системах программы разных партий почти не отличимы друг от друга? Как происходит эволюция? На эти и многие другие вопросы проливает свет мощная и красивая наука — теория игр.

Последнее десятилетие ознаменовалось масштабным сотрудничеством специалистов по теории игр и по теоретической информатике, в результате которого возникло новое направление — алгоритмическая теория игр. В этой дисциплине задачи, постановки которых даёт теория игр, анализируются с точки зрения вычислительной сложности и других алгоритмических аспектов. Направление может похвастаться как теоретическими успехами, так и масштабными приложениями. Например, в теории была полностью классифицирована задача поиска равновесия Нэша, а на практике многие страны начинают регулировать дорожное движение и парковку, основываясь на рекомендациях теории.

В первой части курса будет определена и проанализирована классическая концепция равновесия по Нэшу: мы докажем, что в конечной игре оно всегда существует, изучим различные алгоритмы его нахождения и проведём теоретико-сложностной анализ. Во второй части курса мы познакомимся с различными приложениями теории: к аукционам, рынкам, маршрутизации трафика и т. д.

Что развивает курс (данные для «Вектора»)

Алгоритмы и методы анализа данных (курс сфокусирован на этом)

Информация о развиваемых компетенциях занесена в систему для работы «Вектора». Поскольку занесение информации производится редакторами проекта, а не авторами курсов, информация может быть неполной или даже частично неверной. Если Вы нашли ошибку, напишите нам об этом. См. также подробнее о системе «Вектор» и полный список компетенций.