DM Seminar

Discrete Mathematics Seminar

Семинар 19 октября 2001 года

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

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

МОДАЛЬНЫЕ ЛОГИКИ И СЕМАНТИКИ КРИПКЕ
Модальные логики получаются из традиционной пропозициональной добавлением новых "модальных" операторов и "модальных" аксиом (примеры: логика возможности/необходимости, темпоральная логика). Весьма удобным средством не только для интерпретации, но и для исследования получающихся формальных аксиоматических систем оказались модели Крипке (1960-е гг.), системы отношений над множествами.
В докладе будет рассказано, что из себя представляют семантики Крипке (relational structures) и как они могут быть использованы.
Изложение основано на первой главе книги P. Blackburn, M. de Rijke, Y. Venema. "Modal Logic". (http://www.mlbook.org)

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

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

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

СВЯЗЬ КОЛИЧЕСТВА ВИСЯЧИХ ВЕРШИН В ОСТОВНОМ ДЕРЕВЕ КУБИЧЕСКОГО ГРАФА И КОЛИЧЕСТВА ПОДГРАФОВ K_4^-.
Рассматривается связный граф~$ G $, степени вершин которого не менее трех. Доказывается, что ограничение на долю вершин степени три, входящих в подграфы $ K_4^- $, позволяет гарантировать большее количество висячих вершин в остовном дереве такого графа. Все оценки снизу на количество висячих вершин доказываются с помощью полиномиальных алгоритмов.

Семинар 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, ...).
Все необходимые определения будут приведены.

Syndicate content