Бакалавриат
2022/2023
Дискретная математика
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 1-3 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Валинкин Михаил Валерьевич,
Вялый Михаил Николаевич,
Енгоян Анна Тиграновна,
Лукьяненко Никита Сергеевич,
Соколов Павел Павлович,
Хузиева Алина Эдуардовна
Язык:
русский
Кредиты:
6
Контактные часы:
104
Программа дисциплины
Аннотация
Дискретная математика-1 — базовый вводный курс, прививающий студентам азы математической культуры, нужные для последующего изучения как математических дисциплин, так и компьютерных наук. Курс знакомит с такими фундаментальными понятиями как множества, алгебра логики, функции и отображения, булевы функции, отношения и графы. Они являются фундаментом как для изучения математики и для структур данных в программировании. Раздел "мощность множеств" важен для изучения математического анализа и готовит студентов к последующему изучению вычислимых функций в рамках курса дискретная математика-2.
Цель освоения дисциплины
- Знакомство с базовыми математическими понятиями.
- Развитие математической культуры (культуры доказательств).
- Изучение фундаментальных разделов, относящихся к дискретной математике, необходимых для успешного прохождения последующих курсов.
Планируемые результаты обучения
- Владеть определениями и математическим аппаратом, связанным с функциями: образы, прообразы, инъекция, сюръекция, биекция.
- Выработать базовую математическую культуру (культуру доказательств)
- Знать базовые комбинаторные числа: число перестановок, сочетаний, размещений, сочетаний с повторениями
- Знать основы теории графов
- Знать основы теории множеств, владеть формулами алгебр множеств и логики
- Изучить доказательство нижних оценок для алгоритмов поиска максимума в массиве и сортировки.
- Освоение ключевых тем основных разделов комбинаторики.
- Умение оперировать терминами и понятиями, освоение подходов к построению определений (могут быть разными в зависимости от источника) комбинаторики.
- Умение ориентироваться в научных источниках с целью нахождения наиболее близкой литературы для решения возникающих задач из комбинаторики.
- Уметь решать базовые комбинаторные задачи: пользоваться правилами суммы и произведения, формулой включений-исключений
- Уметь строить разложения в ДНФ и КНФ, проверять на полноту базис.
- Знание базовых свойств бинарных отношений: рефлексивность, симметричность, транзитивность, антисимметричность, антирефлексивность, линейность; отношения эквивалентности, отношения частичного порядка
- Уметь различать счётные множества и множества мощности континуум. Овладеть диагональным методом на примере теоремы Кантора.
Содержание учебной дисциплины
- Множества и логика
- Комбинаторика
- Алгебра логики
- Математические определения, утверждения и доказательства
- Графы
- Двудольные графы, паросочетания и функции
- Ориентированные графы и отношения порядка.
- Бинарные отношения. Отношения эквивалентности.
- Булевы функции
- Вероятность
- Мощность множеств
- Разрешающие деревья и нижние оценки
Элементы контроля
- Коллоквиум 1
- Домашнее задание 1В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
- Домашнее задание 2В вычислениях текущие оценки и промежуточные величины не округляются. Результат вычисляется точно и округляется только в момент выставления промежуточной и итоговой оценок. При выставлении итоговой и промежуточных оценок используется следующее правило округления: между 1 и 5 округление вниз, между 5 и 6 округление арифметическое, а в остальных случаях округление вверх. Т.е. 3,92 округляется до 3, 5,48 – до 5, 5,54 – до 6, 7,12 – до 8.
- Коллоквиум 2
- Промежуточный экзаменВ письменной форме после второго модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.
- Итоговый экзаменВ письменной форме после третьего модуля. Предполагается очная форма сдачи экзамена. При невозможности проведения очного экзамена проводится дистанционный экзамен по правилам, которые дополнительно сообщаются студентам.
Промежуточная аттестация
- 2022/2023 учебный год 2 модуль0.401 * Промежуточный экзамен + 0.3 * Коллоквиум 1 + 0.299 * Домашнее задание 1
- 2022/2023 учебный год 3 модуль0.2 * Домашнее задание 2 + 0.2 * Промежуточный экзамен + 0.15 * Коллоквиум 1 + 0.15 * Коллоквиум 2 + 0.3 * Итоговый экзамен
Список литературы
Рекомендуемая основная литература
- 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). — Режим доступа: для авториз. пользователей.
Рекомендуемая дополнительная литература
- Дискретная математика. Углубленный курс: Учебник / Соболева Т.С.; Под ред. Чечкина А.В. - М.:КУРС, НИЦ ИНФРА-М, 2017. - 278 с.: - (Бакалавриат) - Режим доступа: http://znanium.com/catalog/product/851215