Топология
ОБЪЯВЛЕНИЯ
Дедлайны
ДЗ 1: 18 сентября, 23:59
ДЗ 2: 02 октября, 23:59
ДЗ 3: 16 октября, 23:59
Общая информация о курсе Топология, М++, 1 курс
Преподаватели и ассистенты
Лектор: Федор Юрьевич Попеленский
Семинарист: Иван Сергеевич Бельдиев
Ассистенты: Пётр Крамарский, Михаил Далингер, Андрей Кандрашкин
Таблица оценок
Правила оценивания
Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Один раз за весь курс домашнее задание разрешается сдать на неделю позже срока без потери баллов (предварительно уведомив ассистента).
Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится по тем же правилам в письменном формате (передаётся только экзамен, формула учитывает накопленную за курс оценку по остальным элементам контроля).
Оценка за курс
Итоговая оценка = Округление(0.25 * ДЗ + 0.35 * КОЛЛ + 0.4 * ЭКЗ)
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. Округление арифметическое.
Контрольные мероприятия
Программа курса
Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.
Лекция 1. Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами, знакомство с аксиоматикой ZFC. Доказательство теоретико-множественных тождеств. Упорядоченная пара, декартово произведение множеств. Определение функции, ее области определения и области значений, образа и полного прообраза множества. Инъекции, сюръекции, биекции. Примеры.
Литература: [1, §5.1-5.2, §6.3-6.4]
Онлайн лекция 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]
Материалы курса
Листок 1. Перечислительная комбинаторика
Листок 4. Хроматическое число и хроматический многочлен графа
Листок 5. Теоремы Холла, Кёнига, Турана и Рамсея
Записи лекций
На курсе есть две предзаписанные онлайн-лекции:
папка LEC 01 - лекция по базовой комбинаторике (просьба посмотреть до 7.09);
папка LEC 02 - лекция по основам теории неориентированных графов (просьба посмотреть до 21.09);
Литература
- М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. Черновик этого учебника. В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
- Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
- Яблонский С. В. Введение в дискретную математику. 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