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

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

Лучший по критерию «Новизна полученных знаний»

Статус: Курс обязательный (Программная инженерия)

Направление: 09.03.04. Программная инженерия

Кто читает: Кафедра информационных технологий в бизнесе (Пермь)

Где читается: Факультет экономики, менеджмента и бизнес-информатики

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

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

Преподаватели: Морозенко Владимир Викторович

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

Кредиты: 8

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

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

Аннотация

Настоящая программа учебной дисциплины устанавливает требования к образовательным результатам и результатам обучения студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих дисциплину «Дискретная математика», учебных ассистентов и студентов направления подготовки 09.03.04 Программная инженерия, обучающихся по образовательной программе «Программная инженерия».

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

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

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

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

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

Теория графов
Тема 1. Основные понятия теории графов, способы задания Тема 2. Типы графов и обходы графов Тема 3. Экстремальные задачи на графах Тема 4. Изоморфизм, планарность, правильная вершинная раскраска Тема 5. Ориентированные графы
Булевы функции, логика высказываний и предикатов
Тема 6. Элементарные булевы функции, канонические способы задания Тема 7. Замкнутые классы булевых функций Тема 8. Полные системы булевых функций, базисы Тема 9. Высказывания, методы проверки логического следования Тема 10. Предикаты, предикатные формулы Тема 11. Метод резолюций в логике высказываний Тема 12. Метод резолюций в логике предикатов
Элементы комбинаторики
Тема 13. Основные комбинаторные операции Тема 14. Комбинаторные принципы Тема 15. Биномиальная и полиномиальная формулы Тема 16. Рекуррентные соотношения
Теория кодирования
Тема 17. Однозначно декодируемые схемы алфавитного кодирования Тема 18. «Экономное» кодирование, коды с минимальной избыточностью Тема 19. Помехоустойчивое кодирование, самокорректирующиеся коды Тема 20. Методы сжатия и шифрования информации
Теория конечных детерминированных автоматов
Тема 21. Конечные детерминированные автоматы, способы задания Тема 22. Регулярные выражения, распознавание регулярных языков Тема 23. Задачи анализа и синтеза автоматов Тема 24. Задача минимизации автоматов Тема 25. Логические автоматы

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

письменная работа 1
письменная работа 2
письменная работа 3
письменная работа 4
самостоятельная работа
Экзамен
Экзамен проводиться очно в виде теста из 30 заданий. Время на выполнение теста - 1 час 20 минут. Студенты, у которых накопленная оценка равна 7 баллам или выше, и оценки за все 4 контрольные точки не ниже 6 баллов, могут получить итоговую оценку по накопленной (в случае согласия с ней). Накопленная оценка вычисляется как среднее арифметическое оценок за все 4 контрольные точки.

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

Промежуточная аттестация (3 модуль)
0.15 * письменная работа 1 + 0.1 * письменная работа 2 + 0.1 * письменная работа 3 + 0.15 * письменная работа 4 + 0.1 * самостоятельная работа + 0.4 * Экзамен

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