Комбинаторика и теория графов 2026/2027

ОБЪЯВЛЕНИЯ

Группа курса

Дедлайны

ДЗ 1: 15 сентября, 18:10

Общая информация о курсе Комбинаторика и теория графов, М++, 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]

Материалы курса

Листок 1. Перечислительная комбинаторика

Листок 2. Множества и функции

Листок 3. Булевы функции

Записи лекций

На курсе есть две предзаписанные онлайн-лекции:

папка LEC 01 - лекция по базовой комбинаторике (просьба посмотреть до 7.09);

папка LEC 02 - лекция по основам теории неориентированных графов (просьба посмотреть до 21.09);

Литература

1. М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. Черновик этого учебника. В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
2. Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
3. Яблонский С. В. Введение в дискретную математику. 4-е издание, стереотипное - М.: Высшая школа, 2003. - 484 с.
4. 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
5. Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: https://znanium.com/catalog/document?id=343807
6. Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144 с.
7. А. Ромащенко, А. Румянцев, А. Шень. Заметки по теории кодирования. — 2-е изд., испр. и доп. — М.: МЦНМО, 2017. — 88 с. URL: https://users.mccme.ru/anromash/courses/coding-theory-2017.pdf
8. Р. Дистель, "Теория графов", второе издание, 2002, Springer, Graduate Texts in Mathematics, 173 https://books.google.ru/books?id=pZm8AAAAQBAJ&hl=ru&source=gbs_navlinks_s