Рабочая программа по Дискретной математике для специальности Прикладная информатика

стр.

1. ПАСПОРТ рабочей ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

2

1. СТРУКТУРА и содержание УЧЕБНОЙ ДИСЦИПЛИНЫ

4

1. условия реализации рабочей программы учебной дисциплины

10

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

13

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

Объем часов

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

126

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

84

в том числе:

лабораторные занятия

-

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

30

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

-

курсовая работа (проект)

-

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

36

в том числе:

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

- работа с конспектами лекций

- работа с материалом учебных пособий

- подготовка к выполнению практических заданий

- выполнение тестовых заданий

- решение задач и упражнений

26

для самостоятельного овладения учебным материалом:

- изучение материала учебника, пособия, дополнительного источника;

- конспектирование текста;

- работа со справочниками;

10

Консультации

6

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

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

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

Объем часов

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

1

2

3

4

Раздел 1.

Введение в дисциплину. Основы теории множеств.

9

(6 ауд + 3 сам)

2

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

Содержание учебного материала

4

2

1

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

2

Понятие «множество». Конечные и бесконечные множества. Пустое множество. Подмножество. Количество подмножеств конечного множества. Операции над множествами и их свойства.

Самостоятельная работа обучающихся

Выполнение практического задания: «Решение задач на выполнение теоретико-множественных операций».

2

2

Тема 1.2. Формулы количества элементов в объединении нескольких множеств.

Содержание учебного материала

2

2

1

Формула количества элементов в объединении двух конечных множеств; соответствующая формула для трех множеств.

2.

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

Самостоятельная работа обучающихся

Выполнение практического задания «Подсчет количества элементов в объединении нескольких конечных множеств».

1

2

Раздел 2.

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

23

(18 ауд + 5 сам)

Тема 2.1. Основные логические операции. Формулы логики. Таблица истинности. Дизъюнктивная нормальная форма.

Содержание учебного материала

8

2

1

Понятие «высказывание». Основные логические операции. Формулы логики. Таблица истинности и методика ее построения. Тождественно-истинные формулы.

2

Понятие «элементарное произведение». Понятие «дизъюнктивная нормальна форма».

Практическое занятие 1. «Построение таблицы истинности для формулы логики».

4

2

Самостоятельная работа обучающихся

Выполнение практического задания: «Построение таблицы истинности для ДНФ упрощенным методом»

2

2

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

Содержание учебного материала

2

2

1

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

Самостоятельная работа обучающихся

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

1

2

Тема 2.3. Проверка теоретико-множественных отношений с помощью формул логики.

Содержание учебного материала

2

2

1

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

Практическое занятие 2. «Проверка двух формул на равносильность».

2

2

Самостоятельная работа обучающихся

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

2

2

Раздел 3.

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

22

(16 ауд+6 сам)

Тема 3.1. Булевы векторы. Понятие булева функция. Совершенная ДНФ.

Содержание учебного материала

2

2

1

Понятие «булев вектор». Понятие «булева функция». Способы задания булевой функции. Совершенная ДНФ. Представление булевой функции в виде совершенной ДНФ,

Практическое занятие 3. «Представление булевой функции в виде совершенной ДНФ».

4

2

Самостоятельная работа обучающихся

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

2

2

Тема 3.2.

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

Содержание учебного материала

2

2

1

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

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

4

2

Самостоятельная работа обучающихся

Выполнение практического задания: «Представление в виде полинома Жегалкина булевой функции, заданной таблично».

2

2

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

Содержание учебного материала

4

2

1

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

Практическое занятие 5. «Проверка булевой функций на принадлежность к классам T0, T1, S, L, M».

2

2

Самостоятельная работа обучающихся

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

2

2

Раздел 4.

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

10

(6 ауд+4 сам)

Тема 4.1. Предикаты.

Содержание учебного материала

2

2

1

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

Практическое занятие 6. «Решение задач на определение области истинности предиката».

2

2

Самостоятельная работа обучающихся

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

2

2

Тема 4.2. Бинарные отношения.

Содержание учебного материала

2

2

1

Понятие «бинарное отношение». Рефлексивные, симметричные и транзитивные бинарные отношения. Отношения эквивалентности. Теорема о разбиении множества на классы эквивалентности.

Самостоятельная работа обучающихся

Выполнение практического задания: «Исследование бинарных отношений на рефлексивность, симметричность и транзитивность».

2

2

Раздел 5.

Отображения. Подстановки.

9

(6 ауд+3 сам)

Тема 5.1. Отображения.

Содержание учебного материала

2

2

1

«Понятие «отображение». Способы задания отображения. Композиция отображений. Обратные отображения.

Самостоятельная работа обучающихся

Выполнение практического задания: «Решение задач на выполнение операции композиции отображений, на запись обратного отображения».

1

Тема 5.2. Подстановки.

Содержание учебного материала

2

2

1

Понятие «подстановка». Формула количества подстановок. Произведение подстановок. Обратная подстановка. Четные и нечетные подстановки. Методика решения простейших уравнений с подстановками. Порядок подстановки.

Практическое занятие 7. «Решение простейших уравнений с подстановками».

2

2

Самостоятельная работа обучающихся

Выполнение практического задания: «Определение порядка и четности подстановки».

2

2

Раздел 6.

Алгебра вычетов по модулю N.

6

(4 ауд+2 сам)

Тема 6.1. Алгебра вычетов по модулю N.

Содержание учебного материала

4

2

1

Понятие «вычет по модулю N». Система вычетов по модулю N. Операции над вычетами и их свойства. Обратимые вычеты. Методика решения уравнений в алгебре вычетов.

Самостоятельная работа обучающихся

Выполнение практического задания: «Решение простейших уравнений в алгебре вычетов».

2

3

Раздел 7.

Некоторые элементы теории и практики шифрования.

3

(2 ауд+1 сам)

Тема 7.1. Некоторые элементы теории и практики шифрования.

Содержание учебного материала

2

2

1

Понятие «шифрование». Задачи теории шифрования и области ее применения. Шифры замены. Шифр Цезаря и шифр Виженера. Абсолютно стойкий шифр однократного использования. Понятие о шифросистемах с «открытым ключом».

Самостоятельная работа обучающихся

Выполнение практического задания: «Шифрование текста с помощью шифра Виженера».

1

2

Раздел 8.

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

8

(6 ауд+2 сам)

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

Содержание учебного материала

2

2

1

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

Практическое занятие 8. «Доказательство утверждений с помощью метода математической индукции».

4

2

Самостоятельная работа обучающихся

Реферат на тему: «Доказательство некоторых теорем элементарной алгебры методом математической индукции».

2

2

Раздел 9.

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

6

(4 ауд+2 сам)

Тема 9.1. Алгоритмическое перечисление некоторых видов комбинаторных объектов.

Содержание учебного материала

4

2

1

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

Самостоятельная работа обучающихся

Выполнение практического задания: «Генерирование комбинаторных объектов заданного типа».

2

2

Раздел 10.

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

16

(10 ауд+6сам)

Тема 10.1. Неориентированный граф.

Содержание учебного материала

2

2

1

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

Самостоятельная работа обучающихся

Выполнение практического задания: «Нахождение метрических характеристик графа».

2

2

Тема 10.2. Эйлеровы и гамильтоновы графы. Плоские графы.

Содержание учебного материала

2

2

1

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

Практическое занятие 9. «Распознавание графов на эйлеровость и гамильтоновость ».

2

2

Самостоятельная работа обучающихся

Выполнение практического задания: «Распознавание графа на плоскость».

2

2

Тема 10.3. Ориентированный граф.

Содержание учебного материала

2

2

1

Понятие «ориентированный граф». Матрица смежности для орграфа. Степень входа и степень выхода вершины. Ориентированный путь. Ориентированный цикл. Матрица достижимости.

Самостоятельная работа обучающихся

Выполнение практического задания: «Запись матрицы достижимости для орграфа».

1

3

Тема 10.4. Деревья. Код Пруфера. Бинарные деревья.

Содержание учебного материала

2

2

1

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

Самостоятельная работа обучающихся

Выполнение практического задания: «Построение бинарного дерева сортировки».

1

3

Раздел 11.

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

8

(6 ауд+2 сам)

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

Содержание учебного материала

2

2

1

Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний. Таблица автомата. Принцип работы автомата. Диаграмма автомата. Автомат, распознающий свойство слова, и его построение.

Практическое занятие 10. «Построение автоматов, распознающих заданные свойства слова ».

4

2

Самостоятельная работа обучающихся

Написание рефератов на темы, например:

«Классификация автоматов»;

«Автоматы и компьютеры, область применения в современном мире».

2

Консультации

6

Всего:

126

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

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

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

Уметь:

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

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

экспертная оценка; защита работы

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

экспертная оценка; защита работы

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

экспертная оценка; защита работы

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

экспертная оценка; защита работы

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

экспертная оценка; защита работы

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

экспертная оценка; защита работы

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

тестирование; зачет

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

тестирование; зачет

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

тестирование; зачет

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

экспертная оценка; защита работы

Знать:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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