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

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

Статус: Курс по выбору (Прикладная математика и информатика)

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

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

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

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

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

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

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

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

Кредиты: 6

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

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

Аннотация

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

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

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

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

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

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

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

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

Домашнее задание 1
Среднее арифметическое оценок за домашние задания первого и второго модуля. Домашние задания выдаются раз в неделю и должны быть выполнены в течение недели. Предварительная оценка за домашнее задание выставляется в 10-балльной шкале и пропорциональна доле решенных задач (с учетом неполных решений, за которые выставляется неполный балл). Для проверки остаточных знаний по темам домашних заданий проводится выборочная защита (устная беседа) по решенным (хотя бы частично) задачам. В случае, если студент не может ответить на ключевые вопросы по решению задачи или сформулировать используемые при решении задач теоремы и определения, преподаватель уменьшает предварительную оценку за домашнее задание на 50%. При неудаче ответа по двум задачам оценка за домашнее задание обнуляется. Комментарий. Помимо обязательных домашних заданий будут выдаваться дополнительные домашние задания. Они не являются элементом контроля, играют чисто учебную роль и служат для тренировки в решении более трудных задач по материалам курса. Дополнительные домашние задания проверяются, но оценки за них не учитываются в оценке за курс. В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
Домашнее задание 2
Среднее арифметическое оценок за домашние задания третьего модуля, выставляется аналогично оценке Домашнее задание 1.
Письменная контрольная работа по проверке теоретических знаний – 1
Проводится в конце второго модуля во время семинарских занятий по темам, изученным к моменту проведения контрольной.
Промежуточный экзамен
Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам. Экзамен проводится в письменной форме после второго модуля. Письменный экзамен служит для проверки умения творчески использовать полученные знания при решении новых для студента задач. Участие в письменном экзамене необязательное, более того, рекомендуется идти на экзамен только студентам, претендующим на оценку не ниже 8 (при этом оценку 8 возможно получить, не сдавая экзамена). Задания в промежуточном письменном экзамене возможны по всем темам, которые изучались в первых двух модулях. Критерии проверки и правила оценивания экзаменационных работ объявляются после проверки работ.
Письменная контрольная работа по проверке теоретических знаний – 2
Проводится в конце третьего модуля во время семинарских занятий по темам, изученным к моменту проведения контрольной (включая темы второго модуля, не вошедшие в первую контрольную работу).
Итоговый экзамен
Правила проведения полностью аналогичны правилам промежуточного экзамена, только задачи возможны по всем темам курса.

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

2023/2024 учебный год 2 модуль
Промежуточная аттестация после второго модуля. Формула оценки зависит от результата письменного экзамена второго модуля. Если оценка за письменный экзамен не больше 5, то оценка промежуточной аттестации Оценка 2 модуля = 0.25 * Домашнее задание 1 + 0.55* Контрольная 1 Если оценка за письменный экзамен больше 5, то оценка промежуточной аттестации Оценка 2 модуля = 0.25 * Домашнее задание 1 + 0.55* Контрольная 1 + 0.2* Промежуточный экзамен Программой дисциплины не предусмотрено обучение в 3 модуле тех, кто получил неудовлетворительную промежуточную оценку в 1 семестре.
2023/2024 учебный год 3 модуль
Окончательная оценка по курсу. Формула оценки зависит от результата письменного экзамена 3 модуля. Если оценка за письменный экзамен не больше 5, то оценка промежуточной аттестации Оценка 3 модуля = 0.2*Оценка 2 модуля + 0.2* Домашнее задание 2 + 0.4 * Контрольная2 Если оценка за письменный экзамен больше 5, то оценка промежуточной аттестации Оценка 3 модуля = 0.2*Оценка 2 модуля + 0.2* Домашнее задание 2 + 0.4 * Контрольная2 + 0.2*Итоговый экзамен

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

Авторы

Подольский Владимир Владимирович
Вялый Михаил Николаевич

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