imported>Vpodolskii: Migrated current public revision from wiki.cs.hse.ru

2022-06-14T16:49:47Z

Migrated current public revision from wiki.cs.hse.ru

Новая страница

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

[http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/grading.pdf Правила выставления оценок] 

Классрум для сдачи дз: https://classroom.google.com/c/Mzk4MjI3NDUyMDI5?cjc=gsk6r3e

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

Второй дедлайн по домашним заданиям: 13.12.21 

Экзамен будет проходить на неделе с 13 декабря по 17 декабря. Оптимально сдать во время факультатива, но можно договориться и на другое время.

Первый дедлайн по домашним заданиям весеннего семестра: 06.04.22 (листки 6-10) 





== Расписание ==

Занятия проходят по вторникам в 14:40 в зуме. Первое занятие прошло 28 сентября.



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

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

{| 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]
|}

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

{| class="wikitable"
|-
! Дата !! Summary !! Домашнее задание
|-
|| 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]
|-
|| 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]
|-
|| 09.11.21 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. || [https://www.dropbox.com/s/2oju05jodn14835/cw05_dop.pdf?dl=0 Листок 5]
|-
|| 23.11.21 || Начальные отрезки, их свойства. Теорема о рекурсии.|| Тот же листок
|-
|| 30.11.21 || Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок

|}

== Источники ==

Числа Каталана: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf Черновик учебника по дискретной математике] 
Исчисление высказываний: [https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf Верещагин, А. Шень, Языки и исчисления.] 
Замкнутые классы булевых функций: [https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf Верещагин, А. Шень, Языки и исчисления.] 
Лемма Шпернера, теорема Брауэра: [http://math.mit.edu/~fox/MAT307-lecture03.pdf http://math.mit.edu/~fox/MAT307-lecture03.pdf] 
Вполне упорядоченные множества: [https://www.mccme.ru/free-books/shen/shen-logic-part1-2.pdf Верещагин, А. Шень, Начала теории множеств.] 
Цепи и антицепи: [https://web.vu.lt/mif/s.jukna/EC_Book_2nd/index.html Stasys Jukna, Extremal Combinatorics] 
Теорема Бонди-Хватала: [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] 
Теорема Хватала: Р. Дистель, Теория графов 
Вероятностный алгоритм проверки чисел на простоту: Michael Sipser, Introduction to the Theory of Computation 
Рекурренты: [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] 
Разрешающие деревья: [https://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Обзор по теме] 
Приближение 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) 
Доказательство гипотезы чувствительности: [https://terrytao.wordpress.com/2019/07/26/twisted-convolution-and-the-sensitivity-conjecture/ блог Теренса Tao]


== Результаты ==

Dopglavy DM 2022 - История изменений

imported>Vpodolskii: Migrated current public revision from wiki.cs.hse.ru