С: 06.05.2026 18:30 по: 06.05.2026 20:05

В среду, 6 мая, в 18:30 в аудитории 1213 на заседании кафедрального семинара "Теория автоматов" состоится доклад Д.Н. Жука "Минионы и алгоритмы для решения задачи удовлетворения ограничениям".

Заседание состоится в 18:30 в смешанном формате. Очная часть пройдет в аудитории 1213 Главного здания МГУ, дистанционная – в zoom-конференции https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlVKcytzTU96VFlSNFZ6dz09.

Анонс доклада:

Открытия 2025 года показали, что почти любой универсальный алгоритм для задачи удовлетворения ограничениям задается абстрактным минионом, а применимость алгоритма зависит от существования гомоморфизма минионов. В докладе мы покажем, как абстрактные минионы возникают из замкнутых классов функций k-значной логики, продемонстрируем на примерах, как минионы задают конкретные алгоритмы. На примере классификации Шефера мы покажем, как наличие гомоморфизма минионов связано с применимостью алгоритма. В конце мы сформулируем конкретные (почти комбинаторные) вопросы, решение которых станет прорывом в теории алгоритмов.