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

Текущая версия на 20:37, 9 августа 2023

ОБЪЯВЛЕНИЯ

Канал, где дублируются важные объявления курса (рекомендуем подписаться): https://t.me/+98kPFGRbB48zYzgy

_______________________________________________________________________________________________

Показ работ итогового экзамена состоится очно 3 апреля, в 18:10, ауд. R408

_______________________________________________________________________________________________

Итоговый экзамен состоится 28 марта в 11:00. Не опаздывайте! Пользоваться можно любыми бумажными материалами, и никакими электронными!

Расписание:

группы 221, 224 и 225-1 - ауд. R201

группы 222, 223 и 225-2 - ауд. R301

_______________________________________________________________________________________________

Второй коллоквиум пройдет 18 марта, 11:00-19:00! Программа, регламент и расписание коллоквиума выложены ниже.

_______________________________________________________________________________________________

Зимний (промежуточный) экзамен состоится 23 декабря, 9:00-11:00!

Очень рекомендую всем выспаться. И обязательно приходите вовремя!

Пользоваться можно любыми бумажными материалами, и никакими электронными!

Расписание:

группы 221, 222 - ауд. R503

группа 223, 225-1 - ауд. R504

группа 224, 225-2 - ауд. R205

Показ работ состоится очно 28 декабря, в 16:00, ауд. R407

_______________________________________________________________________________________________

Первый коллоквиум пройдет 10 декабря, 9:00-18:00! Программа и регламент коллоквиума выложены ниже.

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

Итоговый экзамен (28.03, вторник)

Решения задач итогового экзамена

Результаты итогового экзамена

Программа и правила проведения весеннего коллоквиума 2023 года (18.03, суббота)

Программа и правила проведения весеннего коллоквиума. Важное замечание: в программу коллоквиума вошли не все темы курса. Нужно иметь в виду, что письменный экзамен в конце третьего модуля будет содержать задачи по всем темам курса (в основном, по темам 3 модуля).

По умолчанию предполагается, что коллоквиум для всех студентов пилотного потока будет проводиться в аудитории R201. Для групп, начинающих сдачу коллоквиума в 14:30 и позднее, возможен перенос в другую аудиторию.

Коллоквиум состоится 18 марта с 11:00 до 19:00. Студенты из разных групп (и подгрупп) приглашаются на разное время согласно расписанию. Приходите вовремя: сдавать с другой (под)группой не разрешается!

Группа ПМИ 222: в 11:00.

Группа ПМИ 225: в 12:00.

Группа ПМИ 221: в 14:30.

Подгруппа ПМИ 223-1: в 14:40.

Группа ПМИ 224: в 15:30.

Подгруппа ПМИ 223-2: в 16:00.

Промежуточный экзамен (23.12, пятница)

Решения задач промежуточного экзамена

Результаты промежуточного экзамена

Программа и правила проведения зимнего коллоквиума 2022 года (10.12, суббота)

Программа и правила проведения зимнего коллоквиума.

По умолчанию предполагается, что коллоквиум для всех студентов пилотного потока будет проводиться в аудитории R401. Для групп, начинающих сдачу коллоквиума в 14:40 и позднее, возможен перенос в другую аудиторию.

Коллоквиум состоится 10 декабря с 9:00 до 18:00. Студенты из разных групп (и подгрупп) приглашаются на разное время согласно расписанию. Приходите вовремя: сдавать с другой (под)группой не разрешается!

Группы 221ПМИ, 225ПМИ: в 9:00.

Подгруппа 224-1ПМИ: в 11:15.

Подгруппа 224-2ПМИ: в 12:00.

Группа 223ПМИ: в 14:40.

Подгруппа 222-1ПМИ в 15:40.

Подгруппа 222-2ПМИ: в 16:20.

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

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

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

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

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

Дарья Чубарова

Иван Скворцов

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

Вес коллоквиумов в итоговой оценке 30%, промежуточного экзамена 15%, итогового 30%, домашних заданий 25%.

Промежуточная оценка выставляется по фактически проведенным в 1-2 модулях контрольным мероприятиям с весами: коллоквиум 30%, промежуточный экзамен 40%, домашние задания 30%. В промежуточной оценке учитываются те домашние задания, которые будут проверены в первом семестре.

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

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

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, между 6 и 8 округление вверх, а между 8 и 10 округление арифметическое. Т.е. 3,92 округляется до 3; 5,48 - до 5; 5,54 - до 6; 7,12 - до 8; 9,4 - до 9.

Результаты

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

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

Лекция 1. Метод математической индукции. Примеры задач. Усиление утверждения. Принцип полной индукции. Эквивалентность принципа математической индукции, принципа полной индукции и принципа наименьшего числа.

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

Лекция 2. Операции со множествами. Парадокс Рассела. Доказательство теоретико-множественных тождеств. Декартово произведение множеств. Бинарные отношения, теорема об ассоциативности композиции отношений. Функции. Инъекции, сюръекции, биекции. Обратная функция, критерий обратимости функции. Утверждение о композиции биекций.

Литература: [1, §5.1-5.2, лекция 6, лекция 7]

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

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

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

Литература: [1, §2.9, §5.3-5.5], [3, глава 1, §1-4]

Лекция 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, лекция 9], [2, §2.1-2.4]

Лекция 9. Изоморфизм конечных линейных порядков одинаковой мощности. Теорема о том, что счетный линейный порядок изоморфен подмножеству рациональных чисел. Цепи и антицепи в частично упорядоченных множествах. Теорема о том, что размер максимальной цепи равен минимальному числу антицепей, образующих разбиение множества. Теорема Дилуорса.

Литература: [1, §9.5, §9.7], [2, §2.2]

Лекция 10. LYM-лемма, теорема Шпернера о размере максимальной антицепи в булевом кубе. Графы, основные понятия (степень вершины, путь, цикл, простой путь, простой цикл). Лемма о рукопожатиях. Связность графа, компоненты связности. Неравенство, связывающее число вершин, ребер и компонент связности в графе. Деревья.

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

Лекция 11. Теорема об эквивалентных определениях дерева. Полное двоичное дерево. Остовное дерево в графе. Ориентированные графы: основные понятия. Лемма о числе ребер в ориентированном графе. Сильная связность орграфа, компоненты сильной связности. Ациклические орграфы, топологическая сортировка. Эйлеровы циклы в ориентированных и неориентированных графах. Критерий существования эйлерова цикла. Двудольные графы, критерий двудольности графа.

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

Лекция 12. Булев куб как граф, его 2-раскрашиваемость. Клики и независимые множества. Теорема Рамсея. Верхняя оценка на числа Рамсея. Паросочетания в графе. Теорема Холла. Вершинные покрытия. Утверждение о связи максимального размера паросочетания и минимального размера вершинного покрытия в произвольном графе. Теорема Кёнига (формулировка). Чередующийся и увеличивающий пути относительно паросочетания. Отсутствие увеличивающего пути относительно максимального паросочетания.

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

Лекция 13. Теорема Кёнига (доказательство). Вероятностное пространство, вероятностное распределение, примеры. Свойства вероятности. Оценка объединения. Вероятностный метод: нижняя оценка для чисел Рамсея. Формула включений-исключений для вероятностей.

Литература: [1, §10.1-10.3]

Лекция 14. Задача о беспорядках. Условная вероятность, примеры ее подсчета. Теорема умножения, формулы Байеса и полной вероятности. Пример с тестом на выявление болезни. Равномерное распределение на ребрах регулярного графа: два подхода. Независимые события. Независимость событий в совокупности, отличие от попарной независимости событий.

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

Лекция 15. Раскраски графов, хроматическое число графа, его свойства. Верхняя оценка на хроматическое число через максимальную из степеней вершин графа. Теорема Брукса (без доказательства). Мыцельскиан графа. Пример Зыкова–Мыцельского графа без треугольников со сколь угодно большим хроматическим числом. Хроматический многочлен, его свойства.

Лекция 16. Теорема Уитни о свойствах хроматического многочлена. Случайная величина, математическое ожидание, линейность матожидания. Задача о днях рождения. Нервенство Маркова, пример применения. Дисперсия. Неравенство Чебышёва. Общая формулировка вероятностного метода, пример применения для поиска разреза в графе величины не менее половины числа ребер.

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

Лекция 17. Пример применения вероятностного метода для поиска разреза графа величины более половины числа ребер. Независимые случайные величины. Математическое ожидание и дисперсия независимых случайных величин. Вероятность выпадения ровно половины орлов при бросании честной монеты. Оценки для биномиальных коэффициентов. Неравенство Чернова.

Литература: [1, §10.5-10.7]

Лекция 18. Производящие функции, определение. Их сложение и умножение на скаляр. Произведение производящих функций, основные свойства арифметических операций. Обратимые производящие функции, примеры. Формальное дифференцирование производящих функций, свойства производной, правило Лейбница. Подстановка нуля в производящую функцию, вычисление n-го коффициента производящей функции с использованием производных. Пример применения производящих функций: вывод формулы для суммы квадратов первых n натуральных чисел. Связь произведения производящих функций с неупорядоченными выборками.

Литература: [6, глава 1]

Лекция 19. Бином Ньютона, обобщение на целые показатели. Пример получения тождеств с помощью производящих функций. Числа Фибоначчи: их производящая функция и вывод явной формулы (формула Бине). Линейные рекурентные соотношения с постоянными коэффициентами. Доказательство того, что производящая функция последовательности, удовлетворяющей линейному рекурентному соотношению с постоянными коэффициентами, рациональна. Явная формула для общего члена последовательности, метод ее вывода. Задача о правильных скобочных последовательностях. Рекуррентная формула для числа правильных скобочных последовательностей. Их производящая функция и ее вывод как решения квадратного уравнения.

Литература: [6, глава 2], [1, §2.9-2.10]

Лекция 20. Числа Каталана (напоминание, рекуррентное соотношение, производящая функция). Вывод явной формулы для чисел Каталана. Явное доказательство того, что получена правильная формула. Комбинаторные игры с полной информацией. Задание игры в виде ориентированного графа. Партии и стратегии. Стратегии, гарантирующие выигрыш. Цена игры. Теорема о цене игры.

Литература: [1, §2.10.4, §2.10.6, §11.1-11.2]

Лекция 21. Беспристрастные игры, N- и P-позиции. Анализ игры с конца, примеры. Игра ним, ее P-позиции. Задача об угадывании числа, ее сложность в адаптивном и неадаптивном случае. Модель разрешающих деревьев. Адаптивный и неадаптивный протоколы, сведение адаптивного протокола к неадаптивному. Задача о взвешиваниях: поиск самой тяжелой монеты. Сложность в адаптивном и неадаптивном случае. Сложность булевой функции. Сложность функции CONN, определяющей связность графа: верхняя оценка и слабая нижняя оценка (≥ n^2 / 4).

Литература: [1, §11.3-11.5, §12.1-12.4]

Лекция 22. Метод противника. Сложность булевой функции CONN, определяющей связность неориентированного графа на n вершинах. Булевы схемы, определение. Задание схемы в виде ациклического ориентированного графа. Схемы-графы для функции XOR и функции голосования. Схема линейного размера для сложения двоичных чисел. Вычисление произвольной булевой функции от n переменных схемой размера O(n 2^n). Существование функций с экспоненциальной схемной сложностью.

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

Лекция 23. Верхняя и нижняя оценки для схемной сложности функции XOR. Глубина булевой схемы. Построение схемы для функции CONN, определяющей связность неориентированного графа на n вершинах (два варианта для размера и глубины). Возведение булевой матрицы в степень, связь с числом путей в графе. Формулы как частный случай схем. Существование формулы, эквивалентной данной булевой схеме, той же глубины и экспоненциального размера. Задачи выполнимости булевой схемы, КНФ и 3-КНФ.

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

Лекция 24. Эффективное сведение задачи выполнимости булевой схемы к задаче выполнимости 3-КНФ. Лемма о существовании балансирующей вершины в булевой формуле. Теорема о балансировке булевых формул. Коды с исправлением ошибок. Возникновение и исправление ошибок в коде, примеры. Расстояние Хэмминга. Код, исправляющий e ошибок и связь с непересекающимися шарами.

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

Лекция 25. Параметры кода. Код, исправляющий e ошибок. Связь кодового расстояния с числом исправляемых кодом ошибок. Число точек в шаре радиуса r. Граница Хэмминга (необходимое условие существования кода). Граница Гилберта (достаточное условие существования кода). Граница Синглтона. МДР-коды: код Рида-Соломона над вычетами по простому модулю. Линейные коды, утверждение о расстоянии линейного кода. Порождающая матрица кода, кодирование с помощью порождающей матрицы. Проверочная матрица кода. Связь столбцов проверочной матрицы с кодовым расстоянием. Двоичный код Хэмминга как совершенный код, исправляющий одну ошибку.

Литература: [7, §1-2, §4, §6-8]

Лекция 26. Двоичный код Хэмминга как совершенный код, исправляющий одну ошибку. Эффективное исправление ошибки в коде Хэмиинга. Матрица Адамара. Утверждение о том, что порядок матрицы Адамара равен 2 или делится на 4. Построение матрицы Адамара порядка степени двойки. Связь матриц Адамара и кодов длины n с расстоянием n/2. Код Адамара. Построение матрицы Адамара порядка p+1, где p - простое число, дающее остаток 3 при делении на 4.

Литература: [7, §6, §15, §17]

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

Листок 1

Листок 2

Листок 3

Листок 4

Листок 5

Листок 6

Листок 7

Листок 8

Листок 9

Листок 10

Листок 11

Листок 12

Листок 13

Листок 14

На 15-м семинаре разбирались экзаменационные варианты прошлых лет. Домашнее задание не задавалось.

Листок 16

Листок 17

Листок 18

Листок 19

Листок 20

Листок 21

Листок 22

Листок 23

Листок 24

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

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

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

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

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

Экзамен весна 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