Laboratory of Mathematical Logic at PDMI

Пятница, 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. Докладчик: В.П.Оревков
ПРОДОЛЖЕНИЕ
доклада
МЕТОДЫ ПОИСКА ДОКАЗАТЕЛЬСТВ ДЛЯ СКУЛЕМОВСКОГО ФРАГМЕНТА ИСЧИСЛЕНИЯ ПРЕДИКАТОВ