DM Seminar

Discrete Mathematics Seminar

Семинар 3 сентября 2001 года

Понедельник, 3 сентября, комната 106. Начало в 14:30.

понедельник, 3 сентября 2001 г., в 14:30 в ауд. 203
Vladimir Grebinskiy, Compugen Inc.
Design and Applications of Oligo Based Micro Arrays.
Abstract
In this talk I'll describe a new tool of modern biology (oligo based micro arrays) and its use in medical dignostics, as well as computational problems in the design of optimal oligos.
No previous biological knowledge required.
Обращаю ваше внимание на нестандартное время проведения семинара

Семинар 25 мая 2001 года

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

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

Доклад по статье В.Лифшица
WHAT IS THE INVERSE METHOD?
Предлагается одна переформулировка обратного метода Маслова в терминах дизъюнктов и "супердизъюнктов", а также отношение этого метода к методу резолюций.

Семинар 11 мая 2001 года

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

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

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

Семинар 27 апреля 2001 года

Пятница, 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 апреля 2001 года

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

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

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

Семинар 16 апреля 2001 года

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

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

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

Семинар 13 апреля 2001 года

Пятница, 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 апреля 2001 года

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

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

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

Семинар 23 марта 2001 года

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

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

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

Семинар 16 марта 2001 года

Пятница, 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".

Syndicate content