Адрес e-mail:

Маргарита Ахмеджанова "Онлайн раскраски гиперграфов"

Семинар проводится совместно кафедрой дискретной математики ФИВТ МФТИ, кафедрой математических основ управления ФУПМ МФТИ и кафедрой высшей математики МФТИ.

На заседаниях семинара обсуждаются задачи современной комбинаторики, дискретной геометрии, теории кодирования, теории алгоритмов и др., а также их приложения.

Расписание семинаров доступно здесь.

На следующем семинаре 6 ноября состоится выступление Маргариты Ахмеджановой

"Онлайн раскраски гиперграфов"  

В докладе будет рассказано об одной увлекательной задаче, связанной одновременно с теорией игр и раскрасками гиперграфов.

  Рассмотрим следующую игру.
  1. Есть 2 игрока: Pusher и Remover, и есть 2 дороги, на каждой из которых отмечено n позиций: n, n-1,...,1, 0, 1, ...., n-1, n.
  2. В начале игры на каждой дороге стоит N фишек на позиции с номером n.
  3. Далее, в каждом раунде Pusher выбирает произвольное количество фишек на первой и второй дороге и сдвигает их на одну позицию вперед к 0. Remover после каждого хода Pushera удаляет все сдвинутые фишки в этом раунде, но только с одной дороги.
  4. Pusher выигрывает если хотя бы 1 фишка дошла до 0, Remover-если удалены все N фишек.

Можно легко доказать, что при N<2^n Remover имеет выйгрышную стратегию (http://www.ccs.neu.edu/home/jaa/papers/AslamDh93.pdf), а при N>8*2^n Pusher. В пару строк доказывается наличие стратегии у Pushera при N>n*2^n (https://arxiv.org/pdf/1506.01148.pdf). Теперь если рассмотреть другую задачу с 3 дорогами и Remover удаляет с 2 из 3 дорог, то есть только оценки 3^n и 4n*3^n (результат Хузиевой и Шабанова).


ID
CODE
NAME
PREVIEW_TEXT
DETAIL_TEXT
DETAIL_PICTURE
DATE_FROM
DATE_TILL
ADDRESS
EVENT_TYPE
/Workshop on graphs, networks, and their applications
/15th Workshop on Algorithms and Models for the Web Graph
/BigData approaches in genetics and brain imaging of complex human disorders
/The 8th International Conference on Network Analysis
/Маргарита Ахмеджанова "Онлайн раскраски гиперграфов"
/Geometry, Dynamics, Integrable Systems – GDIS 2018
/Optimization at work
/Big Data Conference 2018
/Презентация новой лаборатории когнитивных динамических систем ФПМИ
/Лекция «Платформа Hedera Hashgraph, или „Блокчейн 2.0“»
/Курс по выбору "Современные методы оптимизации"
/Ю.С. Ильяшенко "Навстречу глобальной теории бифуркаций на плоскости"
/Стохастический анализ в задачах
/150-ая рабочая научная сессия ученых и разработчиков Нейронет - "Котел идей"
/Лекции на тему «Scale-free networks» от профессора Нелли Литвак
/Conference on graphs, networks, and their applications
/Russian Workshop on Complexity and Model Theory
/3rd Hungarian-Russian Combinatorics workshop
/Лекция В.А. Быковского "Последовательности Сомоса и их приложения"
/Презентация кафедр ABBYY
/Лекция «Глобальная карьера для физтехов» от преподавателя кафедры РВК в МФТИ
/Рон Аарони "Цикл лекций по функциям выбора и топологической комбинаторике"
/Осенние математические чтения в Адыгее
/Воркшоп по оптимизации и приложениям
/Workshop on Complex Networks
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

МФТИ в социальных сетях