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

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

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

Направление: 09.03.01. Информатика и вычислительная техника

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

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

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

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

Преподаватели: Гуськова Мария Сергеевна, Рабинович Александр Соломонович

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

Кредиты: 4

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

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

Аннотация

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

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

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

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

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

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

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

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

Активность на семинарских занятиях 1
Домашние задания 1
Контрольная работа 1
Контрольная работа 2
Самостоятельная работа 1
Экзамен 1
контрольно-измерительные материалы
контрольно-измерительные материалы
Активность на семинарских занятиях 2
Домашние задания 2
Контрольная работа 3
Контрольная работа 4
Самостоятельная работа 2
Экзамен 2
контрольно-измерительные материалы
контрольно-измерительные материалы

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

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

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