|
|
| (не показано 20 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| ==ОБЪЯВЛЕНИЯ== | | ==ОБЪЯВЛЕНИЯ== |
|
| |
|
| [https://t.me/+I4zYZBIKFisxNzky Группа курса] | | Чаты: [https://t.me/+My8o4LtxHaFiYTli всего курса], [https://t.me/+nHTUUMmFBBRlMjUy группы П], [https://t.me/+9tkRX3EjBdlhYTZi группы П+]. |
| | |
| | Контрольная 1 состоится 7 октября во время семинара. |
|
| |
|
| ==Дедлайны== | | ==Дедлайны== |
| ДЗ 1: <i>15 сентября, 18:10</i>
| |
|
| |
|
| ДЗ 2: <i>22 сентября, 18:10</i> | | ДЗ 1: 18 сентября, 23:59; |
|
| |
|
| ДЗ 3: <i>27 сентября, 23:59</i> | | ДЗ 2: 02 октября, 23:59; |
|
| |
|
| == Общая информация о курсе Комбинаторика и теория графов, М++, 1 курс== | | ДЗ 3: 16 октября, 23:59. |
| | |
| | == Общая информация о курсе Топология, М++, 1 курс== |
|
| |
|
| === Преподаватели и ассистенты=== | | === Преподаватели и ассистенты=== |
|
| |
|
| Лектор: [https://www.hse.ru/org/persons/310667694 Артём Максимович Максаев] | | Лектор: [https://www.hse.ru/org/persons/768859984/ Федор Юрьевич Попеленский] |
| | |
| Семинарист: [https://www.hse.ru/org/persons/225516943 Иван Сергеевич Бельдиев]
| |
|
| |
|
| Ассистенты: [https://t.me/petr_kramarsky Пётр Крамарский], [https://t.me/misha_dalinger Михаил Далингер], [https://t.me/JafoNoksy Андрей Кандрашкин]
| | Семинарист: [https://www.hse.ru/org/persons/208521245/ Василий Юрьевич Рождественский] |
|
| |
|
| === Таблица оценок=== | | === Таблица оценок=== |
|
| |
|
| [https://docs.google.com/spreadsheets/d/1YYJm1Zp9lBwohnh1sBmO9gQ-Cx1N6WMB8yRRzpM7O2U/edit?usp=sharing Ведомость] | | [Ведомость] |
|
| |
|
| ===Правила оценивания=== | | ===Правила оценивания=== |
|
| |
|
| Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Один раз за весь курс домашнее задание разрешается сдать на неделю позже срока без потери баллов (предварительно уведомив ассистента).
| |
|
| |
| Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится по тем же правилам в письменном формате (передаётся только экзамен, формула учитывает накопленную за курс оценку по остальным элементам контроля).
| |
|
| |
|
| ===Оценка за курс=== | | ===Оценка за курс=== |
|
| |
| '''Итоговая оценка''' = ''Округление(0.25 * ДЗ + 0.35 * КОЛЛ + 0.4 * ЭКЗ)''
| |
|
| |
| В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. Округление арифметическое.
| |
|
| |
|
| == Контрольные мероприятия == | | == Контрольные мероприятия == |
|
| |
|
| | === Домашние задания=== |
|
| |
|
| ==Программа курса==
| | [Кондуит] |
|
| |
|
| ''Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.''
| | # Группа П: 1,4,6,8,9,10,18,20,21,24 (Л.1); Группа П+: 1,4,6,8,9,10,20,21,24 (Л.1). |
| | # Группа П: 2,4,8,10,11,13,14,15,21 (Л.2); Группа П+: 2,4,8,10,13,14,15,21 (Л.2). |
| | # Группа П: 1,3,7,8,9,15,19,20,21,24 (Л.3); Группа П+: 1,7,8,9,15,19,20,21,24 (Л.3). |
|
| |
|
| '''Лекция 1'''. Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами, знакомство с аксиоматикой ZFC. Доказательство теоретико-множественных тождеств. Упорядоченная пара, декартово произведение множеств. Определение функции, ее области определения и области значений, образа и полного прообраза множества. Инъекции, сюръекции, биекции. Примеры.
| | === Контрольные === |
|
| |
|
| ''Литература: [1, §5.1-5.2, §6.3-6.4]''
| | Контрольная 1 состоится 7 октября |
|
| |
|
| '''Онлайн лекция 1'''. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.
| | ==Программа курса== |
| | |
| ''Литература: [1, лекция 2, §5.6]''
| |
| | |
| '''Лекция 2'''.
| |
| Бинарные отношения, теорема об ассоциативности композиции отношений.
| |
| Композиция всюду определенных функций, ее ассоциативность. Обратная функция, критерий биективности функции. Утверждение о композиции биекций. Отношение эквивалентности, теорема о разбиении множества с отношением эквивалентности на классы, состоящие из попарно эквивалентных элементов.
| |
| Булевы функции, основные логические связки. Задание булевых функций таблицами истинности, количество булевых функций от n переменных. Простейшие тождества алгебры логики. Дизъюнктивная нормальная форма, теорема о существовании ДНФ для любой булевой функции. Совершенная дизъюнктивная нормальная форма (СДНФ). Многочлены Жегалкина. Теорема о представлении булевой функции многочленом Жегалкина (формулировка).
| |
| | |
| ''Литература: [1, лекция 7, §6.4-6.5, §5.3-5.5]''
| |
| | |
| '''Онлайн лекция 2'''. Графы, основные понятия (степень вершины, путь, цикл, простой путь, простой цикл). Лемма о рукопожатиях. Связность графа, компоненты связности. Неравенство, связывающее число вершин, ребер и компонент связности в графе. Деревья. Теорема об эквивалентных определениях дерева. Полное двоичное дерево. Остовное дерево в графе.
| |
| | |
| ''Литература: [1, §3.1-3.2]''
| |
| | |
| '''Лекция 3.''' Теорема о представлении булевой функции многочленом Жегалкина.
| |
| Полные системы связок, достаточное условие полноты системы. Полнота системы связок «конъюнкция, дизъюнкция, отрицание» и «конъюнкция, отрицание». Полнота системы связок «XOR, конъюнкция, 1». Замкнутые классы булевых функций. Классы линейных, монотонных, самодвойственный функций, а также функций, сохраняющих константу. Критерий Поста (без доказательства). Двудольные графы, критерий двудольности графа. Раскраски графов, хроматическое число графа. Свойства хроматического числа. Верхняя оценка на хроматическое число через максимальную из степеней вершин графа. Теорема Брукса (без доказательства). Хроматический многочлен, его вычисление для полного графа, пустого графа и дерева. Теорема Уитни о свойствах хроматического многочлена (формулировка).
| |
| | |
| ''Литература: [1, §5.4-5.5, §3.4-3.5], [3, глава 1, §5-6]''
| |
| | |
| '''Лекция 4.''' Лемма о связи хроматического многочлена графа, графа с удаленным ребром и стянутым ребром. Теорема Уитни о свойствах хроматического многочлена (доказательство). Мыцельскиан графа. Пример Зыкова–Мыцельского графа без треугольников со сколь угодно большим хроматическим числом. Числа Рамсея. Теорема Рамсея. Верхняя оценка на числа Рамсея.
| |
| | |
| ''Литература: [1, §3.6]''
| |
| | |
| '''Лекция 5 (план).''' Паросочетание и вершинное покрытие в графе. Утверждение о связи максимального размера паросочетания и минимального размера вершинного покрытия в произвольном графе. Чередующийся и увеличивающий пути относительно паросочетания. Отсутствие увеличивающего пути относительно максимального паросочетания. Теорема Кёнига. Условие Холла для двудольного графа, теорема Холла. Графы Турана, подсчет числа ребер в них. Теорема Турана о максимальном числе ребер в графе с заданным кликовым числом.
| |
| | |
| ''Литература: [1, §1.11], [8, теорема 2.1.1]''
| |
|
| |
|
| == Материалы курса == | | == Материалы курса == |
|
| |
|
| [https://drive.google.com/file/d/1hRJ-A-m7DqGFztgbuZFBnVYBA3Wama2_/view?usp=sharing Листок 1. Перечислительная комбинаторика] | | === Листки === |
| | [https://disk.yandex.ru/i/VAWoeSzGKVyhRw Листок 1. Топологические пространства и непрерывные отображения] |
|
| |
|
| [https://drive.google.com/file/d/19hk8193zMSkruyNcRv6axq533Km2F13B/view?usp=sharing Листок 2. Множества и функции] | | [https://disk.yandex.ru/i/x43ZY0-eUxvawQ Листок 2. Компактность и гомеоморфность] |
|
| |
|
| [https://drive.google.com/file/d/1-VUGbu8E_6uok1lN1tQN9imHuiRRN6mo/view?usp=sharing Листок 3. Булевы функции] | | [https://disk.yandex.ru/i/wWsjvy2Rwvl6WQ Листок 3. Базы, связность и продолжение компактности] |
|
| |
|
| [https://drive.google.com/file/d/1EH6BbXg0ucQQC4UtH1GiLZonkpAEquCg/view?usp=sharing Листок 4. Хроматическое число и хроматический многочлен графа]
| | === Записи лекций === |
|
| |
|
| [https://drive.google.com/file/d/1bYxesUWWcBgQtQDrWCGF5WXzshe5D_Xn/view?usp=sharing Листок 5. Теоремы Холла, Кёнига, Турана и Рамсея] | | # [https://disk.yandex.ru/i/Kgxmsj5Fdb6ZUQ Конспект лекции 1] |
| | # [https://disk.yandex.ru/i/3q2dFetMxKwEKQ Конспект лекции 2] |
| | # [https://disk.yandex.ru/i/gvQXULrWjNTDdA Конспект лекции 3] |
| | # [https://disk.yandex.ru/i/_vkx252xfjJ6Xg Конспект лекции 4] |
|
| |
|
| == Записи лекций == | | == Литература == |
|
| |
|
| На курсе есть две предзаписанные онлайн-лекции:
| | === Основная литература === |
|
| |
|
| папка LEC 01 - [https://disk.yandex.ru/d/-xv1z4M1iXNoNw лекция по базовой комбинаторике] (просьба посмотреть до '''7.09''');
| | # A. Hatcher - Notes on Introductory Point-Set Topology (доступно [https://pi.math.cornell.edu/~hatcher/Top/TopNotes.pdf по сслыке]). |
| | # John M. Lee - Introduction to Topological Manifolds. |
| | # А.Т. Фоменко, Д.Б. Фукс - Курс гомотопической топологии. |
| | # А. Хатчер - Алгебраическая топология (продается в [https://biblio.mccme.ru книжном МЦНМО]). |
| | # Т.Е. Панов - Введение в алгебраическую топологию (продается в [https://biblio.mccme.ru книжном МЦНМО]). |
| | # О.Я. Виро, Н. Ю. Нецветаев, О.А. Иванов, В.М. Харламов - Элементарная топология (продается в [https://biblio.mccme.ru книжном МЦНМО]). |
|
| |
|
| папка LEC 02 - [https://disk.yandex.ru/d/TnBxjd8ZBlQENA лекция по основам теории неориентированных графов] (просьба посмотреть до '''21.09''');
| | === Дополнительная литература === |
| | |
| == Литература == | |
|
| |
|
| # М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. [https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf Черновик этого учебника.] В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ). | | # M. Crossley - Essential topology. |
| # Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306 | | # J. Munkres - Topology. |
| # Яблонский С. В. Введение в дискретную математику. 4-е издание, стереотипное - М.: Высшая школа, 2003. - 484 с. | | # К. Рук, В. Сандерсон - Введение в кусочно-линейную топологию. |
| # Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from https://archive.org/details/discretemathemat0000lova/page/n9/mode/2up | | # У. Масси, Дж. Столлингс - Алгебраическая топология: Введение. |
| # Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: https://znanium.com/catalog/document?id=343807 | | # Дж. Милнор, Дж. Уоллес - Дифференциальная топология: начальный курс. |
| # Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144 с. | | # Г. Зейферт, В. Трельфалль - Топология. |
| # А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. — 2-е изд., испр. и доп. — М.: МЦНМО, 2017. — 88 с. URL: https://users.mccme.ru/anromash/courses/coding-theory-2017.pdf
| |
| # Р. Дистель, "Теория графов", второе издание, 2002, Springer, Graduate Texts in Mathematics, 173 https://books.google.ru/books?id=pZm8AAAAQBAJ&hl=ru&source=gbs_navlinks_s
| |