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

2020/2021

Учебный год

RUS

Обучение ведется на русском языке

8

Кредиты

Кто читает:

Вечерне-заочный факультет экономики и управления (Пермь)

Статус:

Курс обязательный

Когда читается:

1-й курс, 3, 4 модуль

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

Аннотация

Содержание программы дисциплины «Дискретная математика» должно обеспечить базовую подготовку студентов в процессе формирования устойчивых теоретических знаний и практических навыков анализа алгоритмов при решении различных задач оптимизации и разработке средств автоматизированной поддержки принятия решений.

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

• Целями освоения дисциплины «Дискретная математика» являются:  изучение дискретных структур, применяемых при разработке математических моделей и алгоритмов;  изучение алгоритмов, используемых при решении социально-экономических, информационно-технологических и вычислительных задач поиска и оптимизации в дискретных пространствах.

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

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

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

• Множества, соответствия, отношения
  Тема 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