Dopglavy DM 2022 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показаны 24 промежуточные версии этого же участника)
Строка 5: Строка 5:
 
Классрум для сдачи дз: https://classroom.google.com/c/Mzk4MjI3NDUyMDI5?cjc=gsk6r3e
 
Классрум для сдачи дз: https://classroom.google.com/c/Mzk4MjI3NDUyMDI5?cjc=gsk6r3e
  
<!---
 
  
Первый дедлайн по домашним заданиям: <span>26.10.20</span><br>
+
Первый дедлайн по домашним заданиям: <span>8.11.21</span><br>
  
 +
Второй дедлайн по домашним заданиям: <span>13.12.21</span><br>
  
 +
Экзамен будет проходить на неделе с 13 декабря по 17 декабря. Оптимально сдать во время факультатива, но можно договориться и на другое время.
 +
 +
Первый дедлайн по домашним заданиям весеннего семестра: <span>06.04.22</span> (листки 6-10)<br>
 +
 +
 +
<!---
  
 
Второй дедлайн по домашним заданиям: <s>01.06.20</s> <span style="color:red">31.05.20</span><br>
 
Второй дедлайн по домашним заданиям: <s>01.06.20</s> <span style="color:red">31.05.20</span><br>
Строка 38: Строка 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]
 +
|}
  
 
'''Первый семестр'''
 
'''Первый семестр'''
Строка 49: Строка 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]  
<!---
 
 
|-  
 
|-  
|| 12.10.20 || Лемма Шпернера. Теорема Брауэра. || [https://www.dropbox.com/s/88raglxnoxnrzd5/cw04_dop.pdf?dl=0 Листок 4]  
+
|| 26.10.21 || Лемма Шпернера. Теорема Брауэра. || [https://www.dropbox.com/s/3u4xqqnptya08tx/cw04_dop.pdf?dl=0 Листок 4]  
 
|-  
 
|-  
|| 26.10.20 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. Теорема о рекурсии, формулировка. || [https://www.dropbox.com/s/zgnf3lgg16fpvyz/cw05_dop.pdf?dl=0 Листок 5]
+
|| 09.11.21 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. || [https://www.dropbox.com/s/2oju05jodn14835/cw05_dop.pdf?dl=0 Листок 5]
 
|-  
 
|-  
|| 02.11.20 || Теорема о рекурсии, доказательство. Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок  
+
|| 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: Строка 119:
 
Исчисление высказываний: [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>
 
Замкнутые классы булевых функций: [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>
Цепи и антицепи: [http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/  Stasys Jukna, Extremal Combinatorics] <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>
Потоки и разрезы: Р. Дистель, Теория графов <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>
Комбинаторные игры: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf  Черновик учебника по дискретной математике] <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

10.03.22 Разрешающие деревья, сертификатная сложность, примеры.

Листок 11

24.03.22 Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев. Степень булевой функции.

Тот же листок

11.04.22 Чувствительность и блочная чувствительность, квадратичный разрыв между ними. Сертификатная сложность не больше квадрата блочной чувствительности.

Тот же листок

18.04.22 Лемма о симметризации многочленов. Оценка на степень многочленов одной переменной.

Листок 12

16.05.22 Полиномиальная связь сложности в модели разрешающих деревьев и степени функции. Многочлены Чебышева, приближение булевых функций многочленами.

Тот же листок

06.06.22 Доказательство гипотезы чувствительности.

Листок 13

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

Дата 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

Результаты