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

А. Тимофеев

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

В докладе будут представлены несколько результатов в области преобразования наборов замкнутых контуров (многоугольников) и планарных укладок графов.

Задача поиска преобразования (морфинга) будет разобрана в нескольких различных постановках, от очень узких классов (ортогонально-выпуклых многоугольников и монотонного морфинга на них), где она оказывается NP-трудной, до очень общего случая допускающего набор непростых многоугольников с "дырками".

Ф. Парт (Академический университет)

Parameterized complexity

Доклад посвящен основам parameterized complexity. Первая часть доклада будет
посвящена иерархии замкнутых относительно сведения классов параметризованных
задач W[k]. Во второй части будет рассказано как из предположений о
неравенстве некоторых классов W[k] можно получать неприближаемости
аппроксимационными схемами тех или иных задач, а также о нижних оценках на
ядра.

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

Нижние оценки на схемную сложность

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

Сжатие строк

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Страницы