  
Паспорт программы дисциплины
1.1. Область применения программы
Рабочая программа дисциплины является частью образовательной программы высшего образования направления подготовки 10.03.01 «Информационная безопасность» (в соответствии с Учебным планом подготовки бакалавра по профессионально-образовательной программе направления 10.03.01 «Информационная безопасность», одобренного Ученым советом вуза 25.02.2014 г.протокол №7).
1.2 Место дисциплины в структуре образовательной программы
Дисциплина Б2.Б3 «Дискретная математика» относится к математическому и естественнонаучному циклу образовательной программы по направлению подготовки 10.03.01 «Информационная безопасность» базовой части.
1.3 Цели и задачи дисциплины – требования к результатам освоения дисциплины:
Цели изучения дисциплины: формирование математической компетентности, ознакомление обучающихся с основными понятиями, методами и языком дискретной математики, формирование навыков решения задач по дискретной математике, умений применять математические методы в решении прикладных задач.
Задачи изучения дисциплины: воспитание у обучающихся математической культуры, четкое осознание необходимости и важности математической подготовки для специалиста технического профиля, приобретение знаний по теории множеств, по математической логике, по теории графов и комбинаторике, изучить методы и алгоритмы решения прикладных задач.
Результаты освоения дисциплины:
Знать: основные понятия и законы теории множеств, основные понятия и законы комбинаторики, основные понятия и законы теории графов, основные понятия и законы математической логики.
Уметь: выполнять операции над множествами, распознавать основные комбинаторные конфигурации и вычислять их количество, определять основные свойства графа, исследовать его планарность, представлять его в виде матрицы, приводить функции логики к дизъюнктивной и конъюнктивной формам и строить их совершенные формы; определять полноту системы функций логики, описывать модель явления на языке исчисления предикатов.
Владеть: теорией множеств, булевой алгеброй, математической логикой, исчислением высказываний и предикатов, теорией графов и теории автоматов для решения различных задач, требующих применения вычислительных средств.
Дисциплина участвует в формировании компетенций ОК-9, ОК-12, ПК-1, ПК-20, ПК-23.
Формируемые компетенции
|
Осваиваемые
знания, умения, владения
|
Код
|
Наименование
|
Общекультурные компетенции (ОК)
|
ОК-9
|
Способность логически верно, аргументировано и ясно строить устную и письменную речь, публично представлять собственные и известные научные результаты, вести дискуссии
|
З Основные понятия и методы математической логики и теории алгоритмов
|
У Строить математические модели задач профессиональной области; осуществлять поиск научной информации и работу с реферативной, справочной, периодической и монографической литературой по различным областям дискретной математики
|
В Оновами теории множеств, булевой алгебры, математической логики, исчислении высказываний и предикатов, теории графов, навыками решения комбинаторных задач
|
ОК-12
|
Способность критически оценивать свои достоинства и недостатки, определять пути и выбрать средства развития достоинств и устранения недостатков
|
З Основные объекты и методы дискретной математики
|
У Применять методы дискретной математики для решения задач профессиональной деятельности с целью повышения математической грамотности как специалиста технического профиля
|
В Методологией дискретной математики для планирования и решения задач исследовательского характера
|
Профессиональные компетенции (ПК) по видам профессиональной деятельности
|
Общепрофессиональные компетенции
|
ПК-1
|
Способность использовать основные естественнонаучные законы, применять математический аппарат в профессиональной деятельности, выявлять сущность проблем, возникающих в ходе профессиональной деятельности
|
З Основные понятия и методы дискретной математики; основные методы решения задач профессиональной области с применением дискретных моделей
|
У Строить математические модели задач профессиональной области; применять стандартные методы дискретной математики к решению типовых задач
|
В Методологией дискретной математики для переработки информации и решения задач исследовательского характера
|
Экспериментально-исследовательская деятельность
|
ПК-20
|
Способность применять методы анализа изучаемых явлений, процессов и проектных решений
|
З Основные понятия и методы математической логики и теории алгоритмов, основные методы решения задач профессиональной области с применением дискретных моделей
|
У Строить математические модели задач профессиональной области; применять стандартные методы дискретной математики к решению типовых задач, осуществлять поиск научной информации и работу с реферативной, справочной, периодической и монографической литературой по различным областям дискретной математики
|
В Методологией дискретной математики для анализа изучаемых явлений, процессов и проектных решений
|
ПК-23
|
способностью принимать участие в проведении экспериментально-исследовательских работ системы защиты информации с учетом требований по обеспечению информационной безопасности
|
З Основные методы решения задач профессиональной области с применением дискретных моделей
|
У Применять стандартные методы дискретной математики к решению типовых задач; осуществлять поиск научной информации и работу с реферативной, справочной, периодической и монографической литературой по различным областям дискретной математики
|
В Методологией дискретной математики для анализа и переработки информации и решения задач исследовательского характера
|
1.4. Связь с другими дисциплинами Учебного плана
Перечень действующих и предшествующих дисциплин
|
Перечень последующих дисциплин, видов работ
|
Математический анализ
Алгебра и геометрия
Информатика
|
Теория вероятностей и математическая статистика
Сети и системы передачи информации
Технологии и методы программирования
Криптографические методы защиты информации
|
2.Содержание дисциплины, способы и методы учебной деятельности преподавателя
Методы обучения – система последовательных, взаимосвязанных действий, обеспечивающих усвоение содержания образования, развитие способностей студентов, овладение ими средствами самообразования и самообучения; обеспечивают цель обучения, способ усвоения и характер взаимодействия преподавателя и студента; направлены на приобретение знаний, формирование умений, навыков, их закрепление и контроль.
Монологический (изложение теоретического материала в форме монолога)
|
М
|
Показательный (изложение материала с приемами показа)
|
П
|
Диалогический (изложение материала в форме беседы с вопросами и ответами)
|
Д
|
Эвристический (частично поисковый) (под руководством преподавателя студенты рассуждают, решают возникающие вопросы, анализируют, обобщают, делают выводы и решают поставленную задачу)
|
Э
|
Проблемное изложение (преподаватель ставит проблему и раскрывает доказательно пути ее решения)
|
ПБ
|
Исследовательский (студенты самостоятельно добывают знания в процессе разрешения проблемы, сравнивая различные варианты ее решения)
|
И
|
Программированный (организация аудиторной и самостоятельной работы студентов осуществляется в индивидуальном темпе и под контролем специальных технических средств)
|
ПГ
|
Другой метод, используемый преподавателем (формируется самостоятельно), при этом в п.п. 2.1.-2.4. дается его наименование, необходимые пояснения
|
|
Приведенные в таблице сокращения обозначения педагогических методов используются составителем Рабочей программы для заполнения п.п. 2.1., 2.2. и 2.3. в столбце «Методы».
2.1.Аудиторные занятия (лекции, лабораторные, практические, семинарские)
Неделя
|
Кол. час
|
в том числе в интерактивной форме, час.
|
Вид занятия, модуль, тема и краткое содержание
|
Методы
|
Реализуемые компетенции
|
|
|
|
Очная форма обучения
|
|
|
|
|
|
Лекции
|
|
|
1-2
|
2
|
2
|
Модуль 1 «Множества, отношения и функции»
|
М, П
|
ПК-19, ПК-21
|
1-2
|
2
|
2
|
Тема 1.1 «Введение в дискретную математику. Множества»
Место дискретной математики в системе математического образования. Понятие множества. Способы задания множеств. Универсальное множество. Операции над множествами: пересечение, объединение, разность, дополнение. Диаграммы Венна. Прямое (декартово) произведение множеств. Основные тождества алгебры множеств. Счетное множество. Мощность множества. Эквивалентные множества. Мощность континуума. Понятие отношения. Бинарные отношения. Способы задания бинарных отношений, определенных на конечных множествах. Свойства бинарных отношений. Эквивалентность и порядок отношений. Операции над бинарными отношениями.
|
М, П
|
ПК-19, ПК-21
|
3-8
|
6
|
4
|
Модуль 2 «Основы теории графов и элементы комбинаторики.»
|
М, П,
Д
|
ПК-19,
ПК-21
|
3-4
|
2
|
2
|
Тема 2.1 «Понятия теории графов.»
Понятие графа. Ориентированные и неориентированные графы. Смежность. Инцидентность. Мультиграф.Петля. Степень вершины графа. Геометрическая реализация графа. Способы задания графов. Связь между графами и бинарными отношениями. Маршрут. Цепь. Цикл. Контур. Деревья и леса. Теорема об основных свойствах дерева.
|
М, П
|
ПК-19 ПК-21
|
5-6
|
2
|
|
Тема 2.2 «Планарность графов»
Планарный граф. Плоский граф. Внутренняя грань. Внешняя грань. Теорема Эйлера для связных плоских графов. Непланарные графы. Теорема о непланарности графов Понтрягина-Куратовского 1 и П типов.Теорема Понтрягина-Куратовского. Раскраска графов. Теорема о раскраске планарных графов в пять цветов.
|
М, П
|
ПК-19, ПК-21
|
7-8
|
2
|
2
|
Тема 2.3. «Элементы комбинаторики»
Комбинаторные задачи. Общие правила комбинаторики: правило суммы, правило произведения. Перестановки, перестановки с повторениями. Размещения с повторениями и без повторений. Сочетания с повторениями и без повторений.
|
М,П
|
ПК-19, ПК-21
|
9-18
|
10
|
2
|
Модуль 3 «Основы математической логики и теории алгоритмов»
|
М,Д,П
|
ПК-19,
ПК-21
|
9-10
|
2
|
|
Тема 3.1 «Высказывания и основные операции логики высказываний»
Понятие высказывания. Простые и составные высказывания. Основные логические связки (операции) логики высказываний: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Законы логики. Понятие логической формулы. Эквивалентные формулы. Стандартный метод установления эквивалентности двух формул.Основные зависимости между операциями.
|
М,Д
|
ПК-19,
ПК-21
|
11-12
|
2
|
|
Тема 3.2 «Дизъюнктивные и конъюнктивные нормальные формы».
Булева формула. Схема упрощения формул логики с помощью равносильных преобразований. Дизъюнктивная нормальная форма (ДНФ) и схема ее построения. Конъюнктивная нормальная форма (КНФ) и схема ее построения. Совершенные дизъюнктивная и конъюнктивная нормальные формы (СДНФ и СКНФ). Теоремы о СДНФ, СКНФ.
|
М,Д
|
ПК-19,
ПК-21
|
13-14
|
2
|
-
|
Тема 3.3 «Полнота систем булевых функций. Многочлены Жегалкина. Двойственные функции»
Булевы функции. Полные системы. Примеры полных систем ю Многочлены Жегалкина. Теорема Жегалкина о представлении функции алгебры логики полиномом Жегалкина. Понятие канонического многочлена Жегалкина. Понятие функции, двойственной к данной функции логики. Принцип двойственности.
|
М,Д
|
ПК-19,
ПК-21
|
15-16
|
2
|
2
|
Тема 3.7 «Логика предикатов»
Понятие о многоместном предикате. Логические операции над предикатами. Равносильность в алгебре предикатов. Булева алгебра предикатов. Операции, уменьшающие местность предиката. Кванторы. Основные равносильности, содержащие кванторы.
|
М,П,Д
|
ПК-19,
ПК-21
|
17-18
|
2
|
-
|
Тема 3.8 «Исчисление предикатов. Разновидности алгоритмических систем»
Формулы исчисления предикатов. Замена переменной в формулах. Некоторые теоремы исчисления предикатов. Эквивалентные формулы. Нормальные формы.
Классификация алгоритмов по временной сложности. Пути получения временных оценок алгоритмов. Машина Тьюринга: описание и примеры. Алгоритмическая система Колмогорова-Успенского. Логические схемы алгоритмов А.А.Ляпунова.
|
М,Д
|
ПК-19,
ПК-21
|
Очная форма обучения
|
Практические занятия
|
1-2
|
4
|
4
|
Модуль 1 «Множества, отношения и функции»
|
М, П
|
ПК-19,
ПК-21
|
1
|
2
|
2
|
Тема «Элементы теории множеств.»
Способы задания множеств: перечисление элементов, описательный, с помощью характеристического свойства. Операции пересечения, объединения множеств, их свойства. Нахождение разности, дополнения множеств.
|
М, Д
|
ПК-19,
ПК-21
|
2
|
2
|
2
|
Тема «Отношения.»
Нахождение прямого (декартова) произведения множеств. Бинарные отношения. Способы задания бинарных отношений, определенных на конечных множествах: списком (перечислением) пар, матрицей. Свойства бинарных отношений. Операции над бинарными отношениями: объединение, пересечение, разность, дополнение, обратное отношение, композиция.
|
И, Д
|
ПК-19,
ПК-21
|
3-8
|
12
|
6
|
Модуль 2 «Основы теории графов и элементы комбинаторики»
|
Д, И, Э
|
ПК-19, ПК-21
|
3
|
2
|
-
|
Тема «Основные понятия теории графов.»
Ориентированные и неориентированные графы.Задание графов через множества вершин и ребер. Нахождение степеней вершин графов. Построение матриц смежности и инцидентности графов.Построение графов по заданным матрицам смежности и инцидентности.
|
Д, И, Э
|
ПК-19, ПК-21
|
4
|
2
|
2
|
Тема «Графы и бинарные отношения.»
Решение задач на нахождение связи между графами и бинарными отношениями. Нахождение метрических характеристик графов.
|
Д, И, Э
|
ПК-19, ПК-21
|
5
|
2
|
2
|
Тема «Маршруты, пути ,цепи, цикл».
Учебная деловая игра по теме: «Нахождение критического пути». Цель игры – обучение моделированию рассматриваемого процесса. Постановка задачи: Требуется проанализировать проект с точки зрения минимальных временных затрат на его выполнение. Группа делится
на три команды, каждая из которых получаем индивидуальное задание.
|
Д, И, Э
|
ПК-19, ПК-21
|
6
|
2
|
2
|
Тема «Деревья и леса»
Деловая игра по теме: «Построения дерева решений». Цель игры- обучение моделированию рассматриваемого процесса.
|
Д, И, Э
|
ПК-19, ПК-21
|
7
|
2
|
-
|
Тема «Элементы комбинаторики»
Распознавание основных комбинаторных конфигураций. Решение задач с использованием комбинаторики.
|
Д, И, Э
|
ПК-19, ПК-21
|
8
|
2
|
-
|
Контрольная работа по модулю 2 по темам «Графы: разные способы задания графов, нахождение различных характеристик графов», «Элементы комбинаторики».
|
Д, И, Э
|
ПК-19, ПК-21
|
9-18
|
20
|
-
|
Модуль 3 «Основы математической логики и теории алгоритмов»
|
Д, И, Э
|
ПК-19, ПК-21
|
9
|
2
|
-
|
Тема «Высказывания и основные операции логики высказываний.»
Основные логические связки (операции) логики высказываний: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция. Законы логики. Представление логическими формулами данные высказывания.
|
Д, И, Э
|
ПК-19, ПК-21
|
10
|
2
|
-
|
Тема «Основные схемы логически правильных рассуждений.»
Правило заключения, правило отрицания, правила утверждения-отрицания, правила отрицания-утверждения, правило транзитивности, закон противоречия, правило контрапозиции правило сложной контрапозиции, правило сечения.
|
Д, И, Э
|
ПК-19, ПК-21
|
11
|
2
|
-
|
Тема «Функции алгебры логики.»
Составление таблиц истинности данной функции алгебры логики. Доказательство эквивалентности заданных функций алгебры логики стандартным методом. Упрощение формул логики с помощью равносильных преобразований.
|
Д, И, Э
|
ПК-19, ПК-21
|
12
|
2
|
-
|
Тема «Совершенная дизъюнктивная и конъюнктивная нормальная форма»
Построение совершенной дизъюнктивной и конъюнктивной нормальной формы с помощью равносильных преобразований и по таблице истинности.
|
Д, И, Э
|
ПК-19, ПК-21
|
13
|
2
|
-
|
Тема «Алгебра Жегалкина»
Эффективное упрощение СДНФ методом Блэйка-Порецкого. Определение многочлена Жегалкина. Представление основных логических операций в виде многочлена Жегалкина. Представление функций алгебры логики в виде многочлена Жегалкина.
|
Д, И, Э
|
ПК-19, ПК-21
|
14
|
2
|
-
|
Тема «Логика предикатов»
Для данного предиката рассмотреть различные варианты квантификации его переменных и определить истинность получаемых выражений для разных случаев интерпретации области определения предиката. Соответствие между предикатами, отношениями и функциями.
|
Д, И, Э
|
ПК-19, ПК-21
|
15
|
2
|
-
|
Тема «Предикаты. Кванторы.»
Правила вывода. Вывод и доказательство истинности формул в исчислении предикатов.Приведение к префиксной нормальной форме данную предикатную форму.
|
Д, И, Э
|
ПК-19, ПК-21
|
16
|
2
|
-
|
Тема «Основы теории алгоритмов»
Операции над алфавитами. Кодирование, декодирование. Примеры кодирования. Построение граф-схем алгоритмов. Определение функций, заданных по схемам.
|
Д, И, Э
|
ПК-19, ПК-21
|
17
|
2
|
-
|
Тема «Нормальные алгоритмы. Рекурсивные функции»
Понятие нормальных алгоритмов. Композиция алгоритмов. Построение блок-схем обобщенных нормальных алгоритмов. Построение рекурсивных схем для заданий функций.
|
Д, И, Э
|
ПК-19, ПК-21
|
18
|
2
|
-
|
Контрольная работа по модулю 3 по темам: «Построение СДНФ, СКНФ различными способами», «Логика предикатов».
|
Д, И, Э
|
ПК-19, ПК-21
|
|
