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

УТВЕРЖДАЮ

Директор ГБОУ СПО «ЖГК»

_________________А.Э. Птицын

«____»__________201__ г.

ОДОБРЕНА

Предметной (цикловой) комиссией

______________________________

Протокол № ____________

от “___” ______________ 201 ___ г.

Председатель___________ Л.В.Форсюк

ОДОБРЕНА

Предметной (цикловой) комиссией

______________________________

Протокол № ____________

от “___” ______________ 201 ___ г.

Председатель_____________ Н.И. Ежова

 (компьютерные системы и комплексы)

СОГЛАСОВАНО

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

научно-методической работе

____________________ Т.А. Агошкова

“___” ______________ 201___ г.

СОГЛАСОВАНО

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

учебно-воспитательной работе

_______________________ С.Ю. Сорокина

“___” ______________ 201___ г.

стр.

1. ПАСПОРТ РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

4

2. СТРУКТУРА И  СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

6

3. УСЛОВИЯ РЕАЛИЗАЦИИ  УЧЕБНОЙ ДИСЦИПЛИНЫ

12

4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ

13

5     ЛИСТ ИЗМЕНЕНИЙ И ДОПОЛНЕНИЙ, ВНЕСЕННЫХ В

      РАБОЧУЮ ПРОГРАММУ                                                                              

14

ПРИЛОЖЕНИЕ

15

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

Объем часов

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

138

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

92

в том числе:

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

-

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

40

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

4

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

46

в том числе:

Внеаудиторная самостоятельная работа

46

Итоговая аттестация в форме экзамена    

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

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

Объем часов

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

1

2

3

4

Тема 1.1

Формулы логики

Понятие высказывания. Основные логические операции (дизъюнкция, произведение (конъюнкция), импликация, эквиваленция, отрицание). Понятие формулы логики. Таблица истинности и методика ее построения. Тождественно-истинные формулы.

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

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

4

1-3

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

2

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

Самостоятельная работа

6

Решение задач на использование формул логики

Тема 1.2

Булевы функции

Понятие булева вектора (двоичного вектора). Соседние векторы. Противоположные векторы. Единичный N-мерный куб.

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

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

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

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

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

8

1-3

Практическая работа

4

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

Контрольная работа

2

Самостоятельная работа

4

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

Тема 1.3

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

Важнейшие замкнутые классы. Теорема Поста

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

4

1-3

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

6

Представление булевой функции в виде совершенной ДНФ, совершенной КНФ, минимальной ДНФ.

Проверка булевой функции на принадлежность к классам ТО, Tl, S, L, М.

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

Самостоятельная работа

6

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

Тема 1.4

Основы теории

множеств

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

Соответствие между теоретико-множественными и логическими операциями.

4

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

2

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

Самостоятельная работа

4

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

Тема 1.5

Предикаты.

 Бинарные

отношения

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

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

Понятие бинарного отношения; примеры бинарных отношений. Диаграмма бинарного отношения. Рефлексивные бинарные отношения.

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

4

1-3

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

6

Определение логического значения для высказываний типов x Р(х), х Р(х), x у Р(х, у), х y P(x, у).

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

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

Самостоятельная работа

6

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

Тема 1.6

Теория отображений и алгебра

подстановок

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

Диаграмма внутреннего отображения, заданного на конечном множестве; циклы. Степенная последовательность элемента (a, f(a), f2(a),...,fn(a),...). Теорема о зацикливании степенной последовательности элемента. Теорема о разбиении взаимооднозначного внутреннего отображения, заданного на конечном множестве, на отдельные независимые циклы Понятие подстановки. Формула количества подстановок. Произведение подстановок. Обратная подстановка. Степень подстановки. Методика решения простейших уравнений (ах=b, xa=b, axb=c) в алгебре подстановок. Чётные и нечетные подстановки, свойства четных и нечетных подстановок

2

1-2

Самостоятельная работа

4

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

Тема 1.7

Основы алгебры

вычетов

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

2

1-2

Тема 1.8

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

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

2

1-2

Самостоятельная работа

4

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

Тема 1.9

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

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

2

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

2

Шифрование текста с помощью шифра замены или перестановочного шифра

Самостоятельная работа

4

Дешифровка шифротекста, зашифрованного заданным шифром

Тема 1.10

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

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

4

1-3

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

2

Генерирование комбинаторных объектов заданного типа.

Самостоятельная работа

4

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

Тема 1.11

Основы теории

графов

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

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

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

Эйлеровы графы. Теорема Эйлера (критерий эйлеровости графа). Методика нахождения эйлерова цикла в эйлеровом графе. Гамильтоновы графы. Плоские графы. Грани плоской укладки плоского графа. Соотношения между количествами вершин, рёбер и граней в плоском графе. Примеры неплоских графов.

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

8

1-3

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

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

Бесконтурные орграфы. Теорема о существовании источника и стока в бесконтурном орграфе.

Эйлеровы орграфы. Критерий эйлеровости орграфа. Гамильтоновы орграфы.

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

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

14

Распознавание мостов и разделяющих вершин в графе, нахождение расстояния между вершинами в графе

Проверка графа на двудольность

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

 Проверка графа на эйлеровость, гамильтоновость, плоскость

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

Восстановление дерева по коду Пруфера

Запись матрицы достижимости и построение диаграммы Герца для ориентированного графа. Решение задач на бинарные деревья.

Контрольная работа

2

Самостоятельная работа

4

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

Тема 1.12

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

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

6

1-3

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

2

Построение автоматов, распознающих заданные свойства слова

Обязательная аудиторная нагрузка:

92

Всего:

138

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

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

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

Умения:

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

Устный, письменный и стандартизированный опрос,  практические работы.

• применять законы алгебры логики;

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

• определять типы графов и давать их характеристики;

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

• строить простейшие автоматы

Устный, письменный и стандартизированный опрос,  практические  работы.

Знания:

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

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

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

Устный, письменный и стандартизированный опрос,  лабораторные работы

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

Устный, письменный и стандартизированный опрос, контрольные, лабораторные работы

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

Устный, письменный и стандартизированный опрос,  практические работы

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

Устный, письменный и стандартизированный опрос, практические работы

• метод математической индукции; алгоритмическое перечисление основных комбинаторных объектов;

Устный, письменный и стандартизированный опрос,  практические  работы

• основные понятия теории графов, характеристики и виды графов;

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

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

Устный, письменный и стандартизированный опрос,  практические  работы

№ изменения,  дата внесения изменения; № страницы с изменением;

.

БЫЛО

СТАЛО

Основание:

Подпись лица внесшего изменения

№

п/п

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

Код формируемых

компетенций

1

Формулы логики

ОК1, ОК2

2

Булевы функции

ОК2, ОК4

3

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

ОК3, ОК4, ОК5

4

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

ОК6,ОК7

5

Предикаты Бинарные отношения

ОК3, ОК2, ОК9

6

Теория отображений и алгебра подстановок

ОК4, ОК3, ОК5

7

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

ОК8, ОК9

8

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

ОК10, ОК11

9

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

ОК8, ОК9

10

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

ОК3, ОК8

11

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

ОК6, ОК7

12

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

ОК9, ОК11