DM Seminar

Discrete Mathematics Seminar

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

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

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

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

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

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

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

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

Семинар 17 октября 2000 года

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

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

Семинар 10 октября 2000 года

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

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

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

Семинар 26 сентября 2000 года

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

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

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

Семинар 19 сентября 2000 года

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

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

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

Семинар 12 сентября 2000 года

Вторник, 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 сентября 2000 года

Вторник, 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. конструкция использует проективную геометрию. кроме того, будет предложен ряд открытых вопросов.

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

Cреда, 31 мая, комната 412. Начало в 14:00.

Докладчик: В. Баргачев.

TITLE: OVERVIEW OF PROBABILISTIC PRIMALITY TESTS, ESPECIALLY THE "VERY STRONG PRIMARILITY TEST" BY WILLIAM ADAMS AND DANIEL SHANKS.
There is no known "good" deterministic algorithm for deciding if the given number p is prime. "Good" means algorithm whose running time is bounded by polynomial of log(p). however, there are some "probabilistic" algorithms: they can decide whether given number is composite or prime with probability (1-a). It is a rather convenient form since after running such an algorithm n times, we obtain either p is composite or p is prime with probability (1-a^n).
Well known are euler test with a=1/2, and Miller-Rabin's test with a=1/4. adams and shanks introduced a test for which most probably a=1/216 -- this will be the focus of our talk.

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

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

Докладчик: А. Тискин.

НЕСТАНДАРТНЫЕ ПРИМЕНЕНИЯ ЭКСТРЕМАЛЬНОЙ ТЕОРИИ ГРАФОВ
В 1975 г. Семереди сформулировал и доказал лемму о регулярном разбиении (Szemeredi's regularity lemma). В последние годы этот результат стал активно использоваться для решения экстремальных задач теории графов, однако его применение возможно и в других областях математики. В докладе будет рассказано о двух задачах, решенных при помощи нестандартного применения леммы семереди: задача об асимптотической плотности упаковки трехмерных полимино, и задача о коммуникационной сложности умножения булевых матриц.

Syndicate content