Dopglavy DM 2022 — различия между версиями
(не показано 19 промежуточных версии этого же участника) | |||
Строка 7: | Строка 7: | ||
Первый дедлайн по домашним заданиям: <span>8.11.21</span><br> | Первый дедлайн по домашним заданиям: <span>8.11.21</span><br> | ||
+ | |||
+ | Второй дедлайн по домашним заданиям: <span>13.12.21</span><br> | ||
+ | |||
+ | Экзамен будет проходить на неделе с 13 декабря по 17 декабря. Оптимально сдать во время факультатива, но можно договориться и на другое время. | ||
+ | |||
+ | Первый дедлайн по домашним заданиям весеннего семестра: <span>06.04.22</span> (листки 6-10)<br> | ||
+ | |||
<!--- | <!--- | ||
Строка 37: | Строка 44: | ||
== Материалы курса == | == Материалы курса == | ||
+ | '''Второй семестр''' | ||
− | + | {| class="wikitable" | |
+ | |- | ||
+ | ! Дата !! Summary !! Домашнее задание | ||
+ | |- | ||
+ | || 27.01.22 || Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. || [https://www.dropbox.com/s/dd4av1a1bejx03q/cw6_dop.pdf?dl=0 Листок 6] | ||
+ | |- | ||
+ | || 03.02.22 || Гамильтоновы графы. Теорема Бонди-Хватала. Теорема Хватала о степенных последовательностях. || [https://www.dropbox.com/s/a3bntgcow7aatlu/cw07_dop.pdf?dl=0 Листок 7] | ||
+ | |- | ||
+ | || 10.02.22 || Вероятностный алгоритм для проверки чисел на простоту. || [https://www.dropbox.com/s/2x1ir4vhvkdj0n0/cw8_dop.pdf?dl=0 Листок 8] | ||
+ | |- | ||
+ | || 17.02.22 || Линейные рекуррентные соотношения с постоянными коэффициентами. Решение рекуррентных соотношений с помощью производящих функций. || [https://www.dropbox.com/s/xckxverlzvezyse/cw9_dop.pdf?dl=0 Листок 9] | ||
+ | |- | ||
+ | || 03.03.22 || Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. || | ||
+ | [https://www.dropbox.com/s/h91wj82d9euat9o/cw10_dop.pdf?dl=0 Листок 10] | ||
+ | |- | ||
+ | || 10.03.22 || Разрешающие деревья, сертификатная сложность, примеры. || | ||
+ | [https://www.dropbox.com/s/rvw46honffebj8q/cw11_dop.pdf?dl=0 Листок 11] | ||
+ | |- | ||
+ | || 24.03.22 || Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев. Степень булевой функции. || | ||
+ | Тот же листок | ||
+ | |- | ||
+ | || 11.04.22 || Чувствительность и блочная чувствительность, квадратичный разрыв между ними. Сертификатная сложность не больше квадрата блочной чувствительности. || | ||
+ | Тот же листок | ||
+ | |- | ||
+ | || 18.04.22 || Лемма о симметризации многочленов. Оценка на степень многочленов одной переменной. || | ||
+ | [https://www.dropbox.com/s/62uv9uagjavttnq/cw12_dop.pdf?dl=0 Листок 12] | ||
+ | |- | ||
+ | || 16.05.22 || Полиномиальная связь сложности в модели разрешающих деревьев и степени функции. Многочлены Чебышева, приближение булевых функций многочленами. || | ||
+ | Тот же листок | ||
+ | |- | ||
+ | || 06.06.22 || Доказательство гипотезы чувствительности. || | ||
+ | [https://www.dropbox.com/s/n7vpvbvfuitxzsk/cw13_dop.pdf?dl=0 Листок 13] | ||
+ | |} | ||
'''Первый семестр''' | '''Первый семестр''' | ||
Строка 48: | Строка 88: | ||
|| 28.09.21 || Числа Каталана. Рекурсивное определение и определение через баланс скобок, их эквивалентность. Рекуррентная формула для чисел Каталана. Выводы формулы для чисел Каталана: метод отражений. || [https://www.dropbox.com/s/tubndxy25jtpevr/cw01_dop.pdf?dl=0 Листок 1] | || 28.09.21 || Числа Каталана. Рекурсивное определение и определение через баланс скобок, их эквивалентность. Рекуррентная формула для чисел Каталана. Выводы формулы для чисел Каталана: метод отражений. || [https://www.dropbox.com/s/tubndxy25jtpevr/cw01_dop.pdf?dl=0 Листок 1] | ||
|- | |- | ||
− | || 05.10.21 || Логика высказываний, ее корректность. Лемма о дедукции. || [https://www.dropbox.com/s/5vu077gclqke17z/cw02_dop.pdf?dl=0 Листок 2] | + | || 05.10.21 || Логика высказываний, ее корректность. Лемма о дедукции (формулировка). || [https://www.dropbox.com/s/5vu077gclqke17z/cw02_dop.pdf?dl=0 Листок 2] |
|- | |- | ||
|| 12.10.21 || Замкнутые классы булевых функций. Теорема Поста. || [https://www.dropbox.com/s/zhkyucq844znzry/cw03_dop.pdf?dl=0 Листок 3] | || 12.10.21 || Замкнутые классы булевых функций. Теорема Поста. || [https://www.dropbox.com/s/zhkyucq844znzry/cw03_dop.pdf?dl=0 Листок 3] | ||
|- | |- | ||
|| 26.10.21 || Лемма Шпернера. Теорема Брауэра. || [https://www.dropbox.com/s/3u4xqqnptya08tx/cw04_dop.pdf?dl=0 Листок 4] | || 26.10.21 || Лемма Шпернера. Теорема Брауэра. || [https://www.dropbox.com/s/3u4xqqnptya08tx/cw04_dop.pdf?dl=0 Листок 4] | ||
− | |||
|- | |- | ||
− | || | + | || 09.11.21 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. || [https://www.dropbox.com/s/2oju05jodn14835/cw05_dop.pdf?dl=0 Листок 5] |
+ | |- | ||
+ | || 23.11.21 || Начальные отрезки, их свойства. Теорема о рекурсии.|| Тот же листок | ||
+ | |- | ||
+ | || 30.11.21 || Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок | ||
+ | <!--- | ||
|- | |- | ||
− | || | + | || 30.11.21 || Теорема о рекурсии, доказательство. Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок |
|- | |- | ||
|| 09.11.20 || Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. || [https://www.dropbox.com/s/ot0sb7lqhw5tp4g/cw6_dop.pdf?dl=0 Листок 6] | || 09.11.20 || Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. || [https://www.dropbox.com/s/ot0sb7lqhw5tp4g/cw6_dop.pdf?dl=0 Листок 6] | ||
Строка 76: | Строка 120: | ||
Замкнутые классы булевых функций: [https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf Верещагин, А. Шень, Языки и исчисления.] <br> | Замкнутые классы булевых функций: [https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf Верещагин, А. Шень, Языки и исчисления.] <br> | ||
Лемма Шпернера, теорема Брауэра: [http://math.mit.edu/~fox/MAT307-lecture03.pdf http://math.mit.edu/~fox/MAT307-lecture03.pdf] <br> | Лемма Шпернера, теорема Брауэра: [http://math.mit.edu/~fox/MAT307-lecture03.pdf http://math.mit.edu/~fox/MAT307-lecture03.pdf] <br> | ||
− | |||
− | |||
− | |||
Вполне упорядоченные множества: [https://www.mccme.ru/free-books/shen/shen-logic-part1-2.pdf Верещагин, А. Шень, Начала теории множеств.] <br> | Вполне упорядоченные множества: [https://www.mccme.ru/free-books/shen/shen-logic-part1-2.pdf Верещагин, А. Шень, Начала теории множеств.] <br> | ||
− | Цепи и антицепи: [ | + | Цепи и антицепи: [https://web.vu.lt/mif/s.jukna/EC_Book_2nd/index.html Stasys Jukna, Extremal Combinatorics] <br> |
Теорема Бонди-Хватала: [https://personalpages.manchester.ac.uk/staff/mark.muldoon/Teaching/DiscreteMaths/LectureNotes/HamiltonBondyAndChvatal.pdf https://personalpages.manchester.ac.uk/staff/mark.muldoon/Teaching/DiscreteMaths/LectureNotes/HamiltonBondyAndChvatal.pdf] <br> | Теорема Бонди-Хватала: [https://personalpages.manchester.ac.uk/staff/mark.muldoon/Teaching/DiscreteMaths/LectureNotes/HamiltonBondyAndChvatal.pdf https://personalpages.manchester.ac.uk/staff/mark.muldoon/Teaching/DiscreteMaths/LectureNotes/HamiltonBondyAndChvatal.pdf] <br> | ||
Теорема Хватала: Р. Дистель, Теория графов <br> | Теорема Хватала: Р. Дистель, Теория графов <br> | ||
− | |||
− | |||
Вероятностный алгоритм проверки чисел на простоту: Michael Sipser, Introduction to the Theory of Computation <br> | Вероятностный алгоритм проверки чисел на простоту: Michael Sipser, Introduction to the Theory of Computation <br> | ||
Рекурренты: [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_notes.pdf MIT lecture notes] <br> | Рекурренты: [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/readings/MIT6_042JF10_notes.pdf MIT lecture notes] <br> | ||
− | |||
Разрешающие деревья: [https://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Обзор по теме] <br> | Разрешающие деревья: [https://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Обзор по теме] <br> | ||
+ | Приближение OR многочленами: [http://www.cs.columbia.edu/~rocco/Public/d16.pdf A. Klivans and R. Servedio, Toward Attribute-Efficient Learning of Decision Lists and Parities.] (Section 4.2) <br> | ||
+ | Доказательство гипотезы чувствительности: [https://terrytao.wordpress.com/2019/07/26/twisted-convolution-and-the-sensitivity-conjecture/ блог Теренса Tao] | ||
+ | <!--- | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | Потоки и разрезы: Р. Дистель, Теория графов <br> | ||
+ | Планарные графы: Р. Дистель, Теория графов <br> | ||
+ | Комбинаторные игры: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf Черновик учебника по дискретной математике] <br> | ||
+ | |||
Балансирующие семейства множеств: [https://eccc.weizmann.ac.il/report/2019/026/ https://eccc.weizmann.ac.il/report/2019/026/] <br> | Балансирующие семейства множеств: [https://eccc.weizmann.ac.il/report/2019/026/ https://eccc.weizmann.ac.il/report/2019/026/] <br> |
Текущая версия на 19:49, 14 июня 2022
Общая информация
Классрум для сдачи дз: https://classroom.google.com/c/Mzk4MjI3NDUyMDI5?cjc=gsk6r3e
Первый дедлайн по домашним заданиям: 8.11.21
Второй дедлайн по домашним заданиям: 13.12.21
Экзамен будет проходить на неделе с 13 декабря по 17 декабря. Оптимально сдать во время факультатива, но можно договориться и на другое время.
Первый дедлайн по домашним заданиям весеннего семестра: 06.04.22 (листки 6-10)
Расписание
Занятия проходят по вторникам в 14:40 в зуме. Первое занятие прошло 28 сентября.
Материалы курса
Второй семестр
Дата | Summary | Домашнее задание |
---|---|---|
27.01.22 | Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. | Листок 6 |
03.02.22 | Гамильтоновы графы. Теорема Бонди-Хватала. Теорема Хватала о степенных последовательностях. | Листок 7 |
10.02.22 | Вероятностный алгоритм для проверки чисел на простоту. | Листок 8 |
17.02.22 | Линейные рекуррентные соотношения с постоянными коэффициентами. Решение рекуррентных соотношений с помощью производящих функций. | Листок 9 |
03.03.22 | Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. | |
10.03.22 | Разрешающие деревья, сертификатная сложность, примеры. | |
24.03.22 | Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев. Степень булевой функции. |
Тот же листок |
11.04.22 | Чувствительность и блочная чувствительность, квадратичный разрыв между ними. Сертификатная сложность не больше квадрата блочной чувствительности. |
Тот же листок |
18.04.22 | Лемма о симметризации многочленов. Оценка на степень многочленов одной переменной. | |
16.05.22 | Полиномиальная связь сложности в модели разрешающих деревьев и степени функции. Многочлены Чебышева, приближение булевых функций многочленами. |
Тот же листок |
06.06.22 | Доказательство гипотезы чувствительности. |
Первый семестр
Дата | Summary | Домашнее задание |
---|---|---|
28.09.21 | Числа Каталана. Рекурсивное определение и определение через баланс скобок, их эквивалентность. Рекуррентная формула для чисел Каталана. Выводы формулы для чисел Каталана: метод отражений. | Листок 1 |
05.10.21 | Логика высказываний, ее корректность. Лемма о дедукции (формулировка). | Листок 2 |
12.10.21 | Замкнутые классы булевых функций. Теорема Поста. | Листок 3 |
26.10.21 | Лемма Шпернера. Теорема Брауэра. | Листок 4 |
09.11.21 | Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. | Листок 5 |
23.11.21 | Начальные отрезки, их свойства. Теорема о рекурсии. | Тот же листок |
30.11.21 | Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. | Тот же листок |
Источники
Числа Каталана: Черновик учебника по дискретной математике
Исчисление высказываний: Верещагин, А. Шень, Языки и исчисления.
Замкнутые классы булевых функций: Верещагин, А. Шень, Языки и исчисления.
Лемма Шпернера, теорема Брауэра: 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
Разрешающие деревья: Обзор по теме
Приближение OR многочленами: A. Klivans and R. Servedio, Toward Attribute-Efficient Learning of Decision Lists and Parities. (Section 4.2)
Доказательство гипотезы чувствительности: блог Теренса Tao