Дополнительные главы дискретной математики 1

2019/2020

Статус: Дисциплина общефакультетского пула

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 1, 2 модуль

Преподаватели: Подольский Владимир Владимирович

Язык: русский

Кредиты: 3

Контактные часы: 54

Полная версия программы учебной дисциплины

Аннотация

Текущий курс дискретной математики программы ПМИ покрывает множество больших тем. Поскольку время в курсе ограниченно, по этим темам удается обсудить только самый необходимый минимум материала. Эту проблему как раз и планируется решить на факультативе. Для желающих студентов на факультативе будет рассказываться дополнительный (по сравнению с пилотным потоком ПМИ) материал по изучаемым в основном курсе темам. Занятия факультатива будут идти параллельно с основным курсом и во многом его продолжать. От слушателей факультатива требуется знакомство с материалом идущего параллельно курса дискретной математике на пилотном потоке ПМИ.

Цель освоения дисциплины

Дать студентам возможность получить повышенные знания по дискретной математике по сравнению с обязательным курсом.

Планируемые результаты обучения

Знать продвинутые понятия и методы дискретной математики
Уметь пользоваться продвинутыми методами дискретной математики для решения задач как в области дискретной математики, так и за ее приделами
Иметь навыки формализации и решения практических задач методами дискретной математики

Содержание учебной дисциплины

Комбинаторные игры
Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр.
Разрешающие деревья
Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев; пример квадратичного разрыва. Чувствительность и блочная чувствительность. Чувствительность и блочная чувствительность: квадратичный разрыв. Сертификатная сложность не больше квадрата блочной чувствительности. Степень булевой функции. Степень не больше сложности в модели деревьев разрешения. Пример: степень квадратично больше сертификатной сложности. Пример: чувствительность больше степени.
Булевы схемы
Схемная сложность функции "четность" от n переменных не меньше 3n-3. Глубина булевой схемы. Булева формула. Эквивалентность схем и формул с точки зрения глубины. Теорема о балансировке булевой формулы. Эквивалентность глубины булевой схемы и размера булевой формулы. Классы функций AC^i, NC^i, иерархия. PARITY не лежит в NC^0. Сложение чисел в AC^0. PARITY не лежит в AC^0, полиномиальный метод: схемы приближаемы многочленами. PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. Теорема Роджерса о главных универсальных функциях, начало доказательства.
Вычислимые функции
Теорема о существовании перечислимых неотделимых множеств. Перечислимое бесконечное множество номеров вычислимой функции. Теорема Роджерса об изоморфизме главных универсальных функциях. Конструкция Поста перечислимого неразрешимого множества.
Машины Тьюринга
Теорема об иерархии по времени. Квадратичный разрыв между временем вычисления на одноленточных и многоленточных машинах.
Коды с исправлением ошибок
Граница Хэмминга. Граница Гилберта. Оценки объема шара. Линейные коды. Граница Варшамова-Гилберта. Код Хэмминга. Граница Синглтона. Код Рида—Соломона, его декодирование. Оценка Плоткина. Усиление оценки Синглтона над бинарным алфавитом.
Цепи и антицепи в упорядоченных множествах
Разбиения на цепи и антицепи, связь с максимальными размерами цепей и антицепей. Разбиение на симметричные цепи в булевом кубе. Теорема Шпернера, LYM неравенство. Слово со всеми подмножествами в качестве подслов.
Производящие функции
Производящие функции, операции над ними: сложение, умножение на число, умножение, взятие обратных, подстановка, сдвиг вправо, производная. Переход от производящей функции последовательности к производящей функции ее частичных сумм. Нахождение коэффициентов производящих функций. Пример: формула для суммы квадратов. Нахождение коэффициентов в общем виде. Решение рекуррентных соотношений с помощью производящих функций.
Дополнительные главы комбинаторики и теории графов
Теорема Холла, в терминах двудольных графов и в терминах множеств. Следствие для регулярных семейств множеств. Разложение дважды стохастических матриц. Расширение k-элементных подмножеств до различных (k+1)-элементных подмножеств. Паросочетания и вершинные покрытия в двудольных графах. Максимальные паросочетания в двудольных графах. Миноры и топологические миноры графов. k-связность графов. Плоские и планарные графы. Свойство плоских лесов. Свойство плоских циклов. Свойство плоских 2-связных графов. Теорема Эйлера. Непланарность K_5 и K_{3,3}. Критерий планарности графов. Неравенство Фишера. Разбиение полного графа на полные двудольные.

Элементы контроля

Домашнее задание 1
Домашнее задание 2
Экзамен
Экзамен проводится в устной форме (опрос по материалам курса). Экзамен проводится на платформе Zoom (https://zoom.us/). К экзамену необходимо подключиться ко времени начала экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Zoom. Для участия в экзамене студент должен: явиться на экзамен, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено пользоваться подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи менее 5 минут. Долговременным нарушением связи во время экзамена считается нарушение больше 5 минут. При долговременном нарушении связи студент не может продолжить участие в экзамене.

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.25 * Домашнее задание 1 + 0.25 * Домашнее задание 2 + 0.5 * Экзамен

Программа дисциплины