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

Разделы

Комбинаторная теория игр

Семестровый курс по выбору.

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

Проходит: по средам с 17:05 до 18:30, первое занятие 14 сентября. Аудитория: 419 ГК.

Лектор: Мусатов Даниил Владимирович.

На курс приглашаются студенты 1 — 6 курсов, аспиранты и все желающие. Специальной подготовки не требуется, зато нужно желание и умение получать удовольствие от занятия математикой.

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

Ним: На столе есть несколько куч камней. Двое по очереди берут любое (положительное) количество камней, но только из одной кучи. Выигрывает взявший последние камни.

Кусторезка: На плоскости изображён граф с красными и синими рёбрами, некоторые из которых прикреплены к «земле». Двое по очереди удаляют рёбра: один синие, другой красные. Если часть графа утратила связь с «землёй», она также исчезает. Проигрывает тот, у кого не осталось рёбер соответствующего цвета.

Доминирование: Двое выкладывают доминошки на клетки шахматной доски, первый вертикально, второй горизонтально, при этом класть доминошки друг на друга запрещено. Игрок, который не сможет сделать ход, проиграет.

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

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

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