Дискретная математика на ПМИ 2022/23 (пилотный поток)
Содержание
ОБЪЯВЛЕНИЯ
Канал, где дублируются важные объявления курса (рекомендуем подписаться): https://t.me/+98kPFGRbB48zYzgy
_______________________________________________________________________________________________
Второй коллоквиум пройдет 18 марта, 11:00-19:00! Программа, регламент и расписание коллоквиума будут выложены ниже.
Итоговый экзамен состоится 28 марта в 11: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! Программа и регламент коллоквиума выложены ниже.
Контрольные мероприятия
Программа и правила проведения зимнего коллоквиума 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.
Промежуточный экзамен (23.12, пятница)
Решения задач промежуточного экзамена
Результаты промежуточного экзамена
Общая информация о курсе Дискретная математика, пилотный поток, 1 курс
Преподаватели и ассистенты
Лекции: Артём Максимович Максаев
Распределение по группам
| Группа | Преподаватель | Консультационные часы преподавателя | Учебный ассистент, отвечающий за группу |
|---|---|---|---|
| 221 | Артём Максимович Максаев | пн 13:00-18:00 (по предварительной договоренности), T909 | Артём Мацкевич |
| 222 | Любовь Николаевна Сысоева | пн 13:30-14:30, вт 17:40-18:40 (по предварительной договоренности) | Игорь Паншин |
| 223 | Любовь Николаевна Сысоева | пн 13:30-14:30, вт 17:40-18:40 (по предварительной договоренности) | Диана Казбекова |
| 224 | Валентин Валерьевич Промыслов | вт 14:30-18:00, пт 9:00-14:00 (по предварительной договоренности), T909 | Анна Оверчук |
| 225 | Никита Сергеевич Лукьяненко | вт 19:50-21:10 (по предварительной договоренности) | Леонид Черепанов |
Остальные ассистенты (проверяют домашние задания в разных группах):
Дарья Чубарова
Иван Скворцов
Правила оценивания
Вес коллоквиумов в итоговой оценке 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.
Результаты
| 221 группа | 222 группа | 223 группа | 224 группа | 225 группа |
|---|
Программа курса
Далее приводится содержание лекций с указанием литературного источника. Отметим, что литературный источник не заменяет лекции и лишь приблизительно ей соответствует: материал в нем может быть изложен иначе, быть неполным или, наоборот, чрезмерным для нашего курса.
Лекция 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. Пример применения вероятностного метода для поиска разреза графа величины более половины числа ребер. Независимые случайные величины. Математическое ожидание и дисперсия независимых случайных величин. Вероятность выпадения ровно половины орлов при бросании честной монеты. Оценки для биномиальных коэффициентов. Неравенство Чернова.
Лекция 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]
Материалы курса
На 15-м семинаре разбирались экзаменационные варианты прошлых лет. Домашнее задание не задавалось.
Варианты зимних экзаменов прошлых лет
Литература
- М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 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 http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
- Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: https://znanium.com/catalog/document?id=343807
- Ландо С. К. Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144 с.
