2019/2020
Дополнительные главы дискретной математики 1
Статус:
Дисциплина общефакультетского пула
Где читается:
Факультет компьютерных наук
Когда читается:
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 * Экзамен
Список литературы
Рекомендуемая основная литература
- Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
Рекомендуемая дополнительная литература
- Buhrman, H., & de Wolf, R. (2002). Complexity measures and decision tree complexity: a survey. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.8E5718C5
- Shen, A., Romashchenko, A., & Yu. Rumyantsev, A. (2017). Notes on coding theory ; Заметки по теории кодирования. France, Europe: HAL CCSD. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.629AC8BC
- Stasys Jukna. (2001). Extremal Combinatorics. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.7D5ACA81
- Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции - Московский центр непрерывного математического образования - 2008 - 192с. - ISBN: 978-5-94057-323-4 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9308