Дискретная математика на ПМИ 2025/2026 (пилотный поток)
Содержание
ОБЪЯВЛЕНИЯ
Канал, где дублируются важные объявления курса (рекомендуем подписаться): LINK
____________________
Первый коллоквиум пройдет в субботу 29 ноября. Файл с правилами и программой коллоквиума выложен ниже. Расписание коллоквиума по группам будет позже.
Обратите внимание, что в коллоквиум войдет в том числе и материал следующей лекции 18.11 (вопросы 33-34 из определений и вопросы 24-25 из доказательств). Касаемо задач, в коллоквиум войдут задачи из первых 10 семинарских листков и первых 9 ДЗ.
Ниже приложено расписание коллоквиума по группам (аудитория R401). Приходить необходимо со своей группой. Пользоваться на коллоквиуме материалами (ни бумажными, ни электронными) нельзя. Бумагу для любых записей тоже выдаем мы.
группа 254 - 10:00
группа 253 - 11:00
группа 255 - 12:00
группа 251 - 13:30
группа 256 - 14:30
группа 252 - 15:30
____________________
Лекция 21.10 НЕ состоится и переносится на четверг, 16.10, 13:00-14:20. (Семинар у группы 251 21.10 тоже не состоится и переносится на четверг 16.10, 14:40-16:00.)
Лекции 4.11 НЕ будет ввиду государственного праздника. Она переносится на 7 ноября, 9:30-10:50.
__________________________
5 ноября, 18:00-20:00, состоится контрольная работа по материалам лекций и семинаров 1 модуля. В контрольной будет 5 задач на следующие темы:
- Индукция
- Перечислительная комбинаторика
- Множества и функции
- Булевы функции: ДНФ, многочлены Жегалкина
- Замкнутые классы булевых функций, критерий Поста
- Мощности множеств, счетные и континуальные множества, сравнение мощностей
Пользоваться материалами (ни бумажными, ни электронными) нельзя. Допускается использование лишь стандартного калькулятора (хотя едва ли он пригодится).
Длительность работы: 90 минут.
Распределение групп по аудиториям:
R503 - группы 253, 255
R201 - группы 251, 254, 256, подгруппа 252-2
M203 - подгруппа 252-1
Пожалуйста, не опаздывайте: не позднее 18:10 мы раздадим всем условия задач и начнем отсчет времени (длительность работы – 90 минут).
Лабораторная работа 1
Лабораторная работа состоит из двух частей: контеста (точнее, двух) с алгоритмическими задачами и ноутбука по библиотеке NetworkX, которые оцениваются по отдельности, подробности см. в классруме. На выполнение работы дается примерно три недели, дедлайн 1 декабря в 23:59. Дедлайн строгий, работы после дедлайна не принимаются.
Оценка за лабораторную работу вычисляется по формуле: ЛАБ-1 = sqrt(НОУТБУК^0.5 * КОНТЕСТ^1.5). Максимальная оценка за обе части равна 12, максимальная возможная оценка за лабораторную работу также 12.
По любым вопросам по лабораторной работе стоит писать ответственному ассистенту Исмаилу Велиджанову.
Общая информация о курсе Дискретная математика, пилотный поток, 1 курс
Преподаватели и ассистенты
Лекции: Артём Максимович Максаев
Распределение по группам
| Группа | Преподаватель | Консультационные часы преподавателя | Учебные ассистенты, отвечающие за группу |
|---|---|---|---|
| 251 | Артём Максимович Максаев | пятница, 14:40-16:00, T909 (по предварительной договоренности) | Дарья Линиченко, Борис Молонов |
| 252 | Михаил Викторович Игнатьев | среда 14:40-16:00, S812 (по предварительной договорённости) | Илья Кардашевский, Николай Маскин |
| 253 | Иван Сергеевич Бельдиев | понедельник, 13:00-14:20, S805 (по предварительной договорённости) | Илья Константинов, Айдар Хасанов |
| 254 | Валентин Валерьевич Промыслов | вторник, 18:10-19:30, T909 (по предварительной договоренности) | Вячеслав Гордеев, Георгий Одновол |
| 255 | Екатерина Денисовна Преснова | вторник, 18:10-19:30, S812 (по предварительной договоренности) | Григорий Служак, Евгений Степичев |
| 256 | Иван Сергеевич Бельдиев | понедельник, 13:00-14:20, S805 (по предварительной договорённости) | Александр Дарчиев, Степан Потапенко |
Ассистент, ответственный за лабораторные работы: Исмаил Велиджанов
Правила оценивания
Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Трижды за весь курс (1-3 модули) домашнее задание разрешается сдать на неделю позже срока без потери баллов.
Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится по тем же правилам в письменном формате (передаётся только экзамен, формула учитывает накопленную за курс оценку по остальным элементам контроля).
Оценка за курс в сессию после 2 модуля считается по формуле:
Промежуточная оценка = Округление(0.25 * ДЗ + 0.15 * КР + 0.25 * КОЛЛ-1 + 0.05 * ЛАБ-1 + 0.3 * ЭКЗ-1), где ДЗ – оценка за первые 9-12 домашних заданий (точное число будет объявлено в начале декабря), КР — оценка за контрольную работу, КОЛЛ-1 – оценка за коллоквиум-1, ЛАБ-1 – оценка за лабораторную работу-1, ЭКЗ-1 – оценка за экзамен-1.
Итоговая оценка за курс в сессию после 3 модуля считается по формуле:
Итоговая оценка = Округление(0.25 * ДЗ + 0.1 * КОЛЛ-1 + 0.2 * КОЛЛ-2 + 0.05 * ЛАБ-2 + 0.15 * ЭКЗ-1 + 0.25 * ЭКЗ-2), где ДЗ – оценка за все домашние задания за 1-3 модули, КОЛЛ-1 – оценка за коллоквиум-1, КОЛЛ-2 – оценка за коллоквиум-2, ЛАБ-2 – оценка за лабораторную работу-2, ЭКЗ-1 – оценка за экзамен-1, ЭКЗ-2 – оценка за экзамен-2.
В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, между 6 и 8 округление вверх, а между 8 и 10 округление арифметическое. Т.е. 3,92 округляется до 3; 5,48 - до 5; 5,54 - до 6; 7,12 - до 8; 9,4 - до 9.
Контрольные мероприятия
Контрольная работа (05.11, среда)
Условия задач контрольной работы
Программа и правила проведения зимнего коллоквиума 2025 года (29.11, суббота)
Программа и правила проведения зимнего коллоквиума
Результаты
| 251 группа ПМИ | 252 группа ПМИ | 253 группа ПМИ | 254 группа ПМИ | 255 группа ПМИ | 256 группа ПМИ |
|---|
Программа курса
Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.
Лекция 1. Метод математической индукции. Примеры задач: существование 2-раскраски областей на плоскости, неравенство Бернулли. Усиление утверждения. Ошибки в рассуждениях по индукции. Принцип полной индукции: задача о разбиении выпуклого многоугольника на треугольники непересекающимися диагоналями. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа.
Литература: [1, лекция 1]
Онлайн лекция 1. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.
Литература: [1, лекция 2, §5.6]
Лекция 2. Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами. Доказательство теоретико-множественных тождеств: по определению и через таблицу истинности (разбор случаев). Упорядоченная пара, декартово произведение множеств. Определение функции, ее области определения и области значений, образа и полного прообраза множества. Инъекции, сюръекции, биекции.
Литература: [1, §5.1-5.2, §6.3-6.4]
Лекция 3. Композиция функций. Теорема об ассоциативности композиции всюду определенных функций. Обратная функция, критерий биективности функции. Утверждение о композиции биекций. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности, количество булевых функций от n переменных. Простейшие тождества алгебры логики. Доказательство теоретико-множественных тождеств с помощью алгебры логики. Дизъюнктивная нормальная форма, теорема о существовании ДНФ для любой булевой функции. Совершенная дизъюнктивная нормальная форма (СДНФ).
Литература: [1, §6.4-6.5, §5.3-5.5]
Лекция 4. Напоминание про ДНФ. Конъюнктивная нормальная форма (КНФ). Многочлены Жегалкина. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Суперпозиция булевых функций, замыкание класса булевых функций, свойства замыкания. Полные системы связок, достаточное условие полноты системы. Полнота системы связок «конъюнкция, дизъюнкция, отрицание» и «конъюнкция, отрицание». Полнота системы связок «XOR, конъюнкция, 1». Класс линейных функций, его замкнутость.
Литература: [1, §5.4-5.5]
Лекция 5. Замкнутые классы булевых функций. Лемма о нелинейной функции. Двойственная функция, принцип двойственности. Класс самодвойственных функций, его замкнутость, лемма о несамодвойственной функции. Классы функций, сохраняющих константу, их замкнутость, леммы о функциях, не сохраняющих константу. Класс монотонных функций, его замкнутость, лемма о немонотонной функции. Критерий Поста полноты системы булевых функций.
Литература: [3, глава 1, §5-6]
Лекция 6. Предполные классы булевы функций, описание предполных классов. Формула включений-исключений: доказательство через индикаторные функции подмножеств. Равномощные множества, примеры. Счетные множества, счётность целых и рациональных чисел. Подмножества счетного множества. Счётность объединения и декартова произведения двух счетных множеств. Существование счетного подмножества у любого бесконечного множества. Лемма о не более чем счетном объединении не более чем счетных множеств. Теорема о том, что добавление счетного множества к бесконечному не меняет его мощности.
Литература: [3, глава 1, §6], [1, §5.6, §8.1-8.2], [2, §1.2-1.4]
Лекция 7. Несчетность множества бесконечных последовательностей из нулей и единиц. Равномощность множеств: бесконечных последовательностей из 0 и 1; вещественных чисел; [0, 1]; [0, 1); (0, 1); множества всех подмножеств натуральных чисел. Мощность континуум. Равномощность отрезка и квадрата. Сравнение мощностей, его свойства. Пример: счетная мощность меньше континуальной. Теорема Кантора о сравнении мощности множества и мощности множества всех его подмножеств. Существование счетного количество попарно неравномощных бесконечных множеств. Теорема Кантора-Бернштейна.
Литература: [1, §8.3-8.5], [2, §1.5-1.6]
Онлайн лекция 2. Графы, основные понятия (степень вершины, путь, цикл, простой путь, простой цикл). Лемма о рукопожатиях. Связность графа, компоненты связности. Неравенство, связывающее число вершин, ребер и компонент связности в графе. Деревья. Теорема об эквивалентных определениях дерева. Полное двоичное дерево. Остовное дерево в графе.
Лекция 8. Бинарные отношения, теорема об ассоциативности композиции отношений. Отношение эквивалентности, теорема о разбиении множества с отношением эквивалентности на классы, состоящие из попарно эквивалентных элементов. Ориентированные графы: основные понятия. Лемма о числе ребер в ориентированном графе. Сильная связность орграфа, компоненты сильной связности. Ациклические орграфы, топологическая сортировка.
Литература: [1, §3.3]
Лекция 9. Эйлеровы циклы в ориентированных и неориентированных графах. Критерий существования эйлерова цикла. Двудольные графы, критерий двудольности графа. Булев куб как граф, его 2-раскрашиваемость. Раскраски графов, хроматическое число графа. Клики и независимые множества в графе. Свойства хроматического числа. Верхняя оценка на хроматическое число через максимальную из степеней вершин графа. Верхняя оценка на хроматическое число через максимальную из степеней вершин связного графа при условии, что не все его степени вершин одинаковы. Теорема Брукса (без доказательства).
Литература: [1, §3.4-3.5]
Лекция 10. Хроматический многочлен, его вычисление для полного графа, его дополнения и дерева. Лемма о связи хроматического многочлена графа, графа с удаленным ребром и стянутым ребром. Теорема Уитни о свойствах хроматического многочлена. Мыцельскиан графа. Пример Зыкова–Мыцельского графа без треугольников со сколь угодно большим хроматическим числом. Паросочетание и вершинное покрытие в графе. Утверждение о связи максимального размера паросочетания и минимального размера вершинного покрытия в произвольном графе. Чередующийся и увеличивающий пути относительно паросочетания. Отсутствие увеличивающего пути относительно максимального паросочетания. Теорема Кёнига (формулировка).
Лекция 11. Чередующийся и увеличивающий пути относительно паросочетания (напоминание). Теорема Кёнига (доказательство). Условие Холла для двудольного графа, теорема Холла. Числа Рамсея. Теорема Рамсея. Верхняя оценка на числа Рамсея.
Литература: [1, §1.11, §3.5.4, §3.6], [8, теорема 2.1.1]
Лекция 12. Частично упорядоченные множества: строгий и нестрогий частичные порядки, примеры, линейный порядок. Утверждение о связи строгого и нестрогого порядков. Операции с частично упорядоченными множествами: покоординатный порядок, лексикографический порядок, сумма порядков. Изоморфизм порядков, примеры. Минимальные (максимальные) и наименьшие (наибольшие) элементы. Замечание о единственности наименьшего элемента, пример частично упорядоченного множества с бесконечным числом минимальных элементов. Отрезки, утверждение о том, что при изоморфизме порядков отрезок переходит в отрезок. Утверждение о том, что натуральные, целые и рациональные числа попарно неизоморфны как линейные порядки. Фундированные множества (определение).
Литература: [1, §9.1-9.4], [2, §2.1-2.2]
Материалы курса
Листок 1. Математическая индукция
Листок 2. Перечислительная комбинаторика
Листок 5. Замкнутые классы булевых функций. Критерий Поста
Листок 8. Отношения и ориентированные графы
Листок 9. Неориентированные графы
Листок 10. Хроматическое число и хроматический многочлен графа
Листок 11. Теоремы Холла, Кёнига и Рамсея
Записи лекций
В этом учебном году регулярных видеозаписей лекций на профессиональную видеокамеру не ведется. Однако, силами web-камеры в аудитории, мы можем записывать лекции самостоятельно (UPD: увы, не все лекции удалось записать). Записанные лекции будут находиться по ссылке (файлы названы датой соответствующей лекции): LINK
Также на курсе есть две предзаписанные онлайн-лекции:
папка LEC 01 - лекция по базовой комбинаторике (просьба посмотреть до 16.09);
папка LEC 02 - лекция по основам теории неориентированных графов (просьба посмотреть до 6.11);
Варианты зимних экзаменов прошлых лет
Литература
- М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 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
