Доклад сотрудника ЯрГУ – в числе лучших на XXIV международной конференции MOTOR 2025 в Новосибирске

В докладе доказано, что Эволомино – новая головоломка от японского издательства Nikoli, известного по таким популярным головоломкам, как Судоку и Какуро – является NP-полной, то есть к ней за полиномиальное время сводится любая задача из класса NP. Таким образом, если будет найден эффективный алгоритм поиска решения Эволомино, он сможет применяться и к широкому спектру практических задач — от предсказания структуры белков по аминокислотной последовательности до подбора ключей шифрования в криптографических системах, которые могут быть представлены в виде игрового поля головоломки Эволомино.

— Изучение вычислительной сложности игр и головоломок – быстроразвивающаяся область теоретической информатики. С одной стороны, игры и головоломки предлагают увлекательные и доступные примеры задач для обучения теории и методов доказательства вычислительной сложности задач и алгоритмов. С другой стороны, понимание сложности задачи помогает в разработке эффективных алгоритмов решения головоломок и разработке выигрышных стратегий для комбинаторных игр с участием двух или более игроков, — подчеркнул Андрей Николаев.

Международная конференция MOTOR ежегодно проводится при поддержке Математического центра в Академгородке и собирает специалистов в области математического программирования, глобальной и дискретной оптимизации, теории вычислительной сложности, комбинаторных алгоритмов, оптимизации в машинном обучении и анализе данных, а также теории игр и математической экономики. В этом году конференция состоялась на базе Новосибирского государственного университета. В ней приняли участие ученые из 15 городов России, а также из Грузии, Ирана, Китая, Бразилии, США, Австралии и Азербайджана. В рамках мероприятия было представлено 11 пленарных и 145 секционных докладов. Шесть докладов, в том числе работа Андрея Николаева, были удостоены награды Best Paper Award.

← Возврат к списку