Бакалавриат
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*Итоговый экзамен
Список литературы
Рекомендуемая основная литература
- Lovász, L., Pelikán, J., & Vsztergombi, K. (2003). Discrete Mathematics : Elementary and Beyond. New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=108108
Рекомендуемая дополнительная литература
- Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., доп. — Москва : МЦНМО, [б. г.]. — Часть 2 : Языки и исчисления — 2008. — 288 с. — ISBN 978-5-94057-322-7. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9307 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.
- Верещагин, Н. К. Лекции по математической логике и теории алгоритмов : учебное пособие / Н. К. Верещагин, А. Шень. — 3-е изд., стер. — Москва : МЦНМО, [б. г.]. — Часть 1 : Начала теории множеств — 2008. — 128 с. — ISBN 978-5-94057-321-0. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/9306 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.