Семинары: Дмитрий Шабанов, Раскраски гиперграфов и смежные проблемы: вероятностно-алгоритмический подход

СЕМИНАРЫ


Коллоквиум Факультета компьютерных наук НИУ ВШЭ 25 октября 2016 г. 18:10, г. Москва, Кочновский проезд 3, аудитория 622

Раскраски гиперграфов и смежные проблемы: вероятностно-алгоритмический подход Дмитрий Шабанов Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
https://www.youtube.com/watch?v=H0zbsOBvdT0 Аннотация: Ряд известных задач комбинаторики и теоретической информатики (например, задача $k$-SAT, задача об оценках чисел Рамсея и др.) могут быть сформулированы в абстрактных терминах раскрасок однородных гиперграфов. В докладе будут представлены классические комбинаторные постановки подобных задач и будет рассказано о последних достижениях в их решении. Мы обсудим вероятностные алгоритмы, с помощью которых были получены новые результаты, а также вопрос их практической реализации.