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

Бакалавриат 2026/2027

ID 1179842

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

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

Где читается: Факультет компьютерных наук

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

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

Преподаватели: Александров Кирилл Игоревич, Валинкин Михаил Валерьевич, Корнеев Сергей Александрович, Оноприенко Анастасия Александровна, Пономарчук Анна Сергеевна, Черебедов Марк Вадимович

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

Кредиты: 4

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

Дополнительные материалы в LMS Задать вопрос

Аннотация

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

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

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

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

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

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

Способы доказательств, булевы связки, высказывания, тавтологии. Множества, операции, связь с булевыми связками.
Методы математических доказательств: метод перебора, доказательство от противного.
Натуральные числа и конечные множества.
Формальное определение функций.
Подсчеты слов и функций.
Монотонные пути.
Мультиномиальные коэффициенты. Сочетания с повторениями.
Формула включений и исключений. Симметрия в подсчетах: примеры.
Бинарные отношения, простые неориентированные графы. Отношения эквивалентности. Связность. Компоненты связности.
Отношения эквивалентности. Графы: ключевые определения.
Связность и сильная связность. Эйлеровы графы.
Деревья. Остовные деревья в графе.
Остовные деревья специального вида
Планарные графы

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

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

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

2026/2027 2nd module
0.4 * Итоговый экзамен + 0.275 * Коллоквиум + 0.175 * Контрольная работа + 0.05 * Самостоятельные работы + 0.1 * Домашнее задание

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

Авторы

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

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