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

2019/2020

Учебный год

RUS

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

8

Кредиты

Кто читает:

Кафедра информационных технологий в бизнесе (Пермь) (Факультет социально-экономических и компьютерных наук)

Статус:

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

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

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

Преподаватель

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

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

Аннотация

Настоящая программа учебной дисциплины устанавливает требования к образовательным результатам и результатам обучения студента и определяет содержание и виды учебных занятий и отчетности. Программа предназначена для преподавателей, ведущих дисциплину «Дискретная математика», учебных ассистентов и студентов направления подготовки 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
• самостоятельная работа
• Экзамен
  Экзамен проводится с использованием асинхронного прокторинга. Требования к ПК пользователя: 1. Стационарный компьютер или ноутбук (мобильные устройства не поддерживаются); 2. Операционная система Windows (версии 7, 8, 8.1, 10) или Mac OS X Yosemite 10.10 и выше; 3. Интернет-браузер Google Chrome последней на момент сдачи экзамена версии: (для установки браузера используйте ссылку https://www.google.com/chrome/, для проверки и обновления версии браузера используйте ссылку chrome://help/, при переходе можно увидеть номер версии своего браузера и кнопку для обновления, если они доступны); 4. Наличие постоянного интернет-соединения со скоростью передачи данных от пользователя не ниже 5 Мбит/сек.; 5. Разрешена передача данных по сетевым портам: 80 TCP, 443 TCP, 3478 TCP/UDP (уточнить этот вопрос у провайдера/открыть панель управления - система и безопасность - брандмауэр защитника Windows- дополнительные параметры. Убедитесь, что нет ограничений на входящее и исходящее соединение); 6. Наличие исправной и включенной веб-камеры (включая встроенные в ноутбуки); 7. Наличие исправного и включенного микрофона (включая встроенные в ноутбуки). https://elearning.hse.ru/data/2020/04/23/1559799268/Инструкция%20по%20работе%20в%20системе%20прокторинга%20Экзамус%202020.%20Асинхрон.pdf

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

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

Список литературы

Рекомендуемая основная литература

• Авдошин С.М., Набебин А.А. - Дискретная математика. Модулярная алгебра, криптография, кодирование - Издательство "ДМК Пресс" - 2017 - 352с. - ISBN: 978-5-97060-408-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/93575
• Лекции по дискретной математике : учеб. пособие / В.Б. Алексеев. — М. : ИНФРА-М, 2018. — 90 с. — (Высшее образование: Бакалавриат). - Режим доступа: http://znanium.com/catalog/product/952158

Рекомендуемая дополнительная литература

• Таранников Ю. В. - ДИСКРЕТНАЯ МАТЕМАТИКА. ЗАДАЧНИК. Учебное пособие для академического бакалавриата - М.:Издательство Юрайт - 2019 - 385с. - ISBN: 978-5-534-01180-7 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-zadachnik-433218