Вадим Владиславович Лозин (Университет Ворвика, Великобритания) сделает доклад на семинаре лаборатории
Профессор Вадим Владиславович Лозин (Университет Ворвика, Великобритания) выступит с докладом "Клики, раскраски и выполнимость: от структуры к алгоритмам" на очередном семинаре лаборатории, который состоится 4 июня в 14:00
Аннотация:
Задачи о клике, раскраске и выполнимости - три центральных задачи теоретической информатики. Все эти задачи в общем случае NP-трудные. С другой стороны, каждая из них может стать полиномиально разрешимой при рассмотрении входных объектов определенной структуры. В этом докладе исследуется вопрос о том, как структура входных данных может влиять на вычислительную сложность этих задач. Также обсуждаются некоторые алгоритмические средства для решения рассматриваемыхзадач. Особое внимание уделяется преобразованиям графов и конъюнктивных нормальных форм (КНФ).
Место проведения семинара: ул. Родионова,136, ауд.401.Приглашаются все желающие!