ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.12.2023
Просмотров: 2352
Скачиваний: 21
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
| УП: 27.03.03_ИАС_ИК_2021.plx | | стр. 4 | |||
| 1. ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ (МОДУЛЯ) | |||||
| | | | | | |
| Дисциплина «Дискретная математика» имеет своей целью способствовать формированию у обучающихся компетенций. предусмотренных данной рабочей программой в соответствии с требованиями ФГОС ВО по направлению подготовки 27.03.03 Системный анализ и управление с учетом специфики направленности подготовки – «Инженерия автоматизированных систем». | |||||
| | | | | | |
| 2. МЕСТО ДИСЦИПЛИНЫ (МОДУЛЯ) В СТРУКТУРЕ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ | |||||
| | Направление: | | 27.03.03 Системный анализ и управление | ||
| | |||||
| | Направленность: | | Инженерия автоматизированных систем | ||
| | | | |||
| | Блок: | | Дисциплины (модули) | ||
| | | | |||
| | Часть: | | Обязательная часть | ||
| | | | |||
| | Общая трудоемкость: | | 3 з.е. (108 акад. час.). | ||
| | | | |||
| | | | | | |
| 3. КОМПЕТЕНЦИИ ОБУЧАЮЩЕГОСЯ, ФОРМИРУЕМЫЕ В РЕЗУЛЬТАТЕ ОСВОЕНИЯ ДИСЦИПЛИНЫ (МОДУЛЯ) | |||||
| | | | | | |
| В результате освоения дисциплины обучающийся должен овладеть компетенциями: | |||||
| ОПК-1 - Способен анализировать задачи профессиональной деятельности на основе положений, законов и методов в области естественных наук и математики | |||||
| ОПК-2 - Способен формулировать задачи профессиональной деятельности на основе знаний профильных разделов математических и естественнонаучных дисциплин (модулей) | |||||
| | | | | | |
| ПЛАНИРУЕМЫЕ РЕЗУЛЬТАТЫ ОБУЧЕНИЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ), ХАРАКТЕРИЗУЮЩИЕ ФОРМИРОВАНИЯ КОМПЕТЕНЦИЙ | |||||
| | | | | | |
| ОПК-1 : Способен анализировать задачи профессиональной деятельности на основе положений, законов и методов в области естественных наук и математики | |||||
| | | | | | |
| ОПК-1.1 : Анализирует задачи профессиональной деятельности на основе положений, законов и методов в области математики | |||||
| Знать: | |||||
| - основные принципы построения дискретных математических моделей для решения задач, возникающих в ходе профессиональной деятельности | |||||
| Уметь: | |||||
| - решать задачи дискретной математики, возникающие в ходе различных видов профессиональной, в частности в научной и образовательной, деятельности. | |||||
| Владеть: | |||||
| - способностью выявлять естественно-научную сущность проблем, возникающих в ходе профессиональной деятельности, привлекать для их решения математический аппарат из различных разделов дискретной математики. | |||||
| | | | | | |
| ОПК-2 : Способен формулировать задачи профессиональной деятельности на основе знаний профильных разделов математических и естественнонаучных дисциплин (модулей) | |||||
| | | | | | |
| ОПК-2.1 : Формулирует задачи профессиональной деятельности на основе знаний профильных разделов математических дисциплин | |||||
| Знать: | |||||
| - математический аппарат дискретной математики, в частности, математический аппарат теории булевых функций и теории графов | |||||
| УП: 27.03.03_ИАС_ИК_2021.plx | | | | | стр. 5 | ||||
| Уметь: | |||||||||
| - планировать процесс исследования дискретных систем и применять методы дискретной математики для решения практических задач | |||||||||
| Владеть: | |||||||||
| - методами и алгоритмами дискретной математики, в частности, методами и алгоритмами дискретной и комбинаторной оптимизации | |||||||||
| | | | | | | | |||
| В РЕЗУЛЬТАТЕ ОСВОЕНИЯ ДИСЦИПЛИНЫ (МОДУЛЯ) ОБУЧАЮЩИЙСЯ ДОЛЖЕН | |||||||||
| | | | | | | | |||
| Знать: | |||||||||
| - математический аппарат дискретной математики, в частности, математический аппарат теории булевых функций и теории графов | |||||||||
| - основные принципы построения дискретных математических моделей для решения задач, возникающих в ходе профессиональной деятельности | |||||||||
| Уметь: | |||||||||
| - планировать процесс исследования дискретных систем и применять методы дискретной математики для решения практических задач | |||||||||
| - решать задачи дискретной математики, возникающие в ходе различных видов профессиональной, в частности в научной и образовательной, деятельности. | |||||||||
| Владеть: | |||||||||
| - методами и алгоритмами дискретной математики, в частности, методами и алгоритмами дискретной и комбинаторной оптимизации | |||||||||
| - способностью выявлять естественно-научную сущность проблем, возникающих в ходе профессиональной деятельности, привлекать для их решения математический аппарат из различных разделов дискретной математики. | |||||||||
| | | | | | | | |||
| 4. СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ) | |||||||||
| | | | | | | | |||
| При проведении учебных занятий организация обеспечивает развитие у обучающихся навыков командной работы, межличностной коммуникации, принятия решений и лидерских качеств. | |||||||||
| Код занятия | Наименование разделов и тем /вид занятия/ | Сем. | Часов | Компетенции | |||||
| 1. Булевы функции. Дизъюнктивные нормальные формы. СДНФ и СКНФ. | |||||||||
| 1.1 | Булевы функции. Дизъюнктивные нормальные формы. СДНФ и СКНФ. (Лек). Булев вектор. Число булевых векторов длины n, n-мерный булев куб, его изображение для n=2,3,4. Булевы функции. Различные способы их задания. Число булевых функций от n переменных. Элементарные булевы функции. Задание булевых функций формулами. Эквивалентность формул. Элементарные конъюнкции. Дизъюнктивные нормальные формы. Теорема о существовании и единственности СДНФ буле-вой функции. Алгоритм приведения булевой функции к СДНФ. СКНФ, ее существование и единственност | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| УП: 27.03.03_ИАС_ИК_2021.plx | | | | | стр. 6 | ||||
| 1.2 | Выполнение практических заданий (Пр). Булевы векторы, их нумерация. n-мерный булев куб, число булевых векторов в n-м булевом кубе. Задание булевых функций таблицей истинности, носителем, вектором значений. Переход от одного способа к другому. Число булевых функций от n переменных. Элементарные булевы функции. Задание булевых функций формулами. Построение таблиц истинности булевых функций, заданных формулами. Приведение булевых функций, заданных различными способами к СДНФ и СКНФ | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 1.3 | Подготовка к аудиторным занятиям (Ср). Выполнение заданий. | 2 | 7 | ОПК-1.1, ОПК -2.1 | |||||
| 2. Минимальная дизъюнктивная нормальная форма. Миними-зация булевых функций. Метод Карно. Метод Квайна-Мак-Класки. | |||||||||
| 2.1 | Минимальная дизъюнктивная нормальная форма. Миними-зация булевых функций. Метод Карно. Метод Квайна-Мак-Класки. (Лек). Минимальная ДНФ булевой функции. Интер-вал, максимальный и ядровый интервал булевой функции. Геометрический метод отыскания минимальной ДНФ булевой функции от трех переменных. Изображение трехмерного и четырехмерного булева куба в виде карт Карно. Представление интервалов на карте Карно. Алгоритм минимизации булевой функции 3-х и 4-х переменных методом Карно. Алгоритм миними-зации булевой функции 4-х переменных мето-дом Квайна. | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 2.2 | Выполнение практических заданий (Пр). Отыскание минимальной ДНФ булевой функции от 3-х переменных. Метод Карно для булевой функции от 3-х переменных. Алгоритм минимизации булевой функции 4-х переменных методом Карно. Алгоритм минимизации булевой функции 4-х переменных методом Квайна. | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 2.3 | Подготовка к аудиторным занятиям (Ср). Выполнение заданий. | 2 | 7 | ОПК-1.1 | |||||
| 3. Замкнутые классы булевых функций. | |||||||||
| 3.1 | Замкнутые классы булевых функций. (Лек). Определение замкнутого класса. Классы T0 и T1 функций, сохраняющих константы, их замк-нутость. Двойственная функция. Принцип двойственности. Класс S самодвойственных функций, его замкнутость. Многочлены Жегал-кина булевой функции. Способы вычисления многочлена Жегалкина. Линейные функции. Необходимое условие линейности. Класс L ли-нейных функций, его замкнутость. Класс M мо-нотонных функций, его замкнутость. Число бу-левых функций от n переменных в классах T0, T1, S, L. | 2 | 2 | ОПК-2.1, ОПК -1.1 | |||||
| УП: 27.03.03_ИАС_ИК_2021.plx | | | | | стр. 7 | ||||
| 3.2 | Выполнение практических заданий (Пр). Проверка принадлежности булевой функции классам T0, T1, S, M. Представление булевой функции многочленом Жегалкина. Способы нахождения многочлена Жегалкина (метод неопределенных коэффициентов, метод преобразования вектора значений). Проверка булевой функции на линейность. Использование необходимого условия линейности. | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 3.3 | Подготовка к аудиторным занятиям (Ср). Выполнение заданий. | 2 | 7 | ОПК-1.1 | |||||
| 4. Функциональная полнота. | |||||||||
| 4.1 | Функциональная полнота. (Лек). Доказательство теоремы Поста о функциональной полноте. Проверка функциональной полноты системы булевых функций с помощью критерия Поста. Представление булевой функции формулой над заданной функционально полной системой булевых функций. | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 4.2 | Выполнение практических заданий (Пр). Проверка функциональной полноты системы булевых функций с помощью критерия Поста. Представление булевой функции формулой над заданной функционально полной системой булевых функций. | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 4.3 | Подготовка к аудиторным занятиям (Ср). Выполнение заданий. | 2 | 7 | ОПК-1.1, ОПК -2.1 | |||||
| 5. Графы. Орграфы. Функциональные и контактные схемы. | |||||||||
| 5.1 | Графы. Орграфы. Функциональные и контактные схемы. (Лек). Определение и способы задания графов. Орграф. Маршруты, циклы, связность. Определение дерева, его свойства. Бесконтурный орграф. Функциональные схемы и их сложность. Контактные схемы. Построение минимальной функциональной схемы, реализующей задан-ную булеву функцию, над системой {¬, &, }. Построение минимальной контактной схемы, реализующей заданную булеву функцию. | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 5.2 | Выполнение практических заданий (Пр). Нахождение булевой функции, заданной функциональной схемой. Построение минимальной функциональной схемы, реализующей заданную булеву функцию над системой {-, &, V}. Нахождение булевой функции, заданной контактной схемой. Построение минимальной контактной схемы, реализующей заданную булеву функцию. | 2 | 2 | ОПК-1.1, ОПК -2.1 | |||||
| 5.3 | Подготовка к аудиторным занятиям (Ср). Выполнение заданий. | 2 | 7 | ОПК-1.1, ОПК -2.1 | |||||
| УП: 27.03.03_ИАС_ИК_2021.plx | | | | | стр. 8 | |
| 6. Оптимизационные задачи на графах. | ||||||
| 6.1 | Оптимизационные задачи на графах. (Лек). Остов дерева. Задача о нахождении остова минимального веса (алгоритм Краскала). Отыска-ние кратчайших путей в графе. Алгоритмы Дейкстры нахождения кратчайшего пути в графе с положительными весам ребер. | 2 | 2 | ОПК-1.1, ОПК -2.1 | ||
| 6.2 | Выполнение практических заданий (Пр). Задача о нахождении остова минимального веса (алгоритм Краскала). Алгоритм Дейкстры нахождения кратчайшего пути в графе с положительными весами ребер. Построение вспомогательной таблицы, отображающей шаги выполнения алгоритма Дейкстры. | 2 | 2 | ОПК-1.1, ОПК -2.1 | ||
| 6.3 | Подготовка к аудиторным занятиям (Ср). Выполнение заданий. | 2 | 7 | ОПК-1.1, ОПК -2.1 | ||
| Избранные_задачи_на_графах._Двудольные_графы_и_задача_об_оптимальном_назначении.__7.1'>7. Избранные задачи на графах. Двудольные графы и задача об оптимальном назначении. | ||||||
| 7.1 | Избранные задачи на графах. Двудольные графы и задача об оптимальном назначении. (Лек). Двудольные графы. Паросочетания в двудольных графах. Венгерский алгоритм отыскания максимального паросочетания. Задача об оптимальном назначении. | 2 | 2 | ОПК-1.1, ОПК -2.1 | ||
| 7.2 | Выполнение практических заданий (Пр). Венгерский алгоритм отыскания максимального паросочетания. Задача об оптимальном назначении. | 2 | 2 | ОПК-1.1, ОПК -2.1 | ||
| 7.3 | Подготовка к аудиторным занятиям (Ср). Выполнение заданий. | 2 | 7 | ОПК-1.1, ОПК -2.1 | ||
| 8. Транспортные сети и потоки. | ||||||
| 8.1 | Транспортные сети и потоки. (Лек). Транспортные сети. Задача об отыскании мак-симального потока в транспортной сети. | 2 | 2 | ОПК-1.1, ОПК -2.1 | ||
| 8.2 | Выполнение практических заданий (Пр). Разрезы. Задача об отыскании максимального потока в транспортной сети. | 2 | 2 | ОПК-1.1, ОПК -2.1 | ||
| 8.3 | Выполнение домашнего задания (Ср). Выполнение заданий. | 2 | 9 | ОПК-1.1, ОПК -2.1 | ||
| 9. Промежуточная аттестация (зачёт) | ||||||
| 9.1 | Подготовка к сдаче промежуточной аттестации (Зачёт). | 2 | 17,75 | ОПК-1.1, ОПК -2.1 | ||
| 9.2 | Контактная работа с преподавателем в период промежуточной аттестации (КрПА). | 2 | 0,25 | ОПК-1.1, ОПК -2.1 | ||
| | | | | | | |
| 5. ОЦЕНОЧНЫЕ МАТЕРИАЛЫ | ||||||
| | | | | | | |
| 5.1. Перечень компетенций | ||||||
| | | | | | | |
| Перечень компетенций, на освоение которых направлено изучение дисциплины «Дискретная математика», с указанием результатов их формирования в процессе освоения образовательной программы, представлен в п.3 настоящей рабочей программы | ||||||
| 5.2. Типовые контрольные вопросы и задания | ||||||