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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
 
(не показано 28 промежуточных версии этого же участника)
Строка 3: Строка 3:
 
[http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/grading.pdf Правила выставления оценок] <br>
 
[http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/grading.pdf Правила выставления оценок] <br>
  
<!---
 
  
Дедлайн по домашним заданиям: <s>03.04.20</s> <span>06.04.20</span><br>
+
 
 +
Первый дедлайн по домашним заданиям: <span>26.10.20</span><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>
Строка 34: Строка 36:
 
== Материалы курса ==
 
== Материалы курса ==
  
<!---
+
 
  
  
Строка 43: Строка 45:
 
! Дата !! Summary !! Домашнее задание
 
! Дата !! Summary !! Домашнее задание
 
|-
 
|-
  || 23.01.20 || Миноры и топологические миноры. 2-связные и 3-связные графы. Теорема Эйлера о плоских графах. Теорема Куратовского. || [https://www.dropbox.com/s/7ygm29rve7zx3qj/cw09_dop.pdf?dl=0 Листок 9]
+
  || 25.01.21 || Разбор задач листков 4-9. ||  
 
|-
 
|-
  || 30.01.20 || Неравенство Чернова. || [https://www.dropbox.com/s/fazc9hjclwojkyz/cw10_dop.pdf?dl=0 Листок 10]  
+
  || 01.02.21 || Вероятностный алгоритм для проверки чисел на простоту. || [https://www.dropbox.com/s/slsedwws4hqzj74/cw10_dop.pdf?dl=0 Листок 10]  
 
|-
 
|-
  || 06.02.20 || Разбор задач прошлого семестра. ||
+
  || 15.02.21 || Линейные рекуррентные соотношения с постоянными коэффициентами. Решение рекуррентных соотношений с помощью производящих функций. || [https://www.dropbox.com/s/efhv45nmxdga0ew/cw11_dop.pdf?dl=0 Листок 11]
 
|-
 
|-
  || 13.02.20 || Вероятностный алгоритм для проверки чисел на простоту. || [https://www.dropbox.com/s/x0erd348blfinuf/cw11_dop.pdf?dl=0 Листок 11]  
+
  || 22.02.21 || Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. ||  
 +
[https://www.dropbox.com/s/fzt2nkc6k0g56v3/cw12_dop.pdf?dl=0 Листок 12]  
 
|-
 
|-
  || 20.02.20 || Линейные рекуррентные соотношения с постоянными коэффициентами. Решение рекуррентных соотношений с помощью производящих функций. || [https://www.dropbox.com/s/mc6x5sl3ad8w77e/cw12_dop.pdf?dl=0 Листок 12]  
+
  || 01.03.21 || Разрешающие деревья, примеры. ||  
 +
[https://www.dropbox.com/s/dr9sfvk7bjjqs12/cw13_dop.pdf?dl=0 Листок 13]  
 
|-
 
|-
  || 12.03.20 || Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. ||
+
  || 22.03.21 || Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев.  ||  
[https://www.dropbox.com/s/66vet3ixcey0l73/cw13_dop.pdf?dl=0 Листок 13]
+
Тот же листок
|-
+
  || 07.04.20 || Разрешающие деревья, примеры. ||  
+
[https://www.dropbox.com/s/ptoqzljh1lro78r/cw14_dop.pdf?dl=0 Листок 14]
+
 
|-
 
|-
  || 09.04.20 || Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев. ||  
+
  || 12.04.21 || Степень булевой функции. Пример квадратичного разрыва между сертификатной сложностью и сложностью в модели разрешающих деревьев. ||  
 
Тот же листок
 
Тот же листок
 
|-
 
|-
  || 16.04.20 || Пример квадратичного разрыва между сертификатной сложностью и сложностью в модели разрешающих деревьев. Чувствительность и блочная чувствительность, квадратичный разрыв между ними. Сертификатная сложность не больше квадрата блочной чувствительности. ||  
+
  || 16.04.21 || Чувствительность и блочная чувствительность, квадратичный разрыв между ними. Сертификатная сложность не больше квадрата блочной чувствительности. ||
 
Тот же листок
 
Тот же листок
 
|-
 
|-
  || 20.04.20 || Балансирующие семейства множеств, верхние и нижние оценки. Полиномиальный метод. ||
+
  || 23.04.21 || Лемма о симметризации многочленов. Оценка на степень многочленов одной переменной. ||
[https://www.dropbox.com/s/l5wuz4wxmv8yc9d/cw15_dop.pdf?dl=0 Листок 15]
+
[https://www.dropbox.com/s/6l9eu9oqdwv7xfj/cw14_dop.pdf?dl=0 Листок 14]
 
|-
 
|-
  || 23.04.20 || Балансирующие семейства множеств, задачи. ||
+
  || 30.04.21 || Полиномиальная связь сложности в модели разрешающих деревьев и степени функции. Многочлены Чебышева, приближение булевых функций многочленами. ||
 +
Тот же листок
 +
|-
 +
|| 07.05.21 || Классы функций AC^i, NC^i, иерархия. Описание класса NC^0. Сложение чисел в AC^0. ||
 +
[https://www.dropbox.com/s/1p4f8yv6nr0kaz1/cw15_dop.pdf?dl=0 Листок 15]
 +
|-
 +
|| 14.05.21 || PARITY не лежит в AC^0, полиномиальный метод: схемы приближаемы многочленами. ||  
 
Тот же листок
 
Тот же листок
 
|-
 
|-
  || 27.04.20 || Полиномиальная связь сложности в модели разрешающих деревьев и степени функции. ||  
+
  || 21.05.21 || PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. || Тот же листок
Позапрошлый листок
+
|-
 +
|| 04.06.21 || Коммуникационная сложность. || 
 +
[https://www.dropbox.com/s/hstobjb6a4rpw5u/cw16_dop.pdf?dl=0 Листок 16]
 +
<!---
 
|-
 
|-
 
  || 30.04.20 || Вычисление булевых функций многочленами. ||  
 
  || 30.04.20 || Вычисление булевых функций многочленами. ||  
Строка 100: Строка 110:
 
  || 31.05.19 || PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. Плотные семейства множеств, необходимые и достаточные условия в терминах числа элементов. Наследственные множества. ||   
 
  || 31.05.19 || PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. Плотные семейства множеств, необходимые и достаточные условия в терминах числа элементов. Наследственные множества. ||   
 
[https://www.dropbox.com/s/fw61vkisl0bejfk/cw17_dop.pdf?dl=0 Листок 17]
 
[https://www.dropbox.com/s/fw61vkisl0bejfk/cw17_dop.pdf?dl=0 Листок 17]
 +
--->
 
|}
 
|}
  
--->
+
 
  
 
'''Первый семестр'''
 
'''Первый семестр'''
Строка 113: Строка 124:
 
|-  
 
|-  
 
|| 28.09.20 || Логика высказываний, ее корректность. Лемма о дедукции. || [https://www.dropbox.com/s/d3wz866zmdwo93t/cw02_dop.pdf?dl=0 Листок 2]  
 
|| 28.09.20 || Логика высказываний, ее корректность. Лемма о дедукции. || [https://www.dropbox.com/s/d3wz866zmdwo93t/cw02_dop.pdf?dl=0 Листок 2]  
<!---
 
 
|-  
 
|-  
|| 02.10.19 || Замкнутые классы булевых функций. Теорема Поста. || [https://www.dropbox.com/s/schzwqwjuhfkxxg/cw03_dop.pdf?dl=0 Листок 3]  
+
|| 05.10.20 || Замкнутые классы булевых функций. Теорема Поста. || [https://www.dropbox.com/s/6zbcjvpclruay74/cw03_dop.pdf?dl=0 Листок 3]  
 
|-  
 
|-  
|| 9.10.19 || Лемма Шпернера. Теорема Брауэра. || [https://www.dropbox.com/s/ip1brxsxv2oro2i/cw04_dop.pdf?dl=0 Листок 4]  
+
|| 12.10.20 || Лемма Шпернера. Теорема Брауэра. || [https://www.dropbox.com/s/88raglxnoxnrzd5/cw04_dop.pdf?dl=0 Листок 4]  
 
|-  
 
|-  
|| 30.10.19 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. Теорема о рекурсии, формулировка. || [https://www.dropbox.com/s/1e5reo01xrp4fio/cw05_dop.pdf?dl=0 Листок 5]
+
|| 26.10.20 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. Теорема о рекурсии, формулировка. || [https://www.dropbox.com/s/zgnf3lgg16fpvyz/cw05_dop.pdf?dl=0 Листок 5]
 
|-  
 
|-  
|| 06.11.19 || Теорема о рекурсии, доказательство. Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок  
+
|| 02.11.20 || Теорема о рекурсии, доказательство. Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок  
 
|-  
 
|-  
|| 13.11.19 || Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. ||  [https://www.dropbox.com/s/a75xfg3mpki942l/cw6_dop.pdf?dl=0 Листок 6]
+
|| 09.11.20 || Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. ||  [https://www.dropbox.com/s/ot0sb7lqhw5tp4g/cw6_dop.pdf?dl=0 Листок 6]
 
|-  
 
|-  
|| 20.11.19 || Гамильтоновы графы. Теорема Бонди-Хватала. Теорема Хватала о степенных последовательностях. ||  [https://www.dropbox.com/s/8bybyiy52v2cly1/cw07_dop.pdf?dl=0 Листок 7]
+
|| 16.11.20 || Гамильтоновы графы. Теорема Бонди-Хватала. Теорема Хватала о степенных последовательностях. ||  [https://www.dropbox.com/s/p72rxjlhwgfnjm5/cw07_dop.pdf?dl=0 Листок 7]
 
|-  
 
|-  
|| 27.11.19 || Потоки и разрезы. Теорема Форда-Фалкерсона. ||  [https://www.dropbox.com/s/pqo9ud4fvdqelan/cw08_dop.pdf?dl=0 Листок 8]
+
|| 23.11.20 || Потоки и разрезы. Теорема Форда-Фалкерсона. ||  [https://www.dropbox.com/s/4gsz3gg6cb2kxyx/cw08_dop.pdf?dl=0 Листок 8]
 
|-  
 
|-  
|| 29.11.18 || Разбор домашних заданий. ||
+
|| 30.11.20 || Миноры и топологические миноры. 2-связные и 3-связные графы. Теорема Эйлера о плоских графах. Теорема Куратовского. || [https://www.dropbox.com/s/s3hk6cqj8dhphg5/cw09_dop.pdf?dl=0 Листок 9]
 
|-  
 
|-  
|| 13.12.18 || Экзамен. ||  
+
|| 7.12.20 || Разбор задач листков 1-4. ||  
--->
+
 
|}
 
|}
  
Строка 139: Строка 148:
 
Числа Каталана: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf  Черновик учебника по дискретной математике] <br>
 
Числа Каталана: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.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>
 
Замкнутые классы булевых функций: [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>
 
Цепи и антицепи: [http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/  Stasys Jukna, Extremal Combinatorics] <br>
Теорема Бонди-Хватала:  [http://freeusermanuals.com/backend/web/manuals/1521810604HamiltonBondyAndChvatal.pdf http://freeusermanuals.com/backend/web/manuals/1521810604HamiltonBondyAndChvatal.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>
 
Планарные графы: Р. Дистель, Теория графов <br>
Неравенство Чернова: https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/lec9.pdf <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>
 
Комбинаторные игры: [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>
 +
<!---
 
Балансирующие семейства множеств: [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>
 
Приближение 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>
 
Приближение 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>
Строка 159: Строка 168:
 
Коды: [https://www.mccme.ru/~anromash/courses/coding-theory-2017.pdf А. Ромащенко, А. Румянцев, А. Шень, Заметки по теории кодирования] <br>
 
Коды: [https://www.mccme.ru/~anromash/courses/coding-theory-2017.pdf А. Ромащенко, А. Румянцев, А. Шень, Заметки по теории кодирования] <br>
 
Плотные множества: [http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/  Stasys Jukna, Extremal Combinatorics] <br>
 
Плотные множества: [http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/  Stasys Jukna, Extremal Combinatorics] <br>
 +
 +
Неравенство Чернова: https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/lec9.pdf <br>
 +
 
---->
 
---->
  

Текущая версия на 16:19, 4 июня 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
Комбинаторные игры: Черновик учебника по дискретной математике
Разрешающие деревья: Обзор по теме

Результаты