Теоретический семинар (весна 2012)

Александр Витвицкий

Реализация булевых функций на непересекающихся множествах переменных

Денис Тугарёв

Реализация булевых функций на непересекающихся множествах переменных

Продолжение доклада.

Максим Гладких

Universal Relation Problem

Будут рассмотрены коммуникационные протоколы для этой задачи, базирующиеся на разных идеях, и имеющие сложность до n + 2 бит. Будет также доказана нижняя оценка для этой задачи в n + 1 бит.

Саша Головнёв

Алгоритмы разбиения на множества и их применения

В докладе будут рассмотрены алгоритмы решения задач покрытия и разбиения множествами. Будут рассмотрены применения алгоритма для раскраски графа, поиска domatic number. На основе полученного алгоритма будет построена экспоненциальная схема приближений для задачи о поиске хроматического числа графа.

Доклад по статье Björklund, Husfeldt, Koivisto, Set Partitioning via Inclusion–Exclusion.

Иван Близнец

Алгоритм проверки выполимости для булевых формул над полным бинарным базисом

В лекции будет приведен алгоритм для определения выполнимости булевых формул с длиной ограниченной $cn$, где $c$ -
некоторая константа, и заданными над базисом $B_2$. Доклад основан на статье:
"A Satisfiability Algorithm and Average-Case Hardness for Formula over the Full Binary Basis".

Денис Тугарёв

Реализация булевых функций на непересекающихся множествах переменных

Дмитрий Сердюк

Подсчёт количества совершенных паросочетаний

В данной лекции будет рассмотрен алгоритм для подсчета количества совершенных паросочетаний в графе на n вершинах, который использует полиномиальную память и $O^*(2^{n / 2})$ время. Ранее для этой задачи были был известен алгоритм, использующий экспоненциальную памать и $O(1.619^n)$ время (Коивисто) и алгоритм, использующий полиномиальную память и $O(1.942^n)$ время (Недерлоф). На лекции будет представлен алгоритм для подсчета хафниана матрицы над любым кольцом $R$ за $O^*(2^n)$ время.

Антон Тимофеев

Построение прямолинейных скелетов многоугольников в 3D

В докладе будут рассмотрены варианты построения прямолинейных скелетов многоугольников в трехмерном пространстве в общем и нескольких частных случаях.

Всеволод Опарин

Мощность SAT-солверов с запоминанием клозов и перезапусками

Мы изучим работу SAT-солвера с запоминанием клозов на невыполнимых формулах. Алгоритм будет рассмотрен как система доказательств. Ключевой вопрос: достаточно ли сильна такая система, чтобы иметь доказательства невыполнимости настолько же короткие как резолюционные?

Страницы