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

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

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

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

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

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

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

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

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

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

Преподаватели: Валинкин Михаил Валерьевич, Вялый Михаил Николаевич, Лукьяненко Никита Сергеевич, Хузиева Алина Эдуардовна

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

Кредиты: 7

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

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

Аннотация

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

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

Знакомство с базовыми математическими понятиями.
Развитие математической культуры (культуры доказательств).
Изучение фундаментальных разделов, относящихся к дискретной математике, необходимых для успешного прохождения последующих курсов.

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

Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция.
Выработать базовую математическую культуру (культуру доказательств)
Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями
Знать основы теории графов
Знать основы теории множеств, владеть формулами алгебр множеств и логики
Изучить доказательство нижних оценок для алгоритмов поиска максимума в массиве и сортировки.
Освоение ключевых тем основных разделов комбинаторики.
Умение оперировать терминами и понятиями, освоение подходов к построению определений (могут быть разными в зависимости от источника) комбинаторики.
Умение ориентироваться в научных источниках с целью нахождения наиболее близкой литературы для решения возникающих задач из комбинаторики.
Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений
Уметь строить разложения в ДНФ и КНФ, проверять на полноту базис.
Знание базовых свойств бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка
Уметь различать счётные множества и множества мощности континуум. Овладеть диагональным методом на примере теоремы Кантора.

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

Множества и логика
Комбинаторика
Алгебра логики
Математические определения, утверждения и доказательства
Графы
Основы теории чисел
Двудольные графы, паросочетания и функции
Ориентированные графы и отношения порядка.
Бинарные отношения. Отношения эквивалентности.
Булевы функции
Вероятность
Мощность множеств
Разрешающие деревья и нижние оценки

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

Домашнее задание 1
Средняя оценка за домашние задания за первый и второй модуль. Предварительная оценка за домашнее задание задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Для проверки остаточных знаний по темам домашних заданий используются два способа. По части домашних заданий проводится выборочная защита (устная беседа) по решенным (хотя бы частично) задачам. В случае если студент не может ответить на ключевые вопросы по решению задачи или сформулировать используемые при решении задач теоремы и определения, преподаватель уменьшает предварительную оценку за домашнее задание на 50%. При неудаче ответа по двум задачам оценка за домашнее задание обнуляется. Второй способ проверки остаточных знаний для части домашних заданий: самостоятельная работа на семинаре (длительность — 20-30 минут, задание из двух задач, аналогичных задачам из домашнего задания). Окончательная оценка за такое домашнее задание получается умножением предварительной оценки на долю решенных на самостоятельной работе задач. Выбор способа проверки остаточных знаний оставляется на усмотрение преподавателей и происходит после того, как домашнее задание сдано и проверено.
Домашнее задание 2
Средняя оценка за домашние задания за первый, второй и третий модуль. Предварительная оценка за домашнее задание пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Для проверки остаточных знаний по темам домашних заданий используются два способа. По части домашних заданий проводится выборочная защита (устная беседа) по решенным (хотя бы частично) задачам. В случае если студент не может ответить на ключевые вопросы по решению задачи или сформулировать используемые при решении задач теоремы и определения, преподаватель уменьшает предварительную оценку за домашнее задание на 50%. При неудаче ответа по двум задачам оценка за домашнее задание обнуляется. Второй способ проверки остаточных знаний для части домашних заданий: самостоятельная работа на семинаре (длительность — 20-30 минут, задание из двух задач, аналогичных задачам из домашнего задания). Окончательная оценка за такое домашнее задание получается умножением предварительной оценки на долю решенных на самостоятельной работе задач. Выбор способа проверки остаточных знаний оставляется на усмотрение преподавателей и происходит после того, как домашнее задание сдано и проверено.
Коллоквиум 1
Проводится в конце второго модуля. Программа коллоквиума объявляется заранее и зависит от пройденного к моменту коллоквиума материала. Для каждого вопроса указано, сколько баллов получает студент при полностью корректном ответе. Итоговая оценка за работу вычисляется как сумма набранных баллов. За ответ может выставляться частичное количество баллов в соответствии с долей правильно изложенного материала. Правило округления выбирается преподавателем индивидуально для каждого студента.
Промежуточный экзамен
Проводится в письменной форме после второго модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам. Задания в промежуточном письменном экзамене возможны по всем темам, которые изучались в первых двух модулях. Каждое задание в работе оценивается по отдельности, итоговая оценка за работу вычисляется по сумме набранных баллов. Правило определения оценки объявляется после проверки работ. За решения могут выставляться частичные баллы, критерии объявляются после проверки работ.
Коллоквиум 2
Проводится в конце третьего модуля. Программа коллоквиума объявляется заранее и зависит от пройденного к моменту коллоквиума материала. Для каждого вопроса указано, сколько баллов получает студент при полностью корректном ответе. Итоговая оценка за работу вычисляется как сумма набранных баллов. За ответ может выставляться частичное количество баллов в соответствии с долей правильно изложенного материала. Правило округления выбирается преподавателем индивидуально для каждого студента.
Итоговый экзамен
Проводится в письменной форме после третьего модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам. Задания в итоговом письменном экзамене возможны по всем темам, которые изучались в курсе. Каждое задание в работе оценивается по отдельности, итоговая оценка за работу вычисляется по сумме набранных баллов. Правило определения оценки объявляется после проверки работ. За решения могут выставляться частичные баллы, критерии объявляются после проверки работ.

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

2022/2023 учебный год 2 модуль
0.401 * Промежуточный экзамен + 0.3 * Коллоквиум 1 + 0.299 * Домашнее задание 1
2022/2023 учебный год 3 модуль
0.15 * Коллоквиум 2 + 0.15 * Коллоквиум 1 + 0.2 * Домашнее задание 2 + 0.3 * Итоговый экзамен + 0.2 * Промежуточный экзамен

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