Dopglavy DM 2021

Общая информация

Правила выставления оценок

Первый дедлайн по домашним заданиям: 26.10.20

Расписание

Занятия проходят по понедельникам в 18:10 в аудитории R408. Первое занятие прошло 21 сентября.

Материалы курса

Второй семестр

Дата	Summary	Домашнее задание
25.01.21	Разбор задач листков 4-9.
01.02.21	Вероятностный алгоритм для проверки чисел на простоту.	Листок 10
15.02.21	Линейные рекуррентные соотношения с постоянными коэффициентами. Решение рекуррентных соотношений с помощью производящих функций.	Листок 11
22.02.21	Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр.	Листок 12
01.03.21	Разрешающие деревья, примеры.	Листок 13
22.03.21	Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев.	Тот же листок
12.04.21	Степень булевой функции. Пример квадратичного разрыва между сертификатной сложностью и сложностью в модели разрешающих деревьев.	Тот же листок
16.04.21	Чувствительность и блочная чувствительность, квадратичный разрыв между ними. Сертификатная сложность не больше квадрата блочной чувствительности.	Тот же листок
23.04.21	Лемма о симметризации многочленов. Оценка на степень многочленов одной переменной.	Листок 14
30.04.21	Полиномиальная связь сложности в модели разрешающих деревьев и степени функции. Многочлены Чебышева, приближение булевых функций многочленами.	Тот же листок
07.05.21	Классы функций AC^i, NC^i, иерархия. Описание класса NC^0. Сложение чисел в AC^0.	Листок 15
14.05.21	PARITY не лежит в AC^0, полиномиальный метод: схемы приближаемы многочленами.	Тот же листок
21.05.21	PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$.	Тот же листок
04.06.21	Коммуникационная сложность.	Листок 16

Первый семестр

Дата	Summary	Домашнее задание
21.09.20	Числа Каталана. Рекурсивное определение и определение через баланс скобок, их эквивалентность. Рекуррентная формула для чисел Каталана. Выводы формулы для чисел Каталана: метод отражений.	Листок 1
28.09.20	Логика высказываний, ее корректность. Лемма о дедукции.	Листок 2
05.10.20	Замкнутые классы булевых функций. Теорема Поста.	Листок 3
12.10.20	Лемма Шпернера. Теорема Брауэра.	Листок 4
26.10.20	Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. Теорема о рекурсии, формулировка.	Листок 5
02.11.20	Теорема о рекурсии, доказательство. Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело.	Тот же листок
09.11.20	Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство.	Листок 6
16.11.20	Гамильтоновы графы. Теорема Бонди-Хватала. Теорема Хватала о степенных последовательностях.	Листок 7
23.11.20	Потоки и разрезы. Теорема Форда-Фалкерсона.	Листок 8
30.11.20	Миноры и топологические миноры. 2-связные и 3-связные графы. Теорема Эйлера о плоских графах. Теорема Куратовского.	Листок 9
7.12.20	Разбор задач листков 1-4.

Источники

Числа Каталана: Черновик учебника по дискретной математике
Логика высказываний: Верещагин, А. Шень, Языки и исчисления.
Замкнутые классы булевых функций: Верещагин, А. Шень, Языки и исчисления.
Лемма Шпернера, теорема Брауэра: http://math.mit.edu/~fox/MAT307-lecture03.pdf
Вполне упорядоченные множества: Верещагин, А. Шень, Начала теории множеств.
Цепи и антицепи: Stasys Jukna, Extremal Combinatorics
Теорема Бонди-Хватала: https://personalpages.manchester.ac.uk/staff/mark.muldoon/Teaching/DiscreteMaths/LectureNotes/HamiltonBondyAndChvatal.pdf
Теорема Хватала: Р. Дистель, Теория графов
Потоки и разрезы: Р. Дистель, Теория графов
Планарные графы: Р. Дистель, Теория графов
Вероятностный алгоритм проверки чисел на простоту: Michael Sipser, Introduction to the Theory of Computation
Рекурренты: MIT lecture notes
Комбинаторные игры: Черновик учебника по дискретной математике
Разрешающие деревья: Обзор по теме