Бакалавриат
2019/2020
Дискретная математика
Статус:
Курс обязательный (Инфокоммуникационные технологии и системы связи)
Направление:
11.03.02. Инфокоммуникационные технологии и системы связи
Кто читает:
Департамент прикладной математики
Когда читается:
1-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Язык:
русский
Кредиты:
4
Контактные часы:
48
Программа дисциплины
Аннотация
Настоящая дисциплина относится к базовой части профессионального цикла дисциплин образовательной программы "Инфокоммуникационные технологии и системы связи". Цели изучения дисциплины: знакомство с понятиями дискретной математики и теории графов; освоение основных приемов решения практических задач по темам дисциплины; развитие способности интерпретации формальных алгебраических структур, развитие четкого логического мышления. В результате освоения дисциплины студент должен: • Знать базовые понятия дисциплины • Понимать доказательства ключевых теорем курса • Иметь навыки использования математического аппарата дисциплины в дальнейшей учебной и профессиональной деятельности
Цель освоения дисциплины
- Цель - знакомство с понятиями дискретной математики как основы значительной части теории информационных систем, освоение основных приемов решения практических задач по темам дисциплины и развитие навыков математического моделирования практических задач связанных с конечными множествами.
Планируемые результаты обучения
- Знать базовые понятия дисциплины
- Понимать доказательства ключевых теорем курса
- Иметь навыки использования математического аппарата дисциплины в дальнейшей учебной и профессиональной деятельности
Содержание учебной дисциплины
- Общие правила комбинаторики. Конечные выборки.Правила суммы и произведения. Элементы теории множеств. Инъективные и сюрьективные отображения. Определение выборки (упорядоченной и неупорядоченной) с повторениями и без повторений. Примеры.
- Размещения, перестановки и сочетания. Свойства биномиальных коэффициентов. Треугольник Паскаля.Размещения, перестановки и сочетания. Формулы для подсчета числа размещений из n элементов по k (c повторениями и без повторений). Формулы для подсчета числа сочетаний из n элементов по k (с повторениями и без повторений). Примеры. Бином Ньютона и свойства биномиальных коэффициентов. Треугольник Паскаля.
- Разбиения и раскладки. Перестановки данного состава.Задача разбиения конечного множества на подмножества. Задачи раскладки n различных или одинаковых предметов по k различным ящикам. Формула для числа перестановок данного состава. Примеры.
- Формула включений и исключений.Формула включений и исключений. Примеры использования этой формулы (число беспорядков, число сюрьективных отображений и т.п.).
- Производящие функции. Операции над производящими функциями.Определение производящих функций и операций над ними. Свойства производящих функций (линейность, сдвиг начала, подобие, дифференцирование, свертка). Составление таблицы производящих функций.
- Рекуррентные соотношения. Рациональные производящие функции.Однородные линейные рекуррентные соотношения с постоянными коэффициентами порядка r. Теорема о рациональных производящих функциях. Последовательность чисел Фибоначчи.
- Основные понятия теории графов. Изоморфизм графов.Основные понятия теории графов: вершины, ребра, петли, кратности вершин, пути, цепи, циклы, простые графы. Регулярные, полные, связные, двудольные графы. Матрица смежности. Изоморфизм графов.
- Эйлеровы и гамильтоновы графы.Эйлеровы и полуэйлеровы графы. Критерий эйлеровости и полуэйлеровости графа. Гамильтоновы и полугамильтоновы графы. Достаточные условия гамильтоновости графа.
- Укладки графов. Планарные графы.Понятие укладки графа. Планарные графы и примеры не планарных графов. Теорема Эйлера для многогранников. Гомеоморфизм графов. Теорема Понтрягина-Куратовского. Укладка графов на топологических поверхностях. Теорема Кенига.
- Раскраска графов.Понятие раскраски графа. Хроматическое число графа. Оценка хроматического числа планарного графа. Гипотеза четырех красок. Раскрашивание карт.
- Деревья.Понятие дерева. Оставное дерево графа. Элементарные свойства и перечисление деревьев.
Элементы контроля
- Контрольная работа
- Домашняя работа
- Аудиторная работа
- Экзаменписьменный экзамен с прокторингом
Промежуточная аттестация
- Промежуточная аттестация (4 модуль)0.2 * Домашняя работа + 0.3 * Контрольная работа + 0.5 * Экзамен
Список литературы
Рекомендуемая основная литература
- Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике - Издательство "Физматлит" - 2009 - 416с. - ISBN: 978-5-9221-0477-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/2157
- Комбинаторика, Виленкин, Н. Я., 2006
Рекомендуемая дополнительная литература
- Комбинаторика и теория графов : учеб. пособие, Кочетков, Ю. Ю., 2009
- Кочкаров А.А., Яцкин Д.В. - Теория графов и классические задачи прикладной математики в экономике. (Бакалавриат) - КноРус - 2019 - 248с. - ISBN: 978-5-406-07224-0 - Текст электронный // ЭБС BOOKRU - URL: https://book.ru/book/932443