Dopglavy DM 1920 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(Новая страница: «== Общая информация == [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 Таблица результатов] | ||
| + | ---!> | ||
Версия 09:19, 18 сентября 2019
Общая информация
Расписание
Первое занятие пройдет 18 сентября с 16:40 до 18:00 в ауд. R306.
Последующие занятия будут проходить по средам с 16:40 до 18:00 в ауд. D510.
Материалы курса
| Дата | Summary | Домашнее задание |
|---|
