2

Лист – вкладка рабочей программы учебной дисциплины

Дискретная математика, ТО.Ф.ОПД.04, федеральный

название дисциплины, цикл, компонент

Список основной учебной литературы

Соответствие ГОС

(для федеральных

Внесение, дисциплин) или Количество продление или соответствия экземпляров в исключение / Год требованиям ООП библиотеке на Дата Наименование, гриф Автор Подпись отв. издания (для региональных и момент за метод вузовских) - указание переутвержден работу на недостаточно ия программы отраженные в учебнике разделы Спирина, М. С. Дискретная математика [Текст] : учебник для студ. учреждений М.С.

Продление сред. проф. образования / М. С. Спирина, П. Спирина, Соотвествует 31.08.2011 2010 А. Спирин. - 6-е изд., стер. - М. : Академия, П.А. Спирин 2010. - 368 с. - (Среднее профессиональное образование).

Канцедал, С. А. Дискретная математика:

Продление учебное пособие / С.А. Канцедал. - М.: С.А. Соотвествует 31.08.2011 2007 ФОРУМ: ИНФРА-М, 2007. - 224 с. Канцедал 1 Пояснительная записка Рабочая программа учебной дисциплины «Дискретная математика» предназначена для реализации государственных требований к минимуму содержания и уровню подготовки выпускников специальности 230103.51 «Автоматизированные системы обработки информации и управления (по отраслям)».

Аппарат дискретной математики необходим при создании и эксплуатации современных ЭВМ, средств передачи и обработки информации, автоматизированных систем управления и проектирования; поэтому знание основ данной дисциплины абсолютно необходимо для современного специалиста в области информатики и вычислительной техники. Учебная дисциплина «Дискретная математика» является фундаментом математической кибернетики.

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

Материал дисциплины «Дискретная математика» используется при изучении дисциплин: «Основы алгоритмизации и программирования», «Архитектура ЭВМ и вычислительных систем», «Базы данных», «Теория вероятностей и математическая статистика», «Пакеты прикладных программ».

Цель преподавания дисциплины «Дискретная математика» при подготовке по специальности 230103.51 «Автоматизированные системы обработки информации и управления (по отраслям)» – изучение свойств объектов конечного характера, различных аспектов построения математических моделей, возникающих при исследовании информационных процессов и процессов управления в различных областях практической деятельности.

В соответствии с государственными требованиями после изучения дисциплины студент должен:

иметь представление:

о роли общепрофессиональных знаний в профессиональной деятельности;

о значении и областях применения дискретной математики;

знать:

основные понятия и приемы дискретной математики;

аппарат алгебры логики и теорию булевых функций;

основы теории множеств;

логику предикатов и бинарных отношений;

теорию отображений и алгебру подстановок;

основы алгебры вычетов;

простейшие криптографические шифры;

метод математической индукции;

методику генерирования основных комбинаторных объектов;

основы теории графов и теории автоматов;

уметь:

применять законы и методы дискретной математики;

строить таблицы истинности для формул логики и упрощать формулы логики;

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

выполнять операции над множествами, применять аппарат теории множеств для решения задач;

выполнять операции над предикатами, записывать области истинности предикатов, формализовывать предложения с помощью логики предикатов;

исследовать бинарные отношения на заданные свойства;

выполнять операции над отображениями и подстановками, выделять структурные особенности отображений и подстановок;

выполнять операции в алгебре вычетов;

применять простейшие криптографические шифры для шифрования текстов;

доказывать утверждения с помощью метода математической индукции;

генерировать основные комбинаторные объекты;

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

строить автоматы с заданными свойствами.

На изучение дисциплины «Дискретная математика» отводится 111 часов в течение четвертого семестра, из них 70 часов теоретического обучения в форме лекций и 20 часов практических занятий. Кроме того, запланирована самостоятельная работа студентов в объеме 21 часа.

При чтении лекций предусмотрено применение технических средств обучения (проектор, экран) и компьютерной техники.

В конце семестра по окончании изучения дисциплины студенты сдают экзамен в устной форме.

2 Учебно-тематический план Введение теоретико-множественные операции и их связь с логическими операциями Тема 1.1 Основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями Раздел 2 Формулы логики функции в совершенных нормальных формах Тема 3.1 Понятие функции алгебры логики Тема 3.2 Операция двоичного сложения.

Многочлен Жегалкина Тема 3.3 Основные классы функций. Полнота множества функций.

Теорема Поста предикатов. Бинарные отношения и их виды Тема 4.1 Логика предикатов.

Бинарные отношения и их подстановок Тема 5.1 Элементы теории отображений и алгебры подстановок Тема 6.1 Основы алгебры простейшим криптографическим Тема 7.1 Приложение алгебры вычетов к простейшим криптографическим Тема 8.1 Метод математической индукции комбинаторных объектов Тема 9.1 Алгоритмическое перечисление основных комбинаторных объектов Тема 10.1 Эйлеровы и гамильтоновы графы, плоские графы, деревья Тема 10.2 Ориентированные графы. Бинарные деревья Раздел 11 Элементы теории автоматов Тема 11.1 Элементы теории автоматов 3 Содержание учебной дисциплины иметь представление:

о роли и месте знаний по дисциплине в профессиональной деятельности;

об основных задачах и областях применения дискретной математики.

Предмет дискретной математики, его основные задачи и области применения.

Раздел 1 Основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями Тема 1.1 Основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями Студент должен:

понятие подмножества, формулу количества подмножеств конечного множества;

операции над множествами (объединение, пересечение, дополнение, разность, декартово произведение, декартова степень) и их свойства;

формулу количества элементов в объединении нескольких (двух, трех) конечных множеств;

операциями;

методику проверки теоретико-множественных соотношений с помощью формул логики;

применять теоретико-множественные диаграммы;

выполнять операции над множествами;

решать задачи на подсчет количества элементов с использованием формулы количества элементов в объединении нескольких конечных множеств;

проверять теоретико-множественные соотношения с помощью формул логики.

Понятие множества. Конечные и бесконечные множества, пустое множество.

Подмножество; количество подмножеств конечного множества. Теоретикомножественные диаграммы. Операции над множествами (объединение, пересечение, дополнение, теоретико-множественная разность) и их свойства. Формула количества элементов в объединении двух конечных множеств:A B = A + B – A B;

соответствующая формула для трех множеств. Декартово произведение множеств.

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

Практические занятия Раздел 2 Формулы логики Тема 2.1 Логические операции. Формулы логики Студент должен:

основные логические операции;

понятие формулы логики, понятие таблицы истинности формулы логики и методику ее построения, понятие тождественно-истинной формулы;

понятие дизъюнктивной нормальной формы (ДНФ), упрощенную методику построения таблицы истинности для ДНФ;

понятие конъюнктивной нормальной формы (КНФ);

выполнять логические операции;

составлять таблицы истинности формул логики;

строить таблицы истинности для ДНФ.

Понятие высказывания. Основные логические операции (дизъюнкция, произведение (конъюнкция), импликация, эквиваленция, отрицание). Понятие формулы логики. Таблица истинности и методика ее построения. Тождественно-истинные формулы. Понятие элементарного произведения; понятие дизъюнктивной нормальной формы (ДНФ). Методика построения таблицы истинности для ДНФ упрощенным методом. Понятие элементарной дизъюнкции, понятие конъюнктивной нормальной формы (КНФ).

Практическое занятие Тема 2.2 Законы алгебры логики Представление функции в совершенных нормальных формах.

Студент должен:

понятие равносильности двух формул логики;

методику упрощения формул логики с помощью равносильных преобразований;

упрощать формулу логики с помощью равносильных преобразований.

Равносильные формулы. Законы логики. Методика упрощения формул логики с помощью равносильных преобразований.

Практическое занятие Раздел 3 Булевы функции Тема 3.1 Понятие функции алгебры логики Студент должен:

понятие булева вектора, понятия соседних и противоположных булевых векторов;

понятие единичного n-мерного куба;

понятие булевой функции (функции алгебры логики) и способы ее задания;

понятие совершенной ДНФ, методику представления булевой функции в виде совершенной ДНФ;

понятие совершенной КНФ, методику представления булевой функции в виде совершенной КНФ;

понятие минимальной ДНФ, методику представления булевой функции (N 3) в виде минимальной ДНФ графическим методом;

изображать единичный n -мерный куб (с разметкой вершин булевыми векторами) в случаях n = 1, 2, 3;

представлять булеву функцию в виде совершенной ДНФ;

представлять булеву функцию в виде совершенной КНФ;

представлять булеву функцию (n 3) в виде минимальной ДНФ графическим методом.

Понятие булева вектора (двоичного вектора). Соседние векторы.

Противоположные векторы. Единичный n -мерный куб.

Понятие булевой функции (функции алгебры логики). Способы задания булевой функции. Проблема представления булевой функции в виде формулы логики.

Понятие совершенной ДНФ. Методика представления булевой функции в виде совершенной ДНФ.

Понятие совершенной КНФ. Методика представления булевой функции в виде совершенной КНФ.

Понятие минимальной ДНФ. Соответствие между гранями единичного n -мерного куба и элементарными произведениями. Методика представления булевой функции (n 3) в виде минимальной ДНФ графическим методом.

Практическое занятие Тема 3.2 Операция двоичного сложения. Многочлен Жегалкина операцию двоичного сложения и ее свойства;

методику представления булевой функции в виде многочлена Жегалкина.

представлять булеву функцию в виде многочлена Жегалкина.

Операция двоичного сложения и ее свойства. Многочлен Жегалкина. Методика представления булевой функции в виде многочлена Жегалкина.

Практическое занятие Тема 3.3 Основные классы функций. Полнота множества функций. Теорема Поста понятие выражения одних булевых функций через другие;

понятие полноты множества функций;

понятие замкнутого класса, важнейшие замкнутые классы: Т0, Т1, S, L, М (определения этих классов, методику проверки булевой функции на принадлежность к этим классам);

понятие шефферовской функции; условие того, что функция является шефферовской; функции Шеффера и Пирса;

проверять булеву функцию на принадлежность к классам Т0, Т1, S, L, М;

проверять множество булевых функций на полноту (с помощью теоремы Поста);

проверять, является ли функция шефферовской.

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

Замыкание множества функций. Понятие замкнутого класса функций. Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), M (класс монотонных функций). Теорема Поста. Шефферовские функции.

Функция Шеффера и функция Пирса как простейшие шефферовские функции.

Практическое занятие Раздел 4 Логика предикатов. Бинарные отношения и их виды Тема 4.1 Логика предикатов. Бинарные отношения и их виды Студент должен:

понятие предиката, понятия области определения и области истинности предиката;

операции над предикатами (обычные логические и кванторные);

понятие предикатной формулы, понятия свободной переменной и связанной переменной;

методику построения отрицаний к предикатам, содержащим кванторные операции;

понятия рефлексивного бинарного отношения, симметричного бинарного отношения, транзитивного бинарного отношения;

понятие отношения эквивалентности, теорему о разбиении множества на классы эквивалентности;

записывать область истинности предиката;

определять логическое значение для высказываний типов x P(x), x P(x), x y P(x, y), x y P(x, y);

выделять в предикатной формуле свободные переменные и связанные переменные;

строить отрицания к предикатам, содержащим кванторные операции;

формализовывать предложения с помощью логики предикатов.

Понятие предиката. Область определения и область истинности предиката.

Обычные логические операции над предикатами. Кванторные операции над предикатами.

Понятие предикатной формулы; свободные и связанные переменные. Построение отрицаний к предикатам, содержащим кванторные операции. Формализация предложений с помощью логики предикатов.

Понятие бинарного отношения; примеры бинарных отношений. Диаграмма бинарного отношения. Рефлексивные бинарные отношения. Симметричные бинарные отношения. Транзитивные бинарные отношения. Отношение эквивалентности; теорема о разбиении множества на классы эквивалентности.

Практическое занятие Раздел 5 Элементы теории отображений и алгебры подстановок Тема 5.1 Элементы теории отображений и алгебры подстановок Студент должен:

понятие взаимооднозначного (биективного) отображения;

операцию композиции отображений и ее свойства;

понятие обратного отображения, условие обратимости отображения;

понятие композиционной степени отображения;

структурные особенности диаграммы внутреннего отображения, заданного на конечном множестве;

теорему о зацикливании степенной последовательности элемента;

теорему о разбиении взаимооднозначного внутреннего отображения, заданного на конечном множестве, на отдельные независимые циклы;

понятие подстановки, формулу количества подстановок;

циклическое разложение подстановки;

операции над подстановками;

методику решения простейших уравнений в алгебре подстановок;

понятия четной подстановки и нечетной подстановки, свойства четных и нечетных подстановок.

Понятие отображения. Взаимооднозначные (биективные) отображения. Операция композиции отображений и ее свойства. Обратное отображение. Композиционная степень отображения. Диаграмма внутреннего отображения, заданного на конечном множестве;

циклы. Степенная последовательность элемента (a, f(a), f2(a),…,fn(a),…).

Теорема о зацикливании степенной последовательности элемента. Теорема о разбиении взаимооднозначного внутреннего отображения, заданного на конечном множестве, на отдельные независимые циклы.

Понятие подстановки. Формула количества подстановок.

Циклическое разложение подстановки. Произведение подстановок. Обратная подстановка. Степень подстановки. Методика решения простейших уравнений (ax=b, xa=b, axb=c) в алгебре подстановок. Чтные и нечетные подстановки, свойства четных и нечетных подстановок.

Раздел 6 Основы алгебры вычетов Тема 6.1 Основы алгебры вычетов Студент должен:

операции над вычетами и их свойства;

понятие обратимого вычета, критерий обратимости вычета;

определение медианы НСВ и методику ее нахождения.

Понятие вычета по модулю N; система вычетов по модулю N. Операции над вычетами (сложение, вычитание, умножение) и их свойства. Обратимые вычеты; критерий обратимости вычета; система обратимых вычетов по модулю N.

Раздел 7 Приложение алгебры вычетов к простейшим криптографическим шифрам Тема 7.1 Приложение алгебры вычетов к простейшим криптографическим шифрам Студент должен:

принцип шифров замены; шифры Цезаря и Виженера;

принцип перестановочных шифров;

применять простейшие шифры замены (в частности, шифр Цезаря и шифр Виженера) для шифрования текста;

применять перестановочные шифры для шифрования текста;

осуществлять дешифровку шифротекста, зашифрованного заданным шифром замены или заданным перестановочным шифром.

Проблема криптографической защиты информации; понятие шифрования. Шифры замены. Шифр Цезаря и шифр Виженера как частные случаи шифров замены.

Перестановочные шифры.

Практическое занятие Раздел 8 Метод математической индукции Тема 8.1 Метод математической индукции Студент должен:

принцип метода математической индукции;

некоторые разновидности (модификации) метода математической индукции.

Принцип метода математической индукции. Некоторые разновидности (модификации) метода математической индукции.

Раздел 9 Алгоритмическое перечисление основных комбинаторных объектов Тема 9.1 Алгоритмическое перечисление основных комбинаторных объектов Студент должен:

понятие алгоритмического перечисления (генерирования) элементов конечного множества;

принцип генерирования двоичных слов заданной длины;

принцип генерирования элементов декартова произведения множеств;

принцип генерирования перестановок заданной длины;

принцип генерирования k-элементных подмножеств данного множества;

принцип генерирования всех подмножеств данного множества;

генерировать двоичные слова заданной длины;

генерировать элементы декартова произведения множеств;

генерировать перестановки заданной длины;

генерировать k -элементные подмножества заданного множества;

генерировать все подмножества заданного множества.

Понятие алгоритмического перечисления (генерирования) элементов конечного множества. Генерирование двоичных слов заданной длины. Генерирование элементов декартова произведения множеств. Генерирование перестановок заданной длины.

Генерирование К-элементных подмножеств данного множества. Генерирование всех подмножеств данного множества.

Практическое занятие Раздел 10 Основы теории графов. Характеристики графов Тема 10.1 Эйлеровы и гамильтоновы графы, плоские графы, деревья понятие неориентированного графа и основные определения, связанные с ним;

теорему о сумме степеней вершин графа;

формулу количества ребер в полном графе;

методику выделения компонент связности в графе;

понятие моста и разделяющей вершины;

понятие расстояния между вершинами в графе и методику его нахождения;

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

понятие двудольного графа, методику проверки графа на двудольность, понятие полного двудольного графа;

понятие изоморфности двух графов, методику проверки пары графов на изоморфность;

понятие эйлерова графа, теорему Эйлера, методику нахождения эйлерова цикла в эйлеровом графе;

понятие гамильтонова графа;

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

понятие дерева, свойства деревьев;

кодирование Пруфера для деревьев с пронумерованными вершинами;

записывать матрицу смежности для графа;

находить количество рбер в графе (с помощью теоремы о сумме степеней вершин графа);

выделять компоненты связности в графе;

определять, является ли данное ребро мостом или является ли данная вершина разделяющей;

находить расстояние между двумя вершинами в графе;

находить эксцентриситеты вершин, радиус и диаметр графа;

проверять, является ли данный граф двудольным;

проверять, являются ли два данных графа изоморфными (в простейших случаях);

проверять, является ли данный граф эйлеровым; находить эйлеров цикл в эйлеровом графе;

проверять, является ли данный граф гамильтоновым (в простейших случаях);

проверять, является ли данный граф плоским (в простейших случаях);

записывать для дерева с пронумерованными вершинами его код Пруфера;

восстанавливать по коду Пруфера дерево с пронумерованными вершинами.

Понятие неориентированного графа. Способы задания графа. Матрица смежности.

Путь в графе. Цикл в графе. Связный граф. Компоненты связности графа. Степень вершины. Теорема о сумме степеней вершин графа. Полный граф; формула количества рбер в полном графе.

Алгоритм фронта волны в графе. Методика выделения компонент связности в графе. Мосты и разделяющие вершины (точки сочленения). Расстояние между вершинами в графе: определение, свойства, методика нахождения. Эксцентриситет вершины. Радиус и диаметр графа. Центральные вершины.

Двудольные графы. Методика проверки графа на двудольность. Полный двудольный граф. Изоморфные графы. Методика проверки пары графов на изоморфность.

Эйлеровы графы. Теорема Эйлера (критерий эйлеровости графа). Методика нахождения эйлерова цикла в эйлеровом графе. Гамильтоновы графы. Плоские графы.

Грани плоской укладки плоского графа. Соотношения между количествами вершин, рбер и граней в плоском графе. Примеры неплоских графов. Деревья и их свойства.

Кодирование Пруфера для деревьев с пронумерованными вершинами.

Практическое занятие Тема 10.2 Ориентированные графы. Бинарные деревья Студент должен понятие ориентированного графа (орграфа) и основные определения, связанные с ним;

понятие достижимости вершин в орграфе, методику записи матрицы достижимости орграфа;

понятие эквивалентности вершин в орграфе, методику построения диаграммы Герца для орграфа, понятие сильносвязного орграфа;

понятие бесконтурного орграфа, теорему о существовании источника и стока в бесконтурном орграфе;

понятие эйлерова орграфа, критерий эйлеровости орграфа;

понятие гамильтонова орграфа;

понятие ориентированного дерева;

понятие бинарного дерева, понятие дисбаланса вершины в бинарном дереве;

кодирование бинарных деревьев;

понятие бинарного дерева сортировки, методику его построения, использование его для организации хранения и поиска информации;

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

находить множество достижимости вершины в орграфе, записывать матрицу достижимости орграфа;

выделять классы эквивалентных вершин в орграфе, строить для орграфа его диаграмму Герца;

проверять, является ли данный орграф эйлеровым;

проверять, является ли данный орграф гамильтоновым (в простейших случаях);

находить дисбаланс вершины в бинарном дереве;

записывать код бинарного дерева;

по коду восстанавливать бинарное дерево;

строить бинарное дерево сортировки для заданной последовательности поступающих элементов.

Понятие ориентированного графа (орграфа). Способы задания орграфа. Матрица смежности для орграфа. Степень входа и степень выхода вершины. Источник. Сток.

Ориентированный путь. Ориентированный цикл (контур). Понятие достижимости одной вершины из другой вершины в орграфе. Множество достижимости вершины. Матрица достижимости. Эквивалентность (взаимодостижимость) вершин в орграфе. Классы эквивалентных вершин. Диаграмма Герца.

Сильносвязный орграф. Бесконтурные орграфы. Теорема о существовании источника и стока в бесконтурном орграфе. Эйлеровы орграфы. Критерий эйлеровости орграфа. Гамильтоновы орграфы. Понятие ориентированного дерева. Понятие бинарного дерева. Дисбаланс вершины в бинарном дереве. Кодирование бинарных деревьев.

Понятие бинарного дерева сортировки, методика его построения для заданной последовательности поступающих элементов, использование его для организации хранения и поиска информации.

Практическое занятие Раздел 11 Элементы теории автоматов Тема 11.1 Элементы теории автоматов Студент должен:

базовые множества и принцип работы автомата, диаграмму автомата;

словарную и финальную функции автомата;

понятие правильного автомата, упрощнный вид диаграммы для правильного автомата;

понятие автомата, распознающего свойство слова;

по таблице автомата строить его диаграмму, по диаграмме автомата записывать его таблицу;

для заданного автомата по заданному входному слову записывать соответствующее выходное слово;

строить автомат, распознающий заданное свойство слова (для простейших случаев свойства слова).

Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний. Таблица автомата. Принцип работы автомата. Диаграмма автомата. Словарная функция автомата. Финальная функция автомата. Правильный автомат (автомат Мура).

Упрощнный вид диаграммы для правильных автоматов. Автомат, распознающий свойство слова, и его построение.

Практическое занятие № Наименование и Номер и содержание практического занятия Кол-во понятия теории Решение задач на выполнение теоретикомножеств, теоретико- множественных операций. Решение задач на множественные подсчет количества подмножеств конечного операции и их связь с множества; нахождение декартова логическими произведения. Решение задач на подсчет операциями количества элементов с использованием Тема 2.1 Логические Практическое занятие операции. Формулы Решение задач на выполнение логических Тема 2.2 Законы Практическое занятие алгебры логики Упрощение формул логики с помощью равноПредставление сильных преобразований.

совершенных нормальных формах Тема 3.1 Понятие Практическое занятие функции алгебры Представление булевой функции в виде Тема 3.2 Операция Практическое занятие двоичного сложения. Представление булевой функции в виде Жегалкина.

Тема 3.3 Основные Практическое занятие классы функций. Проверка булевой функции на принадлежность Полнота множества к классам Т0, Т1, S, L, M. Проверка множества функций. Теорема булевых функций на полноту.

Тема 4.1 Логика Практическое занятие предикатов. Определение логического значения для Бинарные отношения Тема 7.1 Приложение Практическое занятие алгебры вычетов к Шифрование текста с помощью шифра замены простейшим или перестановочного шифра; дешифровка криптографическим шифротекста, зашифрованного заданным Алгоритмическое Генерирование комбинаторных объектов основных комбинаторных объектов Тема 10.1 Эйлеровы и Практическое занятие гамильтоновы графы, Нахождение матрицы смежности для плоские графы, неориентированного графа; нахождение Ориентированные Нахождение матрицы смежности и графы. Бинарные достижимости для ориентированного графа;

Тема 11.1 Элементы Практическое занятие теории автоматов Построение автоматов, распознающих заданные № Наименование и Содержание самостоятельной Формы контроля Кол-во понятия теории Операции над множествами теоретико- дополнение, теоретикомножественные множественная разность) и их операции и их связь свойства.

с логическими операциями Тема 2.2 Законы Выполнение индивидуального Проверка Представление Приведение данной формулы к задания совершенных нормальных функции алгебры Понятие булевой функции Тема 3.2 Операция Выполнение индивидуального Проверка Многочлен функции в виде многочлена Тема 5.1 Элементы Выполнение индивидуального Проверка Тема 6.1 Основы Выполнение индивидуального Проверка Приложение Проблема криптографической алгебры вычетов к защиты информации; понятие простейшим шифрования. Шифры замены.

криптографическим Перестановочные шифры.

шифрам Тема 10.1 Выполнение индивидуального Проверка гамильтоновы Записать матрицу смежности задания графы, плоские для графа.

графы, деревья Ориентированные Понятие бинарного дерева.

графы. Бинарные Кодирование бинарных деревья деревьев. Понятие бинарного автоматов По таблице автомата построить задания 4 Учебно-методическое обеспечение дисциплины 4.1 Основная литература 1. Канцедал, С. А. Дискретная математика: учебное пособие / С.А. Канцедал. - М.:

ФОРУМ: ИНФРА-М, 2007. - 224 с.

2. Спирина, М. С. Дискретная математика [Текст] : учебник для студ. учреждений сред. проф. образования / М. С. Спирина, П. А. Спирин. - 6-е изд., стер. - М. : Академия, 2010. - 368 с. - (Среднее профессиональное образование).

3. Знаткова К.И. Дискретная математика: Методические указания по подготовке и проведению практических и самостоятельных работ по дисциплине «Дискретная математика» для студентов специальности 230103.51 Автоматизированные системы обработки информации и управления (по отраслям) / Сост. Знаткова К.И. - Новокузнецк:

Новокузнецкий институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Кемеровский государственный университет», 2011. - 45 с.

4.2 Дополнительная литература 1.Выгодский, М. Я. Справочник по высшей математике [Текст] : справочник / М.

Я. Выгодский. - изд. 14-е. - М. : Джангар [и др.], 2000. - 863 с. - ISBN 5-7102-0197-9.

2. Акимов О.Е. Дискретная математика: Логика, группы, графы : Учебник для вузов. - 2-е изд., доп. - М. : Лаборатория Базовых Знаний, 2001. - 376с. - (Технический университет). - ISBN 5-93208-025-6.

3. Новиков, Ф. А. Дискретная математика для программистов [Текст] : учебное пособие для вузов. - СПб. : Питер, 2003. - 304 с. - (Учебник для вузов). - Гриф МО "Допущено". - ISBN 5-94723-355-Х.

4.3 Ресурсы Internet 1. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= Микони, С. В. Дискретная математика для бакалавра: множества, отношения, функции, графы [Электронный ресурс]: Учебное пособие / С. В. Микони. – СПб: Лань, 1-е издание, 2012.-192 с.

2. http://e.lanbook.com/books/element.php?pl1_cid=25&pl1_id= Шевелев, Ю.П. Дискретная математика [Электронный ресурс]: Учебное пособие / Ю.П. Шевелев. – СПб: Лань, 2008.-592 с.

4.4 Материально-техническое обеспечение дисциплины Кабинет математических дисциплин:

комплект малых вычислительных средств (калькуляторы);

методические указания по математике;

комплект классных инструментов: угольник, транспортир, линейка, циркуль;

комплект пособий в оформлении кабинета (математические таблицы; портреты математиков).

5 Формы текущего, промежуточного и рубежного контроля 5.1 Вопросы к экзамену Понятие множества, способы задания множеств, диаграммы Эйлера-Венна.

Конечные и бесконечные множества, пустое множество.

Подмножество; количество подмножеств конечного множества.

Операции над множествами и их свойства.

Мощность объединения множеств.

Декартово произведение множеств.

Классификация комбинаторных задач.

Понятие высказывания. Основные логические операции.

Таблица истинности и методика е построения.

Классификация формул логики. Тавтологии.

Понятие элементарной конъюнкции и дизъюнкции.

Понятие дизъюнктивной нормальной формы (ДНФ) и конъюнктивной нормальной формы (КНФ). Алгоритм приведения формулы к ДНФ.

Понятие булева вектора. Соседние векторы. Единичный n-мерный куб.

Булева функция и способы е задания.

Понятие совершенной дизъюнктивной нормальной формы (СДНФ) и совершенной конъюнктивной нормальной формы (СКНФ).

Методика представления булевой функции в виде СДНФ и СКНФ.

Минимизация булевых функций.

Понятие суперпозиции булевых функций.

Операция двоичного сложения. Многочлен Жегалкина.

Понятие замкнутого класса функций. Важнейшие замкнутые классы: класс функций, сохраняющих константу 0; класс функций, сохраняющих константу 1; класс линейных функций; класс самодвойственных функций; класс монотонных функций.

Функционально полные системы. Теорема Поста.

Понятие предиката. Область определения и область истинности предиката.

Обычные логические операции над предикатами.

Кванторные операции над предикатами.

Понятие предикатной формулы. Свободные и связанные переменные.

Построение отрицаний к предикатам, содержащим кванторные операции.

Понятие бинарного отношения. Примеры бинарных отношений.

Рефлексивные, симметричные и транзитивные бинарные отношения.

Отношение эквивалентности. Теорема о разбиении множества на классы эквивалентности.

Понятие отображения. Виды отображений.

Операция композиции отображений. Обратное отображение.

Понятие вычета и системы вычетов по модулю m.

Операции над вычетами и их свойства.

Проблема криптографической защиты информации.

Шифры замены. Шифр Цезаря и шифр Виженера как частные случаи шифров замены.

Принцип метода математической индукции.

Понятие алгоритмического перечисления (генерирования) элементов конечного множества.

Генерирование двоичных слов заданной длины.

Генерирование элементов декартова произведения множеств.

Генерирование перестановок заданной длины.

Генерирование К-элементных подмножеств данного множества.

Генерирование всех подмножеств данного множества.

Основные понятия теории автоматов: входной алфавит, выходной алфавит, множества состояний.

Правильный автомат (автомат Мура).

Понятие неориентированного графа.

Связный граф. Компоненты связности графа.

Степень вершины. Теорема о сумме степеней вершин графа.

Метрические характеристики графа.

Эйлеровы графы. Теорема Эйлера. Методика нахождения эйлерова цикла в эйлеровом графе.

Плоские графы. Примеры неплоских графов.

Кодирование Пруфера для деревьев с пронумерованными вершинами.

Понятие ориентированного графа (орграфа).

Степень входа и степень выхода вершины.

Источник. Сток. Ориентированный путь, ориентированный цикл.

Понятие достижимости вершин в орграфе. Матрица достижимости.

Эквивалентность вершин в орграфе. Классы эквивалентных вершин.

Диаграмма Герца. Сильно связный орграф.

Эйлеров орграф. Критерий эйлеровости орграфа.

Понятие ориентированного дерева.

Понятие бинарного дерева. Дисбаланс вершины в бинарном дереве.

Кодирование бинарных деревьев.

Понятие бинарного дерева сортировки, методика его построения.

5.2 Примерные задания контрольных срезов операции и их связь с логическими операциями»

Из 40 студентов курса 32 изучают английский язык, 21 – немецкий язык, а 15 – английский и немецкий языки. Сколько студентов курса не изучают ни английский, ни немецкий языки?

Пусть M 3,5,7,9. Определите в явном виде (перечислением своих элементов) множество (M ) и его мощность.

12,22,32,42,52,62,72,82,92.

Тема «Логические операции. Формулы логики»

Следующее составное высказывание расчлените на простые и запишите символически, введя буквенные обозначения для простых их составляющих: «Если прямая параллельна каждой из двух пересекающихся плоскостей, то она параллельна и линии их пересечения».

Сформулируйте и запишите в виде конъюнкции или дизъюнкции условие истинности предложения (a, b – действительные числа): a b 0.

Приведите равносильными преобразованиями формулу к дизъюнктивной нормальной форме: ( X Y ) Z.

Приведите равносильными преобразованиями формулу к конъюнктивной нормальной форме: X (Y Z ).

Составив таблицу значений для формулы, докажите, что она является тавтологией: ( P Q) ( P Q).

Тема «Булевы функции»

дизъюнктивную нормальную форму табличным способом.

конъюнктивную нормальную форму табличным способом.

полином Жегалкина.

линейна.

двойственную функцию.

Используя теорему Поста, докажите полноту системы булевых функций Тема «Основы теории графов. Характеристики графов»

Постройте матрицу достижимости для графа, представленного на рисунке:

21. Постройте матрицу инцидентности для графа G, представленного на рисунке:

22. Постройте матрицу смежности для графа G, представленного на рисунке:

23. Определите, являются ли графы, изображенные на рисунке, гамильтоновыми.

Для дерева, изображенного на рисунке, запишите его код Пруфера.

25. Выделите все компоненты связности графа, представленного на рисунке, и укажите их количество.

Проверьте, является ли граф, представленный на рисунке, двудольным.

Найдите мосты и разделяющие вершины в графе, представленном на рисунке.

Найдите эксцентриситет e(1) в графе, представленном на рисунке.

Определите, являются ли графы, изображенные на рисунке, изоморфными.

Постройте матрицу смежности, инцидентности для графа, представленного на рисунке:

Для вершин v1 и v 6 графа G на рисунке привести примеры маршрута, цепи, простой цепи; определить в графе цикл, простой цикл, приняв вершину v1 за их начало и конец.

Определите, является ли граф, изображенный на рисунке, эйлеровым.

5.3 Примерные вопросы устного опроса Тема «Законы алгебры логики. Представление функции в совершенных нормальных формах»

1. В чем заключается понятие равносильных формул.

2. Законы логики.

3. Методика упрощения формул логики с помощью равносильных преобразований.

Тема «Элементы теории отображений и алгебры»

1. Понятие отображения.

2. Взаимооднозначные (биективные) отображения.

3. Операция композиции отображений и ее свойства.

4. Обратное отображение.

5. Композиционная степень отображения.

6. Теорема о зацикливании степенной последовательности элемента.

7. Теорема о разбиении взаимооднозначного внутреннего отображения, заданного на конечном множестве, на отдельные независимые циклы.

8. Понятие подстановки.

9. Формула количества подстановок.

10. Циклическое разложение подстановки.

11. Произведение подстановок.

12. Обратная подстановка.

13. Степень подстановки.

Тема «Приложение алгебры вычетов к простейшим криптографическим шифрам»

1. Понятие вычета по модулю N; система вычетов по модулю N.

вычитание, умножение).

3. Обратимые вычеты.

4. Критерий обратимости вычета.

5. Проблема криптографической защиты информации.

6. Понятие шифрования.

7. Шифры замены.

8. Шифр Цезаря.

9. Шифр Виженера.

10. Перестановочные шифры.

Тема «Метод математической индукции»

1. Принцип математической индукции Тема «Алгоритмическое перечисление основных комбинаторных объектов»

2. Понятие алгоритмического перечисления (генерирования) элементов конечного множества.

3. Генерирование двоичных слов заданной длины.

4. Генерирование элементов декартова произведения множеств.

5. Генерирование перестановок заданной длины.

6. Генерирование К-элементных подмножеств данного множества.

7. Генерирование всех подмножеств данного множества.

Тема «Элементы теории автоматов»

1. Входной алфавит 2. Выходной алфавит Множество состояний.

Таблица автомата.

Принцип работы автомата.

Словарная функция автомата.

Финальная функция автомата.

Правильный автомат (автомат Мура).

5.4 Примерные тестовые задания Тема «Логика предикатов. Бинарные отношения и их виды»

Пусть x, y, z переменные со значениями из (-;). Указать какое из следующих выражений является двухместным предикатом:

c. 2+x+y+z= Пусть x, y, z переменные со значениями из (-;). Указать какое из следующих выражений не является предикатом:

c. x+y+z= d. sin(y)= Записать в виде 2местного предиката: «Все студенты группы сдали экзамен по предмету Элементы математической логики»

Записать в виде предиката: «Во всех городах за полярным кругом бывают белые ночи. Петербург не находится за полярным кругом. Следовательно, в Петербурге не бывает белых ночей»