Теоретический семинар

10 апреля, вторник, 10-00, к.431 (АУ)

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

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

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

3 апреля, вторник, 10-00, к.431 (АУ)

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

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

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

27 марта, вторник, 10-00, к.431 (АУ)

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

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

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

Как окажется, любое резолюционное доказательство можно проэмулировать SAT-солвером, раздув его не более чем в полином.

Доклад по статье Knot Pipatsrisawat and Adnan Darwiche "On the Power of Clause-Learning SAT Solvers with Restarts".

13 марта, вторник, 10-00, к.431 (АУ)

Лёша Бешенов

Формулы Бриона

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

6 марта, вторник, 10-00, к.431 (АУ)

Лёша Бешенов

Формулы Бриона

В недавней работе Гравина, Лассерра, Пасечника и Робинса http://arxiv.org/abs/1106.5723 исследуется задача восстановления для выпуклых многогранников по моментам. Новый метод из этой статьи опирается на то, что авторы называют "тождества Бриона--Лоуренса--Хованского--Пухликова--Барвинка". В своём докладе я объясню, что это за тождества и какая за ними стоит геометрия.

Рассказ по статье

Michel Brion, Points entitiers dans les polyèdres convexes.
Annales scientifiques de l’É.N.S. 4e série, tome 21, no 4 (1988), p. 653-663
http://www.numdam.org/item?id=ASENS_1988_4_21_4_653_0

21 февраля, вторник, 10-00, к.431 (АУ)

Алексей Давыдов

Контрпример к алгоритму Григорьева

На семинаре будет рассмотрена задача о решении линейных тропических систем. Несмотря на то, что задача была поставлена достаточно давно до сих пор неизвестно полиномиальных решений для нее. Один из известных псевдополиномиальных алгоритмов для решения данной задачи - алгоритм Григорьева. На семинаре будет рассмотрена серия матриц, на которых алгоритм работает экспоненциальное время.

14 февраля, вторник, 10-00, к.431 (АУ)

Марковские сети и их применения

Доклад посвящен марковским сетям -- классу графических моделей, основанных на неориентированных графах. Будет дано определение марковской сети, показаны основные свойства и приведены некоторые примеры применения.

7 сентября, вторник, 14:00

Ю. Беляева (АУ)
Поиск кратчайших путей в дорожной сети

В докладе будет рассказано об алгоритмах поиска кратчайшего пути в дорожных сетях. Широко известный алгоритм Дейкстры оказывается слишком медленным для поиска путей на больших дорожных сетях, таких, как дорожная сеть США или Европы. Алгоритмы с предобработкой в данном случае работают гораздо лучше: на первой стадии по карте подсчитывается вспомогательная информация, которая далее помогает быстро выполнять запросы. В лекции будут рассмотрены несколько вариантов подобных алгоритмов.

Доклад основан на лекциях, прочитанных Ренато Вернеком в рамках летней школы Microsoft Data Structures and Algorithms School (MIDAS) 2010 (http://logic.pdmi.ras.ru/midas).

21 сентября, вторник, 14:00

Д. Соколов (АУ)

Нижняя оценка длины доказательств

Доклад по статье:
Edward A. Hirsch, Sergey I. Nikolenko. "Simulating Cutting Plane proofs with restricted degree of falsity by Resolution."

В докладе будет рассмотрено доказательство нижней оценки на размер доказательства в
системе Cutting Plane для языка тавтологий. Будет продемонстрировано моделирование Cutting Plane
при помощи резолюций для ограниченной "степени ошибочности" неравенств.

29 сентября, вторник, 14:00, к.430

С. Капулкин (АУ)

Information retrieval

В докладе будут рассмотрены основные алгоритмы информационного поиска. В начале
будет рассказана общая конструкция поисковой машины на примере бинарного
поиска (boolean retrieval), далее рассматривается vector space model для
задачи ранжированного поиска, приводятся методы оценки поисковых систем.