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