[Коллоквиум]: Раскраски гиперграфов и смежные проблемы: вероятностно-алгоритмический подход

594 views · Published 26 October 2016 · 1:18:14 · Indexed 10 November 2026

Channel: ФКН ВШЭ · 2016 · Education

Watch on YouTube

Докладчик: Дмитрий Шабанов - ФКН ВШЭ/МФТИ

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

More from this channel