https://wikicshse.ru/index.php?action=history&feed=atom&title=Dopglavy_DM_2021
Dopglavy DM 2021 - История изменений
2026-06-06T13:28:38Z
История изменений этой страницы в вики
MediaWiki 1.45.3
https://wikicshse.ru/index.php?title=Dopglavy_DM_2021&diff=251&oldid=prev
imported>Vpodolskii: Migrated current public revision from wiki.cs.hse.ru
2021-06-04T13:19:37Z
<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>== Общая информация ==<br />
<br />
[http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/grading.pdf Правила выставления оценок] <br><br />
<br />
<br />
<br />
Первый дедлайн по домашним заданиям: <span>26.10.20</span><br><br />
<br />
<!---<br />
<br />
Второй дедлайн по домашним заданиям: <s>01.06.20</s> <span style="color:red">31.05.20</span><br><br />
<br />
---><br />
<br />
<!---<br />
<br />
<span style="color:red"><font size="10">Занятие 19.03.20 не состоится!</font></span> <br><br />
<br />
<br />
<span style="color:red"><font size="10">Занятие 05.03.20 не состоится!</font></span> <br><br />
<br />
Экзамен будет проходить на неделе с 16 декабря по 20 декабря. Будет доступно несколько возможностей по времени.<br />
<br />
---><br />
<br />
== Расписание ==<br />
<br />
Занятия проходят по понедельникам в 18:10 в аудитории R408. Первое занятие прошло 21 сентября.<br />
<br />
<!---<br />
<br />
Занятия проходят по четвергам с 13:40 до 15:00 в ауд. G004.<br />
<br />
---><br />
<br />
== Материалы курса ==<br />
<br />
<br />
<br />
<br />
'''Второй семестр'''<br />
<br />
{| class="wikitable"<br />
|-<br />
! Дата !! Summary !! Домашнее задание<br />
|-<br />
|| 25.01.21 || Разбор задач листков 4-9. || <br />
|-<br />
|| 01.02.21 || Вероятностный алгоритм для проверки чисел на простоту. || [https://www.dropbox.com/s/slsedwws4hqzj74/cw10_dop.pdf?dl=0 Листок 10] <br />
|-<br />
|| 15.02.21 || Линейные рекуррентные соотношения с постоянными коэффициентами. Решение рекуррентных соотношений с помощью производящих функций. || [https://www.dropbox.com/s/efhv45nmxdga0ew/cw11_dop.pdf?dl=0 Листок 11] <br />
|-<br />
|| 22.02.21 || Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. || <br />
[https://www.dropbox.com/s/fzt2nkc6k0g56v3/cw12_dop.pdf?dl=0 Листок 12] <br />
|-<br />
|| 01.03.21 || Разрешающие деревья, примеры. || <br />
[https://www.dropbox.com/s/dr9sfvk7bjjqs12/cw13_dop.pdf?dl=0 Листок 13] <br />
|-<br />
|| 22.03.21 || Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев. || <br />
Тот же листок<br />
|-<br />
|| 12.04.21 || Степень булевой функции. Пример квадратичного разрыва между сертификатной сложностью и сложностью в модели разрешающих деревьев. || <br />
Тот же листок<br />
|-<br />
|| 16.04.21 || Чувствительность и блочная чувствительность, квадратичный разрыв между ними. Сертификатная сложность не больше квадрата блочной чувствительности. ||<br />
Тот же листок<br />
|-<br />
|| 23.04.21 || Лемма о симметризации многочленов. Оценка на степень многочленов одной переменной. ||<br />
[https://www.dropbox.com/s/6l9eu9oqdwv7xfj/cw14_dop.pdf?dl=0 Листок 14]<br />
|-<br />
|| 30.04.21 || Полиномиальная связь сложности в модели разрешающих деревьев и степени функции. Многочлены Чебышева, приближение булевых функций многочленами. || <br />
Тот же листок <br />
|-<br />
|| 07.05.21 || Классы функций AC^i, NC^i, иерархия. Описание класса NC^0. Сложение чисел в AC^0. || <br />
[https://www.dropbox.com/s/1p4f8yv6nr0kaz1/cw15_dop.pdf?dl=0 Листок 15]<br />
|-<br />
|| 14.05.21 || PARITY не лежит в AC^0, полиномиальный метод: схемы приближаемы многочленами. || <br />
Тот же листок<br />
|-<br />
|| 21.05.21 || PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. || Тот же листок<br />
|-<br />
|| 04.06.21 || Коммуникационная сложность. || <br />
[https://www.dropbox.com/s/hstobjb6a4rpw5u/cw16_dop.pdf?dl=0 Листок 16]<br />
<!---<br />
|-<br />
|| 30.04.20 || Вычисление булевых функций многочленами. || <br />
[https://www.dropbox.com/s/vy6jxxp4v4juazn/cw16_dop.pdf?dl=0 Листок 16] <br />
|-<br />
|| 07.05.20 || Классы функций AC^i, NC^i, иерархия. Описание класса NC^0. Сложение чисел в AC^0. || <br />
[https://www.dropbox.com/s/y03hqsgakhq9bzf/cw17_dop.pdf?dl=0 Листок 17]<br />
|-<br />
|| 18.05.20 || PARITY не лежит в AC^0, полиномиальный метод: схемы приближаемы многочленами. || <br />
Тот же листок<br />
|-<br />
|| 21.05.20 || PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. || <br />
Тот же листок<br />
|-<br />
|| 22.05.20 || PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. || <br />
Тот же листок<br />
|-<br />
|| 28.05.20 || Комбинаторная теорема о нулях. || <br />
[https://www.dropbox.com/s/20gq1wd0d5yhzsn/cw18_dop.pdf?dl=0 Листок 18]<br />
|-<br />
|| 15.04.19 || Коды исправляющие ошибки, напоминание. Код Хэмминга. Граница Синглтона. Код Рида-Соломона. Усиление границы Хэмминга для двоичных кодов. || <br />
[http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw15_dop.pdf Листок 15]<br />
|-<br />
|| 23.05.19 || Классы функций AC^i, NC^i, иерархия. PARITY не лежит в NC^0. Сложение чисел в AC^0. PARITY не лежит в AC^0, полиномиальный метод: схемы приближаемы многочленами. || <br />
[https://www.dropbox.com/s/flbcgrbqto0dlfa/cw16_dop.pdf?dl=0 Листок 16]<br />
|-<br />
|| 31.05.19 || PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. Плотные семейства множеств, необходимые и достаточные условия в терминах числа элементов. Наследственные множества. || <br />
[https://www.dropbox.com/s/fw61vkisl0bejfk/cw17_dop.pdf?dl=0 Листок 17]<br />
---><br />
|}<br />
<br />
<br />
<br />
'''Первый семестр'''<br />
<br />
{| class="wikitable"<br />
|-<br />
! Дата !! Summary !! Домашнее задание<br />
|-<br />
|| 21.09.20 || Числа Каталана. Рекурсивное определение и определение через баланс скобок, их эквивалентность. Рекуррентная формула для чисел Каталана. Выводы формулы для чисел Каталана: метод отражений. || [https://www.dropbox.com/s/g79axcz2onrco0p/cw01_dop.pdf?dl=0 Листок 1]<br />
|- <br />
|| 28.09.20 || Логика высказываний, ее корректность. Лемма о дедукции. || [https://www.dropbox.com/s/d3wz866zmdwo93t/cw02_dop.pdf?dl=0 Листок 2] <br />
|- <br />
|| 05.10.20 || Замкнутые классы булевых функций. Теорема Поста. || [https://www.dropbox.com/s/6zbcjvpclruay74/cw03_dop.pdf?dl=0 Листок 3] <br />
|- <br />
|| 12.10.20 || Лемма Шпернера. Теорема Брауэра. || [https://www.dropbox.com/s/88raglxnoxnrzd5/cw04_dop.pdf?dl=0 Листок 4] <br />
|- <br />
|| 26.10.20 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. Теорема о рекурсии, формулировка. || [https://www.dropbox.com/s/zgnf3lgg16fpvyz/cw05_dop.pdf?dl=0 Листок 5]<br />
|- <br />
|| 02.11.20 || Теорема о рекурсии, доказательство. Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок <br />
|- <br />
|| 09.11.20 || Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. || [https://www.dropbox.com/s/ot0sb7lqhw5tp4g/cw6_dop.pdf?dl=0 Листок 6]<br />
|- <br />
|| 16.11.20 || Гамильтоновы графы. Теорема Бонди-Хватала. Теорема Хватала о степенных последовательностях. || [https://www.dropbox.com/s/p72rxjlhwgfnjm5/cw07_dop.pdf?dl=0 Листок 7]<br />
|- <br />
|| 23.11.20 || Потоки и разрезы. Теорема Форда-Фалкерсона. || [https://www.dropbox.com/s/4gsz3gg6cb2kxyx/cw08_dop.pdf?dl=0 Листок 8]<br />
|- <br />
|| 30.11.20 || Миноры и топологические миноры. 2-связные и 3-связные графы. Теорема Эйлера о плоских графах. Теорема Куратовского. || [https://www.dropbox.com/s/s3hk6cqj8dhphg5/cw09_dop.pdf?dl=0 Листок 9] <br />
|- <br />
|| 7.12.20 || Разбор задач листков 1-4. || <br />
|}<br />
<br />
== Источники ==<br />
<br />
Числа Каталана: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf Черновик учебника по дискретной математике] <br><br />
Логика высказываний: [https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf Верещагин, А. Шень, Языки и исчисления.] <br><br />
Замкнутые классы булевых функций: [https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf Верещагин, А. Шень, Языки и исчисления.] <br><br />
Лемма Шпернера, теорема Брауэра: [http://math.mit.edu/~fox/MAT307-lecture03.pdf http://math.mit.edu/~fox/MAT307-lecture03.pdf] <br><br />
Вполне упорядоченные множества: [https://www.mccme.ru/free-books/shen/shen-logic-part1-2.pdf Верещагин, А. Шень, Начала теории множеств.] <br><br />
Цепи и антицепи: [http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/ Stasys Jukna, Extremal Combinatorics] <br><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 />
Планарные графы: Р. Дистель, Теория графов <br><br />
Вероятностный алгоритм проверки чисел на простоту: Michael Sipser, Introduction to the Theory of Computation <br><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><br />
Комбинаторные игры: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf Черновик учебника по дискретной математике] <br><br />
Разрешающие деревья: [https://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Обзор по теме] <br><br />
<!---<br />
Балансирующие семейства множеств: [https://eccc.weizmann.ac.il/report/2019/026/ https://eccc.weizmann.ac.il/report/2019/026/] <br><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><br />
Булевы схемы: [http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html Stasys Jukna, Boolean Function Complexity: Advances and Frontiers] <br><br />
Комбинаторная теорема о нулях: [https://www.cs.tau.ac.il/~nogaa/PDFS/null2.pdf N. Alon, Combinatorial Nullstellensatz]<br />
Многочлены для булевых функций: [http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html Stasys Jukna, Boolean Function Complexity: Advances and Frontiers] <br><br />
Коды: [https://www.mccme.ru/~anromash/courses/coding-theory-2017.pdf А. Ромащенко, А. Румянцев, А. Шень, Заметки по теории кодирования] <br><br />
Плотные множества: [http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/ Stasys Jukna, Extremal Combinatorics] <br><br />
<br />
Неравенство Чернова: https://www.cs.cmu.edu/afs/cs/academic/class/15859-f04/www/scribes/lec9.pdf <br><br />
<br />
----><br />
<br />
== Результаты ==<br />
<br />
<!---<br />
[https://docs.google.com/spreadsheets/d/1APlELzEBiOdP1fos8F9sjtZFQQzJ4FZVBDfGTnjtt8s/edit?usp=sharing Таблица результатов]<br />
<br />
---></div>
imported>Vpodolskii