Программа дисциплины Дискретная математика
рабочая программа на тему

ОДОБРЕНА:

На заседании ПЦК математических

дисциплин

Протокол № 1  от 30 августа 2016 г.

Председатель ПЦК_________Зубенко Л.А.

Рабочая программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта  по специальности

09.02.05 Прикладная информатика в образовании

(Приказ МО РФ № 1001 от 13.08.2014)

Заместитель директора

по учебной работе_________Н.В. Стасенко  

Вид учебной работы

Объем часов

Максимальная учебная нагрузка (всего)

130

Обязательная аудиторная учебная нагрузка (всего)

86

в том числе:

     лабораторные занятия – не предусмотрено

-

     практические занятия

44

     контрольные работы

-

     курсовая работа (проект) – не предусмотрено

-

     зачет

2

Самостоятельная работа обучающегося (всего)

44

в том числе:

домашнее задание

36

Написание реферата

3

построение графов, диаграмм

5

Итоговая аттестация                                          дифференцированный зачет                  

Наименование разделов и тем

Содержание учебного материала, лабораторные и практические работы, самостоятельная работа обучающихся

Объем часов

Уровень освоения

1

2

3

4

Введение

Содержание

2

1

Определение и роль дискретной математики в процессе основной профессиональной образовательной программы по специальности

1

2

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

3

3

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

1

4

Обзор методов дискретной математики и их применение

1

Раздел 1. Множества

22

Тема 1.1. Общие понятия теории множеств. Основные операции над множествами

Содержание 

2

1

Понятие  множества

2

2

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

1

3

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

1

4

Способы задания множества

1

5

Операции  над множествами: объединение, пересечение,  теоретико-множественная разность, дополнение

2

6

Свойства операций над множествами

1

7

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

2

8

Связь операций над множествами и логическими операциями

1

9

Применение аппарата  теории множеств для решения задач

2

Практическое занятие

4

1. Классификация множеств. Мощность множеств.

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

Примерная тематика внеаудиторной самостоятельной работы

3

1. Аксиомы множеств, алгоритм доказательства тождества множеств.

Тема 1.2  Соответствие между множествами. Отображения

Содержание

2

1

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

2

2

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

2

3

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

2

4

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

2

5

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

2

Практическое занятие

2

1. Составление отношений и построение графиков

Тема 1.3. Декартовы произведения

Содержание

1

Кортежи

2

2

Понятие декартова произведения

3

3

Табличное задание декартова произведения

3

4

Степень декартова призведения

3

5

Изоморфизм

2

Практическое занятие

2

1. Нахождение декартовых произведений

2. Табличное задание декартова произведения Х х У

Тема 1.4 Отношения. Бинарные отношения и их свойства

Содержание

2

1

Понятие бинарного отношения

2

2

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

1

3

Диаграмма бинарного отношения

2

4

Рефлексивные бинарные отношения

2

5

Симметричные бинарные отношения

3

6

Транзитивные бинарные отношения

3

7

Отношение эквивалентности

3

8

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

1

9

Выделение классов эквивалентности

3

10

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

2

Практическое занятие

2

1. Задание отношения, соответствия, отображения разными способами и их исследование

Примерная тематика внеаудиторной самостоятельной работы

3

1. Исследование бинарного отношения на рефлективность, симметричность и транзитивность.

Тема 1.5 Элементы комбинаторики

Содержание

2

1

Правило суммы и произведения

3

2

Размещения

3

3

Перестановки

3

4

Сочетания

3

5

Применение комбинаторики

2

Практические занятия

2

1. Применение комбинаторики при вычислении дискретных математических структур

Тема 1.6 Алгебра подстановок

Содержание

2

1

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

1

2

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

1

3

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

1

4

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

2

5

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

2

6

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

2

7

Методика решения простейших уравнений (ax=b, xa=b, axb=c) в алгебре подстановок

2

8

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

2

Практическое занятие

2

1. Выполнение операции над подстановками

Примерная тематика внеаудиторной самостоятельной работы

3

1. Выполнение операций и решение простейших уравнений в алгебре подстановок

Раздел 2. Теория графов

12

Тема 2.1. Основные понятия и определения графа и его элементов

Содержание 

2

1

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

2

2

Путь в графе. Цикл в графе.

1

3

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

1

4

Способы задания множества

1

5

Полный граф,  формула количества рёбер в полном графе

2

6

Понятие ориентированного графа (орграфа). Степень входа и степень выхода вершины. Источник. Сток. Ориентированный путь. Ориентированный цикл (контур)

1

7

Изоморфные графы.

2

8

Эйлеровы графы

2

9

Изоморфные графы.

2

10

Построение графов по заданным характеристикам

2

11

Деревья. Лес. Бинарные деревья

2

Примерная тематика внеаудиторной самостоятельной работы

3

1. История создания графов

Тема 2.2. Операции над графами

Содержание 

1

Объединение графов

1

2

Пересечение графов

2

3

Подграф

2

4

Кольцевая сумма

2

5

Связность

1

Практическое занятие

2

1. Выполнение операций над графами

Тема 2.3. Способы задания графа

Содержание 

2

1

Матрица инцидентности

2

2

Матрица смежности

2

3

Определение характеристик графов

2

4

Построение графов по заданным характеристикам

3

Практическое занятие

2

1. Построение диаграммы графа

Примерная тематика внеаудиторной самостоятельной работы

3

1. Граф Эйлера.

Тема 2.4. Сети. Сетевые модели представления информации

Содержание 

2

1

Понятие сети и семантических сетей

2

2

Фрейм. Сети Петри

2

3

Применение графов и сетей

2

4

Бинарный поиск

2

Практическое занятие

2

1. Применение графов и сетей при решении задач планирования. 

Раздел 3. Математическая логика

22

Тема 3.1. Понятие как форма мышления

Содержание 

2

1

Понятие

2

2

Логические приемы формирования понятий

1

3

Логические операции над понятиями

2

4

Отношения между понятиями. Определение понятий

3

5

Деление понятий. Классификация

Примерная тематика внеаудиторной самостоятельной работы

3

1. Определение понятий. Операции над понятиями. Деление понятий. Классификация.

Тема 3.2. Суждение как форма мышления

Содержание 

1

Понятие суждения

2

2

Понятие высказывания и высказывательной формы

2

3

Семантическая характеристика

3

4

Высказывание. Простое и составное высказывание.

3

5

Формализация высказываний

2

Практическое занятие

2

1.  Составление простых и составных высказываний. Формализация высказывания

Тема 3.3. Булевы функции

Содержание 

4

1

Понятие булевой функции

2

2

Равенство функций

2

3

Булевы функции одной переменной: тождественный нуль, тождественная единица, отрицание.

2

4

Булевы функции двух перменных: симметрические функции (конъюнкция, дизъюнкция, эквиваленция, сумма по модулю два, стрелка Пирса, штрих Шеффера, импликация)

3

5

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

3

6

Сложные высказывания. Операции над сложными высказываниями.

3

7

Логические связки. Словарь перевода на язык алгебры логики.

2

8

Обратное и противоположное высказывание.

2

9

Формулы алгебры логики.

3

10

Законы алгебры логики.

3

Практическое занятие

2

1. Операции над сложными высказываниями.

Примерная тематика внеаудиторной самостоятельной работы

4

1.  Логика вопросов и ответов

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

Содержание 

2

1

Разложение функций по переменным.

1

3

Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ).

2

4

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

2

5

Логические схемы. Инвертор.

3

6

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

2

Практическое занятие

4

1. Логические схемы.

2. Представление функций в современных нормативных формах

Примерная тематика внеаудиторной самостоятельной работы

4

1. Карты Карно для булевых функций трех (четырех переменных). Связь булевых функций с суммой по модулю два.

Тема 3.5. Полином Жегалкина. 

Содержание 

2

1

Операция двоичного сложения и ее свойства

1

2

Многочлен Жегалкина

3

3

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

3

Практические занятия

4

1

Функциональная замкнутость. Функционально полные системы функций

2

Проверка полноты множества функций. 

Примерная тематика внеаудиторной самостоятельной работы

3

1. Решение задач по теме «Полином Жикалкина»

Раздел 4. Формальные системы и умозаключения. Логика предикатов

10

Тема 4.1. Формальные системы

Содержание

2

1

Понятие о формальных системах.

1

2

Задание формальных систем.

2

3

Метатеория, метаязык

3

4

Требования, предъявляемые к формальным системам.  

3

5

Исчисление высказываний.

3

Примерная тематика внеаудиторной самостоятельной работы

3

1. Отличительные особенности геометрии Лобачевского и геометрии Евклида.

Тема 4.2. Логика предикатов

Содержание

2

1

Понятие предиката

1

2

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

2

3

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

2

4

Кванторные операции над предикатами (навешивание кванторов на предикат)

2

5

Понятие предикатной формулы

1

6

Свободные и связанные переменные

1

7

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

3

8

Формализация предложений с помощью логики предикатов

3

Практическое занятие

4

1. Логические операции  над предикатами

2. Исчисление предикатов, выполнение операций над предикатами.

Примерная тематика внеаудиторной самостоятельной работы

3

1. Умозаключения и их виды.

Тема 4.3. Методы научного познания

Содержание

1. Роль аналогии в научном познании.

1

2. Индкутивные умозаключения и их виды.

2

3. Виды индукции: полная, неполная.

2

4. Метод (полной) математической индукции. 

3

Практическое занятие

2

1. Методы научного познания

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

Примерная тематика внеаудиторной самостоятельной работы

3

Методы установления причинных связей. Метод Милли.

Раздел 5. Элементы теории и практики кодирования

8

Тема 5.1. Основные понятия вероятностной теории информации 

Содержание

2

1

Теория кодирования

1

2

Кодирование и декодирование.

2

3

Защита информации.

2

4

Криптология. Криптография. Криптоанализ.  

2

5

Системы счисления для представления информации в ЭВМ.

3

6

Основные понятия вероятностной теории информации: сигнал, дискретный и аналоговый, дискретизация.

2

7

Измерение информации. Энтропия. Формула Хартли. Формула Шеннона.   Обработка сообщений как кодирования.

2

8

Основные понятия теории кодирования: алфавит, префикс, постфикс, кодирующий алфавит, кодирование и декодирование.

3

Практическое занятие

2

1. Кодирование и декодирование различной информации с использованием известным видов кодирования. 

Тема 5.2. Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам.

Содержание

2

1

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

1

2

Система вычетов по модулю N

1

3

Операции над вычетами (сложение, вычитание, умножение) и их свойства

2

4

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

3

5

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

3

6

Система обратимых вычетов по модулю N

3

7

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

1

8

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

2

9

Шифры замены

2

10

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

3

11

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

2

12

Методика шифрования текста

2

Практическое занятие

2

1. Выполнение операций в алгебре вычетов.

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

Раздел 6. Конечные автоматы

8

Тема 6.1. Определения конечных автоматов.

Содержание

2

1

Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний

1

2

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

1

3

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

1

4

Диаграмма автомата

3

Тема 6.2. Способы задания конечных автоматов.

Содержание

2

1

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

1

2

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

1

3

Упрощённый вид диаграммы для правильных автоматов

1

4

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

3

Практические занятия

2

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

Дифференцированный зачет

2

Всего:

130

Результаты обучения

(освоенные умения, усвоенные знания)

Формы и методы контроля и оценки результатов обучения

Умения:

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

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

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

суммирующее оценивание результатов выполнения практических работ

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

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

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

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

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

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

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

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

находить характеристики графов

Знания:

логические операции, формулы логики, законы алгебры логики

оценка выполнения КИМов на зачете

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

основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями

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

элементы теории отображений и алгебры подстановок

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

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

алгоритмическое перечисление основных комбинаторных объектов

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

элементы теории автоматов