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