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

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

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

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

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

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

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

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

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

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

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

Кредиты: 6

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

Рекомендуемая основная литература

• 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
• Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-321-0 - 2008 - русский - https://e.lanbook.com/book/9306 - ЛАНЬ - 9306

Рекомендуемая дополнительная литература

• Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления - Верещагин Н.К., Шень А. - Московский центр непрерывного математического образования - 978-5-94057-322-7 - 2008 - русский - https://e.lanbook.com/book/9307 - ЛАНЬ - 9307

Авторы

• Вялый Михаил Николаевич
• Подольский Владимир Владимирович
• Оруджева Альбина Александровна