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

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

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

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

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

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

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

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

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

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

Кредиты: 4

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

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

Аннотация

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

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

Цель - знакомство с понятиями дискретной математики как основы значительной части теории информационных систем, освоение основных приемов решения практических задач по темам дисциплины и развитие навыков математического моделирования практических задач связанных с конечными множествами.

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

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

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

Общие правила комбинаторики. Конечные выборки.
Правила суммы и произведения. Элементы теории множеств. Инъективные и сюрьективные отображения. Определение выборки (упорядоченной и неупорядоченной) с повторениями и без повторений. Примеры.
Размещения, перестановки и сочетания. Свойства биномиальных коэффициентов. Треугольник Паскаля.
Размещения, перестановки и сочетания. Формулы для подсчета числа размещений из n элементов по k (c повторениями и без повторений). Формулы для подсчета числа сочетаний из n элементов по k (с повторениями и без повторений). Примеры. Бином Ньютона и свойства биномиальных коэффициентов. Треугольник Паскаля.
Разбиения и раскладки. Перестановки данного состава.
Задача разбиения конечного множества на подмножества. Задачи раскладки n различных или одинаковых предметов по k различным ящикам. Формула для числа перестановок данного состава. Примеры.
Формула включений и исключений.
Формула включений и исключений. Примеры использования этой формулы (число беспорядков, число сюрьективных отображений и т.п.).
Производящие функции. Операции над производящими функциями.
Определение производящих функций и операций над ними. Свойства производящих функций (линейность, сдвиг начала, подобие, дифференцирование, свертка). Составление таблицы производящих функций.
Рекуррентные соотношения. Рациональные производящие функции.
Однородные линейные рекуррентные соотношения с постоянными коэффициентами порядка r. Теорема о рациональных производящих функциях. Последовательность чисел Фибоначчи.
Основные понятия теории графов. Изоморфизм графов.
Основные понятия теории графов: вершины, ребра, петли, кратности вершин, пути, цепи, циклы, простые графы. Регулярные, полные, связные, двудольные графы. Матрица смежности. Изоморфизм графов.
Эйлеровы и гамильтоновы графы.
Эйлеровы и полуэйлеровы графы. Критерий эйлеровости и полуэйлеровости графа. Гамильтоновы и полугамильтоновы графы. Достаточные условия гамильтоновости графа.
Укладки графов. Планарные графы.
Понятие укладки графа. Планарные графы и примеры не планарных графов. Теорема Эйлера для многогранников. Гомеоморфизм графов. Теорема Понтрягина-Куратовского. Укладка графов на топологических поверхностях. Теорема Кенига.
Раскраска графов.
Понятие раскраски графа. Хроматическое число графа. Оценка хроматического числа планарного графа. Гипотеза четырех красок. Раскрашивание карт.
Деревья.
Понятие дерева. Оставное дерево графа. Элементарные свойства и перечисление деревьев.

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

Контрольная работа
Домашняя работа
Аудиторная работа
Экзамен
письменный экзамен с прокторингом

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

Промежуточная аттестация (4 модуль)
0.2 * Домашняя работа + 0.3 * Контрольная работа + 0.5 * Экзамен

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