Бакалавриат
2019/2020
Дискретная математика
Статус:
Курс обязательный
Направление:
38.03.05. Бизнес-информатика
Когда читается:
1-й курс, 1 модуль
Формат изучения:
без онлайн-курса
Язык:
русский
Кредиты:
6
Программа дисциплины
Аннотация
Дисциплины «Дискретная математика» является одной из базовых дисциплин для подготовки студентов по направлению Бизнес-информатика. Содержание дисциплины направлено на изучение студентами дискретной математики, как математической и логической основы разработки информационных технологий.
Цель освоения дисциплины
- Целями освоения дисциплины «Дискретная математика» являются: ознакомление студентов с основами современной дискретной математики; формирование навыков работы с абстрактными понятиями математики; знакомство с прикладными задачами дисциплины.
Планируемые результаты обучения
- В результате освоения дисциплины студент должен: Знать основы дискретной математики, необходимые для дальнейшего изучения по-следующих дисциплин, предусмотренных базовым и рабочим учебными планами; Уметь применять идеи и методы современной дискретной математики для решения задач, возникающих в дисциплинах, их использующих; Владеть навыками применения современного инструментария дискретной математики.
Содержание учебной дисциплины
- Алгебра высказываний, предикаты и кванторы, логические функцииПонятие высказывания. Логические операции на высказываниях. Предикаты и кванторы. Булевы (логические) функции и способы их задания. Эквивалентные преобразования логических формул.
- Множества и соответствияМножества - основные понятия. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Прямое произведение множеств. Соответствия, теоретикомножественные операции над соответствиями, полный образ и прообраз множества при данном соответствии, классификация соответствий: всюдуопределенность, функциональность, инъективность, сюръективность. Частичные функции, отображения, взаимно-однозначные соответствия. Обратимость частичной функции и отображения. Композиция соответствий и ее свойства. Матричное представление композиции соответствий. Понятие функции. Обратные функции. Суперпозиции и формулы. Способы задания функций. Обратимые отображения и их свойства. Преобразования множества, подстановки.
- Комбинаторика Предмет комбинаторики.Правило суммы и правило произведения. Принцип включения и исключения. Размещения, перестановки, сочетания без повторений и с повторениями. Биномиальные коэффициенты и соотношения для них. Задачи перечисления. Подсчет числа функций с конечными областями определения. Задача Муавра.
- Бинарные отношения Общее понятие отношения.Бинарные отношения и их свойства (рефлексивность, симметричность, транзитивность). Транзитивное замыкание отношений. Отношение эквивалентности и классы эквивалентности. Отношение толерантности, классы толерантности. Отношение порядка. Диаграммы Хассе. Линейный порядок и частичный порядок. Квазипорядок. Решетки.
- Математическая логика и логика предикатовСпособы задания логических функций, фиктивные и существенные переменные, порядок логической функции. Формулы над системой логических функций или их суперпозиции. Теорема о разложении логических функций по переменным. Совершенные дизъюнктивные и конъюнктивные формы. Определение замкнутого класса. Полные системы функ-ций. Базис и порядок замкнутого класса. Алгебра Жегалкина. Теорема об единственности многочлена Жегалкина. Классы Поста: функции сохраняющие 0, функции сохраняющие 1, самодвойственные функции, монотонные функции, линейные функции. Теорема Поста о функциональной полноте. Логические методы анализа и синтеза переключательных схем. Логика предикатов. Предметная область и предметные переменные. Правильно по-строенные формулы. Кванторы общности и существования. Свободные и связанные пе-ременные. Общезначимые и противоречивые формулы. Запись утверждений естествен-ного языка в логике предикатов. Логический вывод в логике высказываний. Теорема де-дукции и ее следствия. Логический вывод в логике предикатов на основе правила резолюции. Извлечение ответа на вопрос из опровержения, основанного на резолюции.
- Теория графовОсновные определения: неориентированные и ориентированные графы, мультиграфы и кратные ребра. Смежность и инцидентность. Локальные степени вершин. Способы представления графов. Матрицы смежности и инцидентности. Графы и бинарные отношения. Изоморфизм графов. Части графов, суграфы и подграфы. Пути, циклы, цепи, простые цепи в неориентированных графах. Связность и компоненты связности. Шарниры мосты и блоки графа. Расстояния. Центр, радиус, диаметр графа. Виды связности в ориентированных графах: сильная связность, односторонняя связность. Задачи о цепях: эйлеровы циклы, гамильтоновы циклы. Основные числа теории графов: цикломатическое число, хроматическое число. Бихроматические (двудольные) графы. Число внутренней устойчи-вости. Число внешней устойчивости. Метод Магу для отыскания всех максимальных внутренне устойчивых множеств, а также минимальных внешне устойчивых множеств. Метод Магу для нахождения хроматического числа графа. Деревья. Алгоритмы нахождения связных суграфов заданного графа с взвешенными ребрами с минимальной стоимостью. Плоские графы, формула Эйлера, необходимые и достаточные условия того, что граф является плоским (теорема Понтрягина-Куратовского). Транспортные сети. Потоки в транспортных сетях. Алгоритм Форда-Фалкерсона для нахождения максимального по-тока. Теорема Форда-Фалкерсона. Алгоритм Дейкстры поиска наикратчайшего пути на орграфе с взвешенными дугами.
- Теория алгоритмовОбщее понятие алгоритма. Требования к алгоритмам. Емкостная и вычислительная сложность алгоритмов. Понятие рекурсии. Рекурсивные функции. Тезис Черча. Машины Тьюринга. Некоторые алгоритмически неразрешимые проблемы.
- Конечные автоматыПонятие конечного автомата Мили и автомата Мура. Примеры применения. Автоматные функции, способы их задания. Минимизация автоматов. Теорема о преобразовании периодической последовательности автоматной функцией. Теорема Мура.
Промежуточная аттестация
- Промежуточная аттестация (1 модуль)0.6 * контрольная работа + 0.4 * самостоятельная работа
Список литературы
Рекомендуемая основная литература
- Гашков С. Б., Фролов А. Б. - ДИСКРЕТНАЯ МАТЕМАТИКА 3-е изд., испр. и доп. Учебник и практикум для вузов - М.:Издательство Юрайт - 2019 - 483с. - ISBN: 978-5-534-11613-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-445753
- Дискретная математика для инженера : [учеб. пособие], Кузнецов О.П., 2009
- Плотникова Е. Г., Левко С. В., Логинова В. В., Хакимова Г. М. ; Под общ. ред. Плотниковой Е. Г. - МАТЕМАТИЧЕСКИЙ АНАЛИЗ И ДИСКРЕТНАЯ МАТЕМАТИКА 2-е изд., пер. и доп. Учебное пособие для вузов - М.:Издательство Юрайт - 2019 - 300с. - ISBN: 978-5-534-07545-8 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/matematicheskiy-analiz-i-diskretnaya-matematika-441347
Рекомендуемая дополнительная литература
- Андреев А. Е., Болотов А. А., Коляда К. В., Фролов А. Б. - ДИСКРЕТНАЯ МАТЕМАТИКА: ПРИКЛАДНЫЕ ЗАДАЧИ И СЛОЖНОСТЬ АЛГОРИТМОВ 2-е изд., испр. и доп. Учебник и практикум для академического бакалавриата - М.:Издательство Юрайт - 2019 - 317с. - ISBN: 978-5-534-04246-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-prikladnye-zadachi-i-slozhnost-algoritmov-444120
- под науч. ред. Сесекина А.Н. - ДИСКРЕТНАЯ МАТЕМАТИКА. Учебное пособие для вузов - М.:Издательство Юрайт - 2019 - 108с. - ISBN: 978-5-534-08214-2 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-438245