Delivered at:: Big Data and Information Retrieval School

Course type:: Compulsory course

When:: 1 year, 1, 2 module

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

Аннотация

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

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

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

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

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

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

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

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

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

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

2024/2025 2nd module
0.299 * Домашнее задание + 0.402 * Итоговый экзамен + 0.299 * Коллоквиум

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

Авторы

Оноприенко Анастасия Александровна

Bachelor’s Programme 'Economics and Data Science'

Address

Discrete Mathematics 1

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