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

10 февраля, четверг, 16-00, к.203 (ПОМИ РАН)

Д. Соколов (Академический Университет)

Трудные примеры для эвристических близоруких DPLL алгоритмов.

В докладе будут рассмотрены ``близорукие'' DPLL алгоритмы с
возможностью отсечения ветвей дерева расщепления. Будет построено
семейство пар (невыполнимая формула, распределение на выполнимых
формулах) для любого количества переменных такое, что либо
математическое ожидание времени работы на невыполнимой формуле не менее
$(1 - \epsilon) 2^{n}$, где $n$ число переменных, либо вероятность
правильной работы на распределении не более $(1 - \epsilon)$.

Доклад основан на совместных результатах докладчика с Д. М. Ицыксоном.

17 февраля, четверг, 16-00, к.203 (ПОМИ РАН)

Д. Соколов (Академический Университет)

Трудные примеры для эвристических близоруких DPLL алгоритмов. (продолжение)

Доказательство теоремы, анонсированной на прошлом семинаре.

24 февраля, четверг, 16-00, к.203 (ПОМИ РАН)

А. Бешенов (Академический Университет)

Вычисления в алгебрах

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

Рассказ по обзору
Gabor Ivanyos, Lajos Ronyai,
Computations in Associative and Lie Algebras.
// Some Tapas of Computer Algebra
(Algorithms and Computation in Mathematics).

Слайды

3 марта, четверг, 16-00, к.106 или 203 (ПОМИ РАН)

А. Бешенов (Академический Университет)

Вычисления в алгебрах (продолжение)

Продолжение доклада (на прошлом семинаре были определены основные понятия).

10 марта, четверг, 16-00, к.106 или 203 (ПОМИ РАН)

С. Исакова (Академический Университет)

Типизированное лямбда-исчисление

В докладе будет рассказано, что такое изоморфизм Карри-Говарда. Это прямое
соответствие между формулами и доказательствами в интуиционистской логике и
программами (термами) и их типами в типизированном лямбда-исчислении. Будут
введены все необходимые для этого определения и понятия. В завершении будет
показано, как задача QBF сводится к задаче построения терма с заданным
типом.

17 марта, четверг, 16-00, к.106 или 203 (ПОМИ РАН)

И. Близнец (Академический университет)

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

В докладе будут рассказаны некоторые алгоритмы касающиеся задачи MAX-SAT. А именно:
1) Алгоритм Вильямса для MAX-2-SAT.
2) Простой алгоритм для (n,3)-MAX-SAT, с оценкой времени работы в зависимости от количества клозов.
3) Обзор самого быстрого алгоритма для MAX-SAT, предложенного Ченом и Канжем (Jianer Chen, Iyad A. Kanj).

24 марта, четверг, 16-00, к.106 или 203 (ПОМИ РАН)

В. Опарин (Академический университет)

Эффективный Nullstellensatz

В докладе будет рассказано о верхних и нижних оценках на многочлены в
равенстве Безу; изложены идеи алгоритма их поиска.

31 марта, четверг, 16-00, к.203 (ПОМИ РАН)

В. Опарин (Академический университет)

Эффективный Nullstellensatz (продолжение)

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

7 апреля, четверг, 16-00, к.203 (ПОМИ РАН)

А. Головнев (Академический университет)

Эффективное решение MAX-2-SAT

В докладе будут рассмотрены лучшие известные алгоритмы для задач MAX
2-SAT, MAX 2-CSP, MAX CUT.
Будут предложены новые алгоритмы решения этих задач. В частности,
будет рассмотрен алгоритм решения задачи MAX 2-SAT с оценкой сложности
$O^*(2^{n(1-3.677/(d+1))})$.

14 апреля, четверг, 16-00, к.203 (ПОМИ РАН)

А. Давыдов (Академический университет)

Сжатие строк

В докладе будет рассказано о сжатии строк с помощью NSLP, также о сложности некоторых классических групповых задач. Будут поставлены вопросы о сложности аналогичных задач на
сжатых строках.