Бакалавриат
2020/2021
Дискретная математика
Статус:
Курс обязательный (Совместный бакалавриат НИУ ВШЭ и ЦПМ)
Направление:
01.03.01. Математика
Кто читает:
Факультет математики
Где читается:
Факультет математики
Когда читается:
1-й курс, 1 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Артамкин Игорь Вадимович,
Басалаев Алексей Андреевич,
Бурман Юрий Михайлович,
Буряк Александр Юрьевич,
Дунин-Барковский Петр Игоревич,
Колмаков Евгений Александрович,
Семенов Павел Владимирович,
Шамканов Данияр Салкарбекович
Язык:
русский
Кредиты:
4
Контактные часы:
50
Программа дисциплины
Аннотация
В дисциплине «Введение в дискретную математику» излагаются базовые понятия и приёмы рассуждений, необходимые в большинстве дальнейших математических курсов, и описываются методы работы с различными комбинаторными объектами (т.е. объектами, нумерующимися элементами конечных множетств). К числу таких методов относятся методы перечислительной комбинаторики, теории производящих функций, теории графов и др.
Цель освоения дисциплины
- Целью изучения дисциплины «Введение в дискретную математику» в первом модуле первого курса является знакомство студентов с базовыми понятиями и приёмами рассуждений, необходимыми в большинстве дальнейших математических курсов.
- Цель изучения второй части дисциплины, читаемой в четвертом модуле первого курса, состоит в том, чтобы научить студентов работать с различными комбинаторными объектами, узнавать эти комбинаторные объекты в задачах из других областей математики и применять к ним методы дискретной математики. К числу таких методов относятся методы перечислительной комбинаторики, теории производящих функций, теории графов и др.
Планируемые результаты обучения
- Студенты должны овладеть методом математической индукции и научиться применять его в различных алгебраических и комбинаторных задачах
- Студенты должны научиться распознавать известные им комбинаторные конструкции (перестановки, размещения, сочетания) в предлагаемым им комбинаторных и простейших вероятностных задачах и применять комбинаторные методы к решению таких задач.
- Студенты должны освоить основные понятия теории графов: изоморфизм и гомотопическая эквивалентность графов, критерий планарности и др., и овладеть навыками применения методов теории графов в комбинаторных задачах.
- Студенты должны изучить основные логические операции, принципы работы с кванторами, а также основные понятия теории множеств.
- Студенты должны овладеть понятием отношения на множестве, в частности, освоить понятия отношения эквивалентности, разбиения на классы эквивалентности, фактормножества, а также частично упорядоченного множества, и научиться применять эти конструкции к решению задач из различных областей математики.
- Студенты должны овладеть понятиями мощности множеств, равномощных множеств, научиться доказывать счётность или несчётность различных множеств (в частности, Z, Q, R, C...).
- Студенты должны познакомиться с аксиомой выбора (в различных формулировках) и эквивалентными ей утверждениями: теоремой Цермело и леммой Цорна, и научиться применять её в различных задачах теории множеств.
- Студенты должны повторить изложенный в 1-м модуле материал, относящийся к элементарной перечислительной комбинаторике и научиться применять его к решению комбинаторных задач. В частности, они должны освоить комбинаторные методы доказательства различных тождеств с биномиальными коэффициентами.
- Студенты должны познакомиться с понятием q-биномиального коэффициента и научиться доказываь q-аналоги различных комбинаторных тождеств, а также выписывать производящую функцию Эйлера для числа разбиений и обратный к ней ряд, задаваемый пентагональной теоремой Эйлера.
- Студенты должны освоить принципы работы с формальными степенными рядами и научиться выписывать общее и частное решение линейного рекуррентного уравнения с постоянными коэффициентами (в частности, в случае кратных корней характеристического уравнения).
- Студенты должны научиться работать с числами Каталана, Шрёдера и Моцкина, в частности, выписывать их производящие функции и строить биекции между множествами, дающими их различные комбинаторные интерпретации (в случае чисел Каталана — пути Дика, бинарные деревья, разбиения треугольника и т.д.)
Содержание учебной дисциплины
- Метод математической индукцииПрименение метода математической индукции к доказательству тождеств и другим задачам
- Элементы комбинаторикиПерестановки, размещения, сочетания
- Простейшие понятия логикиЯзык теории множеств
- ОтношенияОтношения эквивалентности и порядка
- Вполне упорядоченные множестваАксиома выбора, теорема Цермело, лемма Цорна.
- Мощности множествСчетные и несчетные множества. Теорема Кантора-Бернштейна, континуум-гипотеза.
- Перечисление комбинаторных объектовБиномиальные и мультиномиальные коэффициенты. Формула включений-исключений.
- Простейшие производящие функцииВычисления с формальными степенными рядами. Линейные рекурренты и рациональные производящие функции.
- Нелинейные рекуррентыЧисла Каталана, Шрёдера и Моцкина, их производящие функции
- Разбиенияq-биномиальные коэффициенты. Производящая функция Эйлера, пентагональная теорема
- ГрафыИзоморфизм графов. Планарные графы, теорема Эйлера. Критерии планарности, теорема Куратовского. Перечислительные задачи теории графов. Теорема Кэли.
Промежуточная аттестация
- Промежуточная аттестация (1 модуль)Оценка за первый модуль совпадает с накопленной, которая равна среднему арифметическому (со стандартным правилом округления) оценок за шесть листков, но не выше 7 для студентов, не сдавших на положительную оценку последний листок. Формула оценки за каждый листок указана в самом листке; если студент не приступал к сдаче листка, он учитывается с весом -3, за исключением последнего, который в этом случае учитывается с весом 0.
