DM Seminar

Discrete Mathematics Seminar

Семинар 18 января 2000 года

Вторник, 18 января, комната 106. Начало в 15:00.

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

"О вычислении формул сечения при поиске вывода в исчислении предикатов"
Правило резолюций в методе резолюций Робинсона и правило Б в обратном методе Маслова являются правилами сечения по контрарной паре в первом случае и по исходной "clause" во втором. Выводом исходной формулы является вывод пустого объекта по этим правилам. В докладе предлагается, наоборот, по исходной формуле строить формулу сечения таким образом, что устранение сечения приводит к реконструкции исходных контрарных пар и исходных "clauses". Построенная формула сечения оказывается исходной для следующего шага. Последовательность формул сечения, оканчивающаяся пропозиционально выводимой формулой, является выводом исходной формулы.

Семинар 10 января 2000 года

Понедельник, 10 января, комната 203. Начало в 14:30.

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

"Подход Г.Чайтина к колмогоровской сложности"
Этот подход отличается тем, что, в частности, предлагается ограничиться только такими программами универсальной машины Тьюринга, для которых никакой префикс не является программой (self-delimiting programs). Это позволяет ввести вероятность остановки $ \Omega $ (halting probability). Будут рассмотрены свойства введенных понятий, а также следствия для алгоритмической теории информации.

Семинар 28 декабря 1999 года

Вторник, 28 декабря, комната 106. Начало в 18:00.

28 декабря.
М.А.Всемирнов "Реберные раскраски графов, Nullstellensatz и вычисление определителей".
Предлагается новый критерий существования реберных k-раскрасок графов, формулируемый в терминах обращения в 0 определителей специального вида. Тематически этот доклад связан с предыдущим докладом Д.В.Карпова и Ю.В.Матиясевича, однако изложение носит независимый характер.

Семинар 21 декабря 1999 года

Вторник, 21 декабря, комната 106. Начало в 18:00.

21 декабря.
Д.В.Карпов, Ю.В.Матиясевич
В первой части Д.В.Карпов изложит по статье N. Alon "Combinatorial Nullstelensatz" (Combinatorics Probability and Computing 1999, N8, p7-29) технику сведения комбинаторных проблем (в частности, связанных с раскрасками графов) к вопросам о нулях многочленов.
Во второй части семинара Ю.В.Матиясевич изложит результаты о связи существования правильной раскраски ребер триангуляции сферы и невырожденности специального полинома, соответствующего этому графу. (См. Homepage Ю.В.Матиясевича http://logic.pdmi.ras.ru/~yumat/ и статью Ю.В.Матиясевича "Один критерий раскрашиваемости вершин графа, формулируемый в терминах ориентации ребер" (Дискретный анализ, N26(1974) )

Семинар 14 декабря 1999 года

Вторник, 14 декабря, комната 106. Начало в 18:00.

14 декабря.
Э.Гирш "Сложность по Колмогорову: неожиданные примеры применения"
С помощью сложности по Колмогорову и _элементарной_ теории чисел будут заново (более просто) доказаны следующие результаты:
-- Valiant-Vazirani lemma о сведении SAT к SAT для одновыполнимых формул; -- Sipser's lemma; -- BPP \subset \Sigma_2^p.
Попутно получаются другие интересные результаты о ресурсно-ограниченной сложности по Колмогорову.
Доклад будет сделан на основе статьи H. Buhrman, L. Fortnow, "Resource-Bounded Kolmogorov Complexity Revisited", STACS-97.

Семинар 30 ноября 1999 года

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

30 ноября.
В.Жижкун "Представление булевых функций ациклическими направленными графами"
АБСТРАКТ
Binary Decision Diagrams (BDDs) - способ представления логических функций, позволяющий эффективно реализовать различные операции над ними. В том, что такая проблема достаточно актуальна, можно убедиться, например, построив КНФ отрицания формулы в КНФ. Преимущество BDD в том, что результаты операций над булевыми формулами представляются компактно.
Кроме того, BDD - каноническая форма, поэтому проверка двух функций на эквивалентность заключается в сравнении двух направленых ациклических размеченых графов, а выполнимость формулы - сравнение соответствующего графа с тривиальным.
Существенный недостаток этого способа - необходимость фиксировать порядок переменных. Кроме того, размер графов существенно зависит от выбора такого порядка. Помимо этого, известно, что представление функции умножения двоичных чисел с помощью BDD требует экспоненциального числа узлов при любой перестановке переменных.
Доклад будет сделан на основе статьи Randal E. Bryant "Graph-Based Algorithms for Boolean Function Manipulation".

Семинар 23 ноября 1999 года

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

23 ноября.
Д.В.Карпов, доклад по статье
D.Achlioptas, M.Molloy "Almost all graphs with 2.522N edges are not 3-colorable". (The Electronic Journal of Combinatorics, 6(1999), #R29)
Abstract. B этой работе доказывается, что для любого с>=2.522, вершины случайного графа с N вершинами и 2.522N ребрами нельзя правильным образом раскрасить в три цвета с вероятностью 1-o(1). Также в этой работе рассматтривается рассматривается аналогичный вопрос для k-раскрашиваемости при k>3, приводятся соответствующие оценки.

Семинар 16 ноября 1999 года

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

16 ноября.
Б.Ю.Конев. Доклад о патентованном алгоритме Stalmark'а установления тавтологичности пропозициональных формул. Судя по результатам машинных тестов, алгоритм является достаточно эффективным, авторы утверждают, что время его работы зависит не от количества неизвестных, а от "логической структуры формулы". Алгоритм достаточно прост, но никаких оценок для него не известно. Доклад будет сделан на основе статьи John Harrison "Stalmark's Algorithm as a HOL Derived Rule", однако, детали реализации освещаться не будут.

Семинар 2 ноября 1999 года

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

2 ноября.
В.Жижкун "Разрешимые частные случаи задачи квазиунификации".
АБСТРАКТ
Задача квазиунификации возникает естественным образом в теории логического вывода при при изучении возможности обобщения доказательств (гипотеза Крайзеля). В общей постановке задача оказывается алгоритмически неразрешимой. В докладе будет приведен общий (естественно, неполный) алгоритм ее решения, а также полные алгоритмы для двух частных случаев, имеющих конкретное применение в теории вывода. Эти алгоритмы позволяют получить верхние оценки высоты термов в решении.

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

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

19 октября.
М.Всемирнов "Арифметика кватернионов и графы Рамануджана"
Графы Рамануджана определяются в терминах спектра матрицы смежности. Такие графы обладают многими замечательными свойствами.
В настоящее время известно несколько принципиально различных явных конструкций графов Рамануджана. Одна из них, принадлежащая Маргулису- Любоцкому- Сарнаку, основанная на арифметических свойствах кватернионов, и будет представлена в докладе.
Конструкция будет описана явно. К сожалению, провести все необходимые доказательства в рамках одной лекции практически невозможно. С другой стороны, чуть менее сложно удается доказать (что и будет сделано), что такие графы имеют большой обхват. (Обхват - длина кратчайшего простого цикла)
Дальнейшие подробности зависят от интереса слушателей к этой тематике.

Syndicate content