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

Версия 16:28, 23 ноября 2022

ОБЪЯВЛЕНИЯ

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

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

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

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

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

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

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

Диана Казбекова

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

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

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

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

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

В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 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. Операции со множествами. Парадокс Рассела. Доказательство теоретико-множественных тождеств. Декартово произведение множеств. Бинарные отношения, теорема об ассоциативности композиции отношений. Функции. Инъекции, сюръекции, биекции. Обратная функция, критерий обратимости функции. Утверждение о композиции биекций.

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

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

Лекция 5. Теорема о представлении булевой функции полиномом Жегалкина (существование и единственность). Класс линейных функций, лемма о нелинейной функции. Принцип двойственности, класс самодвойственных функций, лемма о несамодвойственной функции. Классы функций, сохраняющих константу. Класс монотонных функций, лемма о немонотонной функции. Критерий Поста полноты системы булевых функций.

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

Лекция 7. Равномощность множеств: бесконечных последовательностей из 0 и 1; вещественных чисел; [0, 1]; [0, 1); множества всех подмножеств натуральных чисел. Мощность континуум. Несчетность множества бесконечных последовательностей из 0 и 1. Сравнение мощностей, теорема Кантора. Теорема Кантора-Бернштейна.

Лекция 8. Равномерность отрезка и квадрата. Частично упорядоченные множества: строгий и нестрогий частичные порядки, их связь, линейный порядок. Операции с частично упорядоченными множествами: сумма порядков, покоординатный порядок, лексикографический порядок. Изоморфизм порядков, примеры. Минимальные (максимальные) и наименьшие (наибольшие) элементы, отрезки. Фундированные множества, принцип индукции.

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

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

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

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

Листок 1

Листок 2

Листок 3

Листок 4

Листок 5

Листок 6

Листок 7

Листок 8

Листок 9

Листок 10

Листок 11

Литература

1. М.Вялый, В.Подольский, А.Рубцов, Д.Шварц, А.Шень. Лекции по дискретной математике. Изд. Дом ВШЭ, 2021. 495 с. Черновик этого учебника. В данной книге излагается почти всё, что будет в курсе (за исключением задач - те меняются чаще, чем пишутся книги). Как нетрудно догадаться, мы рекомендуем читать эту книгу (окончательный вариант есть на бумаге - издан издательством ВШЭ).
2. Верещагин Н.К., Шень А. - Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Московский центр непрерывного математического образования - 2008 - ISBN: 978-5-94057-321-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9306
3. 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
4. Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/851215