Laboratory of Mathematical Logic at PDMI

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

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

РАВЕНСТВА И ПЕРЕПИСЫВАНИЕ ТЕРМОВ
В докладе обсуждаются системы равенств и системы переписывания термов, некоторые их свойства (в частности, нетеровость, или остановочность) и связь этих свойств в проблемой разрешимости (теорема Кнута-Бендикса).

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

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

АВТОМАТИЧЕСКОЕ ПОРОЖДЕНИЕ ДОКАЗАТЕЛЬСТВ В СЕКВЕНЦИАЛЬНЫХ ИСЧИСЛЕНИЯХ С РАВЕНСТВОМ
(продолжение)

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

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

АВТОМАТИЧЕСКОЕ ПОРОЖДЕНИЕ ДОКАЗАТЕЛЬСТВ В СЕКВЕНЦИАЛЬНЫХ ИСЧИСЛЕНИЯХ С РАВЕНСТВОМ
впервые процедура поиска вывода в секвенциальном исчислении с равенством была предложена с. кангером в середине 50-х гг. однако, в отличие от метода резолюции, до сих пор не известен способ поиска доказательств в подобных исчислениях, который давал бы приемлемую производительность. будет сделан доклад на основе обзора А. Дегтярева и А. Воронкова "equality reasoning in sequent-based calculi", представляющий различные способы поиска секвенциальных доказательств с равенством.

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

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

ОЦЕНКИ СНИЗУ НА МАКСИМАЛЬНОЕ КОЛИЧЕСТВО ВИСЯЧИХ ВЕРШИН В ОСТОВНОМ ДЕРЕВЕ ГРАФА
Будет доказано, что в любом связном графе, степени вершин которого не менее 3, можно выделить остовное дерево, в котором более 1/4 всех вершин висячие, а в любом связном графе, степени вершин которого не менее 4, можно выделить остовное дерево, в котором более 2/5 всех вершин висячие. будут приведены бесконечные серии примеров, показывающие оптимальность этих оценок.
Для связного графа, степени всех вершин которого не менее d (d>4) будет приведен алгоритм выделения остовного дерева с большим количеством висячих вершин, будут доказаны оценки снизу на количество висячих вершин в остовном дереве такого графа.

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

вторник, 17 октября 2000 г., 12:00, к.106
состоится два доклада:
1. Докладчик: Э.Гирш
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ ПРОПОЗИЦИОНАЛЬНЫХ ДОКАЗАТЕЛЬСТВ, ПОЛИНОМИАЛЬНО СИМУЛИРУЮЩИЕ СИСТЕМЫ ФРЕГЕ
В последние годы в области пропозициональных доказательств популярны были алгебраические системы: Nullstellensatz, polynomial calculus, и другие. Для каждой их них в том или ином виде известны экспоненциальные нижние оценки (насколько они "честные", будет обсуждаться в докладе).
Для систем Фреге экспоненциальных нижних оценок не известно. в докладе будет предложен вариант polynomial calculus, который полиномиально симулирует системы Фреге. Отличие от обычного polynomial calculus состоит в том, что полиномы представляются не как суммы мономов, а как алгебраические выражения со скобками, При этом в список правил вывода добавляются аксиомы кольца.
2. Докладчик: Д.В.Карпов
О ВЫДЕЛЕНИИ K НЕ ПЕРЕСЕКАЮЩИХСЯ ПО РЕБРАМ ОСТОВНЫХ ДЕРЕВЬЕВ В 2K-РЕБЕРНО СВЯЗНОМ ГРАФЕ
Будет доказано, что во всяком 2k-реберно связном графе можно выделить k остовных деревьев, никакие два из которых не имеют общих ребер и описана конструкция такого построения.

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

Докладчик: А. В. Пастор.

ОБ УДАЛЕНИИ РЕБЕР ИЗ -СВЯЗНОГО ГРАФА БЕЗ ПОТЕРИ -СВЯЗНОСТИ
В 1969 году R. Halin доказал, что в любом -связном графе, степени всех вершин которого не меньше , есть ребро, удаление которого не нарушает -связность графа. Эта теорема положила начало исследованию свойств минимальных -связных графов, т.е. -связных графов, которые теряют -связность при удалении любого ребра, и поиску ребер, удаление которых не ведет к потере -связности, в графах, не являющихся минимальными. В докладе будет произведен обзор известных результатов по данной теме, и будут представлены новые результаты, полученные докладчиком.

Вторник, 26 сентября, комната 412. Начало в 18:30.

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

Определим число Кармайкла порядка m как такое составное число n, что возведение в n-ую степень задает эндоморфизм любой Z/nZ-алгебры, которая может быть порождена как Z/nZ-модуль m элементами. В докладе будет приведена чисто арифметическая интерпретация этого определения. Кроме того, будет доказана нижняя оценка на число простых делителей числа Кармайкла n-го порядка.

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

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

ОСТОВНОЕ ДЕРЕВО С БОЛЬШИМ КОЛИЧЕСТВОМ ВИСЯЧИХ ВЕРШИН
В 1973 году B.Zelinka предложил алгоритм выделения в графе дерева с максимально возможным количеством висячих вершин. однако, до настоящего момента не опубликовано ни одной работы с оценкой на такое количество. Именно этому вопросу и будет посвящен доклад. будет доказано, что в связном графе, в котором никакие две вершины степени 2 не смежны, есть остовное дерево, в котором более 1/5 всех вершин висячие. будет доказана точность этой оценки.

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

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

доклад по статье П.Пудлака
LOWER BOUNDS FOR RESOLUTION AND CUTTING PLANE PROOFS AND MONOTONE COMPUTATIONS
Абстракт статьи:
We prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. the latter result is of independent integers, since, in particular, it implies an exponential lower bound for some arithmetic circuits.

Вторник, 5 сентября, комната 412. Начало в 12:00.

Докладчик: М. А. Всемирнов.

ЯВНЫЕ КОНСТРУКЦИИ СЕМЕЙСТВ ПЕРЕСТАНОВОК, НЕЗАВИСИМЫХ ОТНОСИТЕЛЬНО МИНИМУМА
множество перестановок s называется независимым по k относительно минимума (k-min-wise independent), если для любого набора x_1,...,x_k количество таких перестановок s из s, что s(x_1) < s(x_2), ... , s(x_1) < s(x_k), равно |s|/k. разумеется, представляют интерес множества s как можно меньшей мощности, в частности, отличные от симметрической и знакопеременной групп.
в общем случае известны либо теоремы существования, либо конструкции таких множеств, требующие решения задачи большой вычислительной сложности.
в докладе будет изложена явная простая конструкция при k=4. конструкция использует проективную геометрию. кроме того, будет предложен ряд открытых вопросов.