Бакалавриат
2020/2021
Дискретная математика
Статус:
Курс обязательный (Программная инженерия (очно-заочное обучение))
Направление:
09.03.04. Программная инженерия
Где читается:
Вечерне-заочный факультет экономики и управления (Пермь)
Когда читается:
1-й курс, 3, 4 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Викентьева Ольга Леонидовна
Язык:
русский
Кредиты:
8
Контактные часы:
48
Программа дисциплины
Аннотация
Содержание программы дисциплины «Дискретная математика» должно обеспечить базовую подготовку студентов в процессе формирования устойчивых теоретических знаний и практических навыков анализа алгоритмов при решении различных задач оптимизации и разработке средств автоматизированной поддержки принятия решений.
Цель освоения дисциплины
- Целями освоения дисциплины «Дискретная математика» являются: изучение дискретных структур, применяемых при разработке математических моделей и алгоритмов; изучение алгоритмов, используемых при решении социально-экономических, информационно-технологических и вычислительных задач поиска и оптимизации в дискретных пространствах.
Планируемые результаты обучения
- решает типовые задачи теории графов
- решает типовые задачи теории булевых функций и логики
- решает типовые задачи теории кодирования
- решает типовые задачи теории конечных детерминированных автоматов
- решает типовые задачи теории множеств
- решает типовые задачи комбинаторики
Содержание учебной дисциплины
- Множества, соответствия, отношенияТема 1. Основные понятия теории множеств, способы задания. Основные определения, понятия, обозначения теории множеств. Диаграммы Венна. Операции над множествами: объединение, пересечение, дополнение. Прямое произведение множеств. Основные способы задания множеств. Тема 2. Соответствия и отношения Общее понятие отношения и соответствия. Теоретико-множественные операции над соответствиями, классификация соответствий. Бинарные отношения и их свойства. Транзитивное замыкание отношений. Отношение эквивалентности и классы эквивалентности. Отношение порядка. Диаграммы Хассе. Линейный порядок и частичный порядок. Квазипорядок. Решетки. Тема 3. Мощность множеств. Понятие мощности множества по Кантору. Теорем Кантора. Арифметика бесконечного.
- Булевы функции, логика высказываний и предикатовТема 6. Элементарные булевы функции, канонические способы задания Тема 7. Замкнутые классы булевых функций Тема 8. Полные системы булевых функций, базисы Тема 9. Высказывания, методы проверки логического следования Тема 10. Предикаты, предикатные формулы Тема 11. Метод резолюций в логике высказываний Тема 12. Метод резолюций в логике предикатов
- Теория графовТема 1. Основные понятия теории графов, способы задания Тема 2. Типы графов и обходы графов Тема 3. Экстремальные задачи на графах Тема 4. Изоморфизм, планарность, правильная вершинная раскраска Тема 5. Ориентированные графы
- КомбинаторикаТема 14. Основные комбинаторные операции. Основные комбинаторные операции: выборки с возвращением и без возвращения элементов, выборки с упорядочением и без упорядочения элементов, сочетания и размещения, числа сочетаний и размещений. Тема 15. Комбинаторные принципы Основные комбинаторные принципы: принцип сложения, принцип умножения, принцип дополнения, принцип включения-исключения, принцип кодирования. Тема 16. Биномиальная и полиномиальная формулы Треугольник Паскаля, бином Ньютона, биномиальные коэффициенты, их основные свойства. Полиномиальная формула.
- Теория конечных детерминированных автоматовТема 21. Конечные детерминированные автоматы, способы задания Тема 22. Регулярные выражения, распознавание регулярных языков Тема 23. Задачи анализа и синтеза автоматов Тема 24. Задача минимизации автоматов Тема 25. Логические автоматы
- Теория кодированияТема 17. Однозначно декодируемые схемы алфавитного кодирования Тема 18. «Экономное» кодирование, коды с минимальной избыточностью Тема 19. Помехоустойчивое кодирование, самокорректирующиеся коды Тема 20. Методы сжатия и шифрования информации
Элементы контроля
- Аудиторная работа2 письменные работы. Вес при оценивании делится поровну по 0.15.
- Самостоятельная работа
- Экзамен
Промежуточная аттестация
- Промежуточная аттестация (4 модуль)0.3 * Аудиторная работа + 0.3 * Самостоятельная работа + 0.4 * Экзамен
Список литературы
Рекомендуемая основная литература
- Лекции по дискретной математике : учеб. пособие / В.Б. Алексеев. — М. : ИНФРА-М, 2018. — 90 с. — (Высшее образование: Бакалавриат). - Режим доступа: http://znanium.com/catalog/product/952158
Рекомендуемая дополнительная литература
- Дискретная математика для программистов : учеб. пособие, Новиков Ф.А., 2009
- Таранников Ю. В. - ДИСКРЕТНАЯ МАТЕМАТИКА. ЗАДАЧНИК. Учебное пособие для академического бакалавриата - М.:Издательство Юрайт - 2019 - 385с. - ISBN: 978-5-534-01180-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-zadachnik-433218