Mathematical Logic and Discrete Mathematics at PDMI

Пятница, 11 мая, комната 106. Начало в 17:00.

Докладчик: Г. В. Давыдов, И. М. Давыдова.

ПОДСЧЕТ МЕРЫ ПРОПОЗИЦИОНАЛЬНЫХ ФОРМУЛ
Формуле F в КНФ сопоставляется мера m(F) так, что условие m(F) = 1 эквивалентно невыполнимости $F$. Для подсчета меры предлагается последовательное ипользование принципа "включения-исключения". Классы формул, для которых предложенный метод полиномиален, характеризуются в терминах структуры графа совместности, соответствующего формуле $F$.

Пятница, 27 апреля, комната 106. Начало в 17:00.

пятница, 27 апреля 2001 г., 17:00, к.106
Состоится ДВА доклада.
17:00. Докладчик: С.Норин
НИЖНЯЯ ОЦЕНКА ДЛЯ K-ОГРАНИЧЕННЫХ НЕЗАВИСИМЫХ ОТНОСИТЕЛЬНО МИНИМУМА СЕМЕЙСТВ ПЕРЕСТАНОВОК
Семейство C перестановок чисел от 1 до n называется k-ограниченным независимым относительно минимума, если для любого X - набора чисел от 1 до n, такого, что |X|<=k, и любого x из X Pr(min{p(X)}=p(x))=(1/|X|), где |X| - число элементов множества X, p - перестановка из С.
Будет приведено доказательство полиномиальной нижней оценки для k-ограниченных независимых относительно минимума семейств перестановок, что значительно улучшает ранее известные оценки.
19:00. Докладчик: В.П.Оревков
ПРОДОЛЖЕНИЕ
доклада
МЕТОДЫ ПОИСКА ДОКАЗАТЕЛЬСТВ ДЛЯ СКУЛЕМОВСКОГО ФРАГМЕНТА ИСЧИСЛЕНИЯ ПРЕДИКАТОВ

Пятница, 20 апреля, комната 106. Начало в 17:00.

Докладчик: В. П. Оревков.

МЕТОДЫ ПОИСКА ДОКАЗАТЕЛЬСТВ ДЛЯ СКУЛЕМОВСКОГО ФРАГМЕНТА ИСЧИСЛЕНИЯ ПРЕДИКАТОВ
Предваренная формула исчисления предикатов находится в скулемовской форме, если в ее префиксе кванторы существования предшествуют кванторам всеобщности. В докладе будут рассмотрены: 1) варианты сведения формул к скулемовскому виду; 2) методы элиминации функциональных знаков; 3) метод резолюций и обратный метод для скулемовского случая; 4) разрешимые подклассы исчисления предикатов.

Понедельник, 16 апреля, комната 412. Начало в 12:25.

Докладчик: Д. В. Карпов.

Состоится ПРОДОЛЖЕНИЕ
доклада по статье L.Lovasz STABLE SETS AND POLYNOMIALS.

Пятница, 13 апреля, комната 106. Начало в 17:00.

Докладчик: Д. В. Карпов.

Доклад по статье L.Lovasz
STABLE SETS AND POLYNOMIALS
Several applications of methods from nonlinear algebra to the stable set problem in graphs are surveyed. The most recent work cited was cowritten by A. Schrijver and involves nonlinear inequalities. These yield a procedure to generate facets of the stable set polytope. If a class of graphs has the property that all facets of the stable set polytope can be generated this way in a bounded number of steps, then the stable set problem is polynomially solvable for these graphs.

Пятница, 6 апреля, комната 106. Начало в 17:00.

Докладчик: Э. Гирш.

СОВРЕМЕННАЯ СТРУКТУРНАЯ ТЕОРИЯ СЛОЖНОСТИ
Доклад представляет собой обзор основных фундаментальных результатов 1980х-90х годов о взаимоотношениях между классами сложности вычислительных задач (P, NP, RP, BPP, BQP, PP, UP, ParityP, IP, PSPACE, ...).
Все необходимые определения будут приведены.

Пятница, 23 марта, комната 106. Начало в 17:00.

Докладчик: Б. Ю. Конев.

REDUCTION RULES AND UNIVERSAL VARIABLES FOR FIRST ORDER TABLEAUX AND DPLL
Упрощающие правила (редукции) играют большую роль в автоматическом поиске вывода. Хорошо известна их роль в пропозициональной логике; для логики первого порядка упрощающие правила применяются в основном для резолюционного исчисления. Используемые в исчислениях секвенциального типа "жесткие" переменные затрудняют применение упрощающих правил. Предлагается вариант редукций для секвенциальных исчислений первого порядка, вводимых благодаря "универсальным" переменным и правилу переименования.
Доклад подготовлен по одноименной статье Fabio Massacci.

Пятница, 16 марта, комната 101. Начало в 17:00.

Докладчик: В. Жижкун.

A FIRST-ORDER DAVIS-PUTNAM-LOGEMANN-LOVELAND PROCEDURE
В докладе будет рассказано о Davis-Putnam-Logeman-Loveland (DPLL) procedure для первого порядка (FDPLL).
DPLL для пропозициональной логики представляет собой расщепление по контрарным литералам. FDPLL является обобщением DPLL, с расщеплением по неосновным (т.е., содержащим переменные) литералам.
В качестве преимуществ FDPLL приводятся скромные требования к памяти, наличие всего 2-х правил вывода и явное построение модели в случае, если опровержения формулы не существует.
Доклад основан на статье Peter Baumgartner "FDPLL - A First-Order Davis-Putnam-Logeman-Loveland Procedure".

Пятница, 2 марта, комната 412. Начало в 13:00.

Докладчик: О. Етеревский.

ЕЩЕ О ЧИСЛАХ КАРМАЙКЛА
В докладе улучшена оценка на число простых делителей строгого числа Кармайкла n-го порядка. Будет описан способ улучшения оценки для нестрогих чисел Кармайкла порядка n при малых n. Попутно доказывается оценка снизу на сумму $\sum_{k=1}^n \phi(k)$.

Понедельник, 26 февраля, комната 412. Начало в 12:00.

Докладчик: Б. Конев.

ПРОДОЛЖЕНИЕ доклада
НИЖНИЕ ОЦЕНКИ ДЛЯ СИСТЕМ ФРЕГЕ С ОГРАНИЧЕННОЙ ГЛУБИНОЙ