Дискретная математика

Бакалавриат 2023/2024

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Экономика и анализ данных)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет экономических наук

Когда читается: 1-й курс, 1-3 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Валинкин Михаил Валерьевич, Оноприенко Анастасия Александровна, Хузиева Алина Эдуардовна

Язык: русский

Кредиты: 6

Контактные часы: 96

Полная версия программы учебной дисциплины

Аннотация

Дискретная математика — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения других математических дисциплин. Курс знакомит с такими фундаментальными понятиями как множества, алгебра логики, функции и отображения, отношения и графы, понятиями элементарной теории вероятностей. Эти понятия являются фундаментальными в изучении математики и её приложений.

Цель освоения дисциплины

Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями.
Знать основы теории графов.
Знать основы теории множеств, владеть формулами алгебр множеств и логики.
Знать базовые свойства бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка.

Планируемые результаты обучения

Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция.
Ознакомиться с базовыми математическими понятиями.
Выработать математическую культуру (культуру доказательств).
Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями.
Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений.
Знать основы теории графов.

Содержание учебной дисциплины

Способы доказательств, булевы связки, высказывания, тавтологии. Множества, операции, связь с булевыми связками.
Натуральные числа и конечные множества.
Формальное определение функций.
Подсчеты слов и функций.
Монотонные пути.
Мультиномиальные коэффициенты. Сочетания с повторениями.
Формула включений и исключений. Симметрия в подсчетах: примеры.
Сравнение бесконечных множеств. Обратная функция. Счетные множества.
Мощность континуум. Примеры. Доказательство несчетности. Теорема Кантора--Бернштейна.
Бинарные отношения, простые неориентированные графы. Отношения эквивалентности. Связность. Компоненты связности.
Деревья. Остовные деревья. Деревья поиска в глубину.
Клики и независимые. Теорема Рамсея. Нижняя оценка чисел Рамсея.
Раскраски, критерий 2-раскрашиваемости. Раскраски во много цветов. Двудольные графы. Паросочетания.
Теорема Холла. Вершинные покрытия. Теорема Кёнига.
Ориентированные графы. Сильная связность, компоненты сильной связности. Ациклические графы.
Порядки, основные определения и свойства. Изоморфизм порядков.
Теорема Дилуорса. Цепи и антицепи в бесконечных порядках. Фундированные множества, индукция по фундированному множеству.
Элементарная теория вероятностей.
Условные вероятности. Формула полной вероятности, формула Байеса. Парадокс Симпсона.
Случайная величина, математическое ожидание случайной величины. Лемма о среднем (математическое ожидание не больше максимума и не меньше минимума). Неравенство Маркова.
Деление с остатком. Арифметика остатков, вычеты, свойства арифметики остатков. Признаки делимости.
Наибольший общий делитель. Алгоритм Евклида. Линейные диофантовы уравнения. Основная теорема арифметики.
Малая теорема Ферма. Функция Эйлера, теорема Эйлера. Китайская теорема об остатках. Оценки количества простых чисел.
Разрешающие деревья. Основные определения и примеры. Мощностные нижние оценки.

Элементы контроля

Домашнее задание 1
Домашнее задание 2
Коллоквиум 1
Коллоквиум 2
Промежуточный экзамен
Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен (при условии согласования с учебным офисом) по правилам, которые дополнительно сообщаются студентам. Экзамен проводится в письменной форме после второго модуля. Письменный экзамен служит для проверки умения творчески использовать полученные знания при решении новых для студента задач. Задания в промежуточном письменном экзамене возможны по всем темам, которые изучались в первых двух модулях.
Итоговый экзамен
Проводится после третьего модуля. Правила проведения полностью аналогичны правилам промежуточного экзамена, только задачи возможны по всем темам курса.

Промежуточная аттестация

2023/2024 2nd module
0.299 * Домашнее задание 1 + 0.299 * Коллоквиум 1 + 0.402 * Промежуточный экзамен
2023/2024 3rd module
Оценка 3 модуля = 0.2*Оценка 2 модуля + 0.2*Домашнее задание 2 + 0.2*Коллоквиум 2 + 0.4*Итоговый экзамен

Список литературы

Авторы

Кононова Елизавета Дмитриевна
Оноприенко Анастасия Александровна

Программа дисциплины