Теоретический семинар (осень 2011)

Д. Сердюк

Графические модели: фактор-графы

На данной лекции будет введено понятие фактор-графа, маргинальных функций, соответствующих данной функции. Далее будет рассмотрен sum-product алгоритм для вычисления всех маргмнальных фунуций. В конце будет продемонстрировано, каким образом фактор-графы были применены для рейтинговой системы TrueSkill.

F.Kschischang Factor Graps and the Sum-Product Algorithm.
R.Herbrich, T.Minka, T.Graepel TrueSkill: A Bayesian Skill Rating System.

Байесовские сети

В докладе будет дано определение байесовской сети, введено понятие d-separation, показаны некоторые свойства графов и соответствующих им распределений.

R. Neapolitan. Learning Bayesian Networks

Д. Тугарёв

О полных односторонних функциях

Будут представлены полные односторонних функции, основаннные на:

  • задаче поиска замощения;
  • полусистемах Туэ;
  • задаче Поста.

Будут формально представлены свойства, которыми должна обладать комбинаторная задача, чтобы на её основе можно было построить полную односторонюю функцию.

А.А.Кожевников, С.И. Николенко Проблемы передачи информации 2009 Вып.2 Т.45 О полных односторонних функциях.

В. Опарин

Priority Branching Trees. Lower bounds for schedule and knapsack problems

Priority Branching Tree (pBT) --- модель вычисления, предназначенная для оценки времени работы бэктрекинга и алгоритмов на основе динамического программирования.
В докладе буду показаны нижние оценки на pBT для задачи о рюкзаке и составлении расписаний.

Alekhnovich, Borodin, Buresh-Oppenheim, Impagliazzo, Magen, Pitassi "Toward a Model for Backtracking and Dynamic Programming"

А. Бешéнов

Оценка на числа Бетти полуалгебраических множеств, определенных над квадратичными отображениями

3 ноября 2011 г.

Пусть $R$ — вещественно замкнутое поле, а $Q\colon R^n \to R^k$ — квадратичное отображение. Пусть заданы $s$ полиномов от $k$ переменных $Y_1, \ldots, Y_k$, каждый степени не более $d$:

$$\mathcal{P} \mathrel{\mathop:}= \{ p_1, \ldots, p_s \},\quad p_i \in R [Y_1, \ldots, Y_k],\quad\deg p_i \le d.$$

Пусть также имеется бескванторная булева формула $S (Y_1, \ldots, Y_k)$, атомы которой имеют вид

А. Тимофеев

Монотонные схемы: односторонние функции и псевдослучайные генераторы

На докладе будет разобрана одноименная статья Oded Goldreich и Rani Izrak.
(в свободном доступе: http://www.wisdom.weizmann.ac.il/~oded/PDF/mono-cry.pdf)

Основными результатами являются:

И. Близнец

Новый алгоритм для FormulaSAT и нижняя оценка Субботовской

Будет рассказана идея с помощью которой можно получить нижнюю оценку на размер формулы (Субботовская), а также использующаяся для доказательства оценки сверху на время работы алгоритма для FormulaSAT.

А. Головнёв

Точные и приближённые алгоритмы решения задачи о коммивояжёре (TSP)

М. Гладких

Вычисление редакционного расстояния между деревьями на основе стягивания вершин

На семинаре будет введена новая метрика в пространстве филогенетических деревьев и будут представлены 2 алгоритма её вычисления вместе с интересными подзадачами.

Страницы