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

Бакалавриат 2020/2021

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

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

Статус: Курс обязательный (Информационная безопасность)

Направление: 10.03.01. Информационная безопасность

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

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

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

Преподаватели: Боголюбов Дмитрий Петрович, Бусяцкая Ирина Константиновна, Пахлов Павел Николаевич, Рабинович Александр Соломонович

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

Кредиты: 4

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

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

Аннотация

Настоящая дисциплина относится к базовой части профессионального цикла дисциплин образовательной программы "Инфокоммуникационные технологии и системы связи". Цели изучения дисциплины: знакомство с понятиями дискретной математики и теории графов; освоение основных приемов решения практических задач по темам дисциплины; развитие способности интерпретации формальных алгебраических структур, развитие четкого логического мышления. В результате освоения дисциплины студент должен: • Знать базовые понятия дисциплины • Понимать доказательства ключевых теорем курса • Иметь навыки использования математического аппарата дисциплины в дальнейшей учебной и профессиональной деятельности

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

Знакомство с понятиями дискретной математики как основы важной части математического аппарата теории вероятностей и математической статистики, исследования операций, дискретной оптимизации и других дисциплин;
Развитие способности анализа дискретных структур, развитие строгого логического мышления.

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

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

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

Элементы теории множеств
Типы множеств, основные операции над множествами, законы и, способы доказательств в теории множеств, формула включений и исключений и ее применения.
Элементы математической логики
Основные понятия и способы доказательств в булевской логике, логические функции и их представления, основные понятия логики высказываний, методы доказательства в логике высказываний
Методы подсчета и оценивания
Производящие функции для последовательностей чисел, основные свойства производящих функций, применение производящих функций для решения рекуррентных уравнений и нахождения конечных сумм
Комбинаторные схемы
Определение чисел размещений, перестановок и сочетаний предметов без повторений и с повторениями, определение чисел упорядоченных и неупорядоченных разбиений конечных множеств, бином Ньютона и полиноминальная формула
Основы теории графов
Виды графов, связные графы и деревья, матрицы инцидентности, смежноси и весовые матрицы, построение остовных деревьев в связных графах, минимальное остовное дерево, определение остовных деревьев по матрице инцидентности, нахождение минимальных путей на ориентированных графах, мультиграфы и эйлеровы циклы
Транспортные сети
Транспортные сети и их свойства, арифметические и алгебраические потоки, соотношения на транспортной сети, разрезы в транспортной сети, задача о максимальной величине потока в транспортной сети и алгоритм Форда-Фалкерсона, теорема Форда-Фалкерсона

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

Активность на семинаре 1
Контрольная работа 1
Активность на семинаре 2
Контрольная работа 2
Экзамен 1
Контрольно-измерительные материалы

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

Промежуточная аттестация (4 модуль)
0.1 * Активность на семинаре 1 + 0.1 * Активность на семинаре 2 + 0.15 * Контрольная работа 1 + 0.15 * Контрольная работа 2 + 0.5 * Экзамен 1

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