Дискретная математика на ПМИ 2024/25 (пилотный поток) — различия между версиями

Текущая версия на 21:28, 12 ноября 2024

ОБЪЯВЛЕНИЯ

Канал, где дублируются важные объявления курса (рекомендуем подписаться): LINK

______________________________________________________________________

9 ноября, 11:00-13:00, состоится контрольная работа по материалам лекций и семинаров 1 модуля. В контрольной будет 5 задач на следующие темы:

- Индукция

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

- Множества и функции

- Булевы функции: ДНФ, многочлены Жегалкина

- Замкнутые классы булевых функций, критерий Поста

- Мощности множеств, счетные и континуальные множества, сравнение мощностей

Пользоваться материалами (ни бумажными, ни электронными) нельзя. Допускается использование лишь стандартного калькулятора (хотя едва ли он пригодится).

Длительность работы: 90 минут

Распределение групп по аудиториям:

R401 - группы 241, 242 и 244,

R404 - группы 243, 245 и 246.

Пожалуйста, не опаздывайте: не позднее 11:10 мы раздадим всем условия задач и начнем отсчет времени (длительность работы – 90 минут).

Вариант контрольной прошлого года LINK

Контрольные мероприятия

Контрольная работа 09.11

Условия задач контрольной работы

Общая информация о курсе Дискретная математика, пилотный поток, 1 курс

Преподаватели и ассистенты

Лекции: Артём Максимович Максаев

Ассистент лектора: Артём Парфенов

Распределение по группам

Остальные ассистенты (проверяют домашние задания в разных группах):

Арсений Лазо

Никита Солоницын

Вячеслав Шестаков

Данила Солунов

Ассистент, ответственный за лабораторные работы:

Роман Гундарин

Правила оценивания

Домашние задания выдаются еженедельно и сдаются перед следующим семинаром. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Оценка становится окончательной после защиты домашнего задания. Трижды за весь курс (1-3 модули) домашнее задание разрешается сдать на неделю позже срока без потери баллов.

Экзамен — это письменная работа. Пересдача проводится по правилам экзамена. Комиссия проводится в устном формате без учета накопленной оценки.

Оценка за курс в сессию после 2 модуля считается по формуле:

Промежуточная оценка = Округление(0.25 * ДЗ + 0.15 * КР + 0.25 * КОЛЛ-1 + 0.05 * ЛАБ-1 + 0.3 * ЭКЗ-1), где ДЗ – оценка за первые 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.

Результаты

Программа курса

Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.

Лекция 1. Метод математической индукции. Примеры задач: существование 2-раскраски областей на плоскости, неравенство Бернулли. Усиление утверждения. Ошибки в рассуждениях по индукции. Принцип полной индукции: задача о разбиении выпуклого многоугольника на треугольники непересекающимися диагоналями. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (начало).

Литература: [1, лекция 1]

Онлайн лекция 1. Правило суммы, задача о числе путей. Правило произведения, конечные слова в алфавите. Упорядоченный выбор k элементов из n (с повторениями или без повторений). Числа сочетаний: явная и рекуррентная формула. Треугольник Паскаля. Бином Ньютона. Сумма и знакочередующаяся сумма биномиальных коэффициентов. Полиномиальные коэффициенты. Сочетания с повторениями. Число элементов в объединении двух множеств. Формула включений-исключений.

Литература: [1, лекция 2, §5.6]

Лекция 2. Доказательство эквивалентности принципа математической индукции, принципа полной индукции и принципа наименьшего числа (завершение). Множества и их элементы, примеры множеств. Парадокс Рассела. Операции со множествами. Доказательство теоретико-множественных тождеств: по определению и через таблицу истинности (разбор случаев). Упорядоченная пара, декартово произведение множеств. Определение функции.

Литература: [1, §5.1-5.2, §6.3]

Лекция 3. Определение функции, ее области определения и области значений, образа и полного прообраза множества. Композиция функций. Теорема об ассоциативности композиции всюду определенных функций. Инъекции, сюръекции, биекции. Обратная функция, критерий биективности функции. Утверждение о композиции биекций. Булевы функции, основные логические связки. Задание булевых функций таблицами истинности, количество булевых функций от n переменных. Простейшие тождества алгебры логики.

Литература: [1, §6.4-6.5, §5.3-5.4]

Лекция 4. Доказательство теоретико-множественных тождеств с помощью алгебры логики. Дизъюнктивная нормальная форма, теорема о существовании ДНФ для любой булевой функции. Совершенная дизъюнктивная нормальная форма (СДНФ). Конъюнктивная нормальная форма (КНФ). Полиномы Жегалкина. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Суперпозиция булевых функций, замыкание класса булевых функций, свойства замыкания. Полные системы связок. Полнота системы связок «конъюнкция, дизъюнкция, отрицание» и «конъюнкция, отрицание». Полнота системы связок «XOR, конъюнкция, 1».

Литература: [1, §6.5, §5.3-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]

Лекция 8. Бинарные отношения, теорема об ассоциативности композиции отношений. Отношение эквивалентности, теорема о разбиении множества с отношением эквивалентности на классы, состоящие из попарно эквивалентных элементов. Ориентированные графы: основные понятия. Лемма о числе ребер в ориентированном графе. Сильная связность орграфа, компоненты сильной связности. Ациклические орграфы, топологическая сортировка.

Литература: [1, §3.3]

Онлайн лекция 2. Графы, основные понятия (степень вершины, путь, цикл, простой путь, простой цикл). Лемма о рукопожатиях. Связность графа, компоненты связности. Неравенство, связывающее число вершин, ребер и компонент связности в графе. Деревья. Теорема об эквивалентных определениях дерева. Полное двоичное дерево. Остовное дерево в графе.

Литература: [1, §3.1-3.2]

Лекция 9. Критерий ацикличности графа. Эйлеровы циклы в ориентированных и неориентированных графах. Критерий существования эйлерова цикла. Двудольные графы, критерий двудольности графа. Булев куб как граф, его 2-раскрашиваемость. Раскраски графов, хроматическое число графа. Клики и независимые множества в графе. Свойства хроматического числа.

Литература: [1, §3.4-3.5]

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

Листок 1. Математическая индукция

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

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

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

Листок 5. Замкнутые классы булевых функций. Критерий Поста

Листок 6. Мощность множеств-1

Листок 7. Мощность множеств-2

Листок 8. Отношения и ориентированные графы

Листок 9. Неориентированные графы

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

Видеозаписи регулярных лекций появляются здесь (файлы названы датой лекции): https://disk.yandex.ru/d/e3j_hRnQOsdtqA

_________________________________

Две записанные онлайн-лекции расположены по ссылке: https://disk.yandex.ru/d/GqWnpqpGinYVSg

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

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

Варианты зимних экзаменов прошлых лет

Экзамен зима 2022

Экзамен зима 2021

Экзамен зима 2020

Литература

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 http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
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