Dopglavy DM 1920: различия между версиями
Перейти к навигации
Перейти к поиску
Новая страница: «== Общая информация == [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/grading.pdf Правила выставления оценок] == Р…» |
Нет описания правки |
||
| Строка 7: | Строка 7: | ||
Первое занятие пройдет 18 сентября с 16:40 до 18:00 в ауд. R306. <br> | Первое занятие пройдет 18 сентября с 16:40 до 18:00 в ауд. R306. <br> | ||
Последующие занятия будут проходить по средам с 16:40 до 18:00 в ауд. D510. | Последующие занятия будут проходить по средам с 16:40 до 18:00 в ауд. D510. | ||
== Материалы курса == | |||
{| class="wikitable" | |||
|- | |||
! Дата !! Summary !! Домашнее задание | |||
<!--- |- | |||
|| 19.09.18 || Числа Каталана. Рекурсивное определение и определение через баланс скобок, их эквивалентность. Рекуррентная формула для чисел Каталана. Выводы формулы для чисел Каталана: метод отражений и метод поворотов. || [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw01_dop.pdf Листок 1] | |||
|- | |||
|| 26.09.18 || Вычисление булевых функций многочленами. Существование многочлена для всякой функции. Формула для коэффициентов. Симметризация многочленов. || [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw02_dop.pdf Листок 2] | |||
|- | |||
|| 04.10.18 || Замкнутые классы булевых функций. Теорема Поста. || [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw03_dop.pdf Листок 3] | |||
|- | |||
|| 11.10.18 || Лемма Шпернера. Теорема Брауэра. || [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw04_dop.pdf Листок 4] | |||
|- | |||
|| 01.11.18 || Вполне упорядоченные множества, их свойства. Начальные отрезки, их свойства. Рекурсия. || [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw05_dop.pdf Листок 5] | |||
|- | |||
|| 08.11.18 || Рекурсия. Из двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого. Теорема Цермело. || Тот же листок | |||
|- | |||
|| 15.11.18 || Разбиение булевого куба на симметричные плотные цепи, приложение. Теорема Шпернера, LYM неравенство. || [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw6_dop.pdf Листок 6] | |||
|- | |||
|| 22.11.18 || Гамильтоновы графы. Теорема Бонди-Хватала. Теорема Хватала о степенных последовательностях. || [http://www.mi.ras.ru/~podolskii/files/extra_dm_1819/cw07_dop.pdf Листок 7] | |||
|- | |||
|| 29.11.18 || Разбор домашних заданий. || | |||
|- | |||
|| 13.12.18 || Экзамен. || ---!> | |||
|} | |||
== Источники == | |||
Числа Каталана: [http://rubtsov.su/public/hse/2017/DM-HSE-Draft.pdf Черновик учебника по дискретной математике] <br> | |||
<!--- | |||
Многочлены для булевых функций: [http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html Stasys Jukna, Boolean Function Complexity: Advances and Frontiers] <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-part2-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://freeusermanuals.com/backend/web/manuals/1521810604HamiltonBondyAndChvatal.pdf http://freeusermanuals.com/backend/web/manuals/1521810604HamiltonBondyAndChvatal.pdf] <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> | |||
Рекурренты: [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://www.mccme.ru/~anromash/courses/coding-theory-2017.pdf А. Ромащенко, А. Румянцев, А. Шень, Заметки по теории кодирования] <br> | |||
Балансирующие семейства множеств: [https://eccc.weizmann.ac.il/report/2019/026/ https://eccc.weizmann.ac.il/report/2019/026/] <br> | |||
Булевы схемы: [http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html Stasys Jukna, Boolean Function Complexity: Advances and Frontiers] <br> | |||
Плотные множества: [http://www.thi.informatik.uni-frankfurt.de/~jukna/EC_Book_2nd/ Stasys Jukna, Extremal Combinatorics] <br> | |||
---!> | |||
== Результаты == | |||
<!--- | |||
[https://docs.google.com/spreadsheets/d/1HBHRwMA6X0a_j83Zyw7A-5squiY9nw-6eFdp0RCNEKg/edit?usp=sharing Таблица результатов] | |||
---!> | |||
Версия от 06:19, 18 сентября 2019
Общая информация
Расписание
Первое занятие пройдет 18 сентября с 16:40 до 18:00 в ауд. R306.
Последующие занятия будут проходить по средам с 16:40 до 18:00 в ауд. D510.
Материалы курса
| Дата | Summary | Домашнее задание |
|---|