РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ «ДИСКРЕТНАЯ МАТЕМАТИКА»

государственное автономное профессиональное образовательное учреждение Свердловской области «Нижнетагильский государственный профессиональный колледж имени Никиты Акинфиевича Демидова»

(ГАПОУ СО «НТГПК им. Н.А. Демидова»)

для специальности 09.02.05Прикладная информатика (по отраслям)

Зам. директора по УМР

_______________О.А. Фищукова

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

09.02.05. «Прикладная информатика»

09.00.00 ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

РЕКОМЕНДОВАНО:

НМС колледжа

протокол № ___ от ___________20__г.

председатель________С.А. Лысуенко

СОГЛАСОВАНО:

Руководитель ОПОП 09.02.05 Прикладная информатика (по отраслям)

Т.И. Коновалова_________________

РАССМОТРЕНО:

на заседании ПЦК

протокол № __ от ____________20__г.

председатель _______Я.О. Полякова

Разработчик:

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

Л.М. Авсеенко_____________________

стр.

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

4

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

6

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

7

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

13

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

Количество часов

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

136

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

96

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

-

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

36

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

-

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

в том числе:

40

Домашняя контрольная работа

-

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

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

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

Объем часов

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

1

2

3

4

Раздел 1. Элементы теории множеств

16

2

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

Основные понятия дискретной математики. Множества. Операции над множествами.

2

2

Практическая работа №1: Выполнение операций над множествами.

2

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

4

Тема 1.2. Бинарные операции над множествами.

Основные тождества алгебры множеств. Принцип включений-исключений. Бинарные отношения. Свойства бинарных отношений. Аксиомы теории множеств. Отображение множеств.

2

2

Практическая работа №2.Решение задач на принцип включений-исключений.

2

Практическая работа №3.Построение бинарных отношений. Исследование бинарных отношений на заданные свойства.

2

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

2

Раздел 2. Элементы комбинаторики

24

2

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

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

2

2,3

Бином Ньютона. Полиноминальная теорема.

2

2

Практическая работа №4. Основные вычисления. Свойства биноминальных коэффициентов.

2

Практическая работа №5.Бином Ньютона, биномиальные коэффициенты и треугольник Паскаля.

2

Самостоятельная работа обучающихся. Подготовка сообщения по теме «Бином Ньютона, биномиальные коэффициенты и треугольник Паскаля».

2

Тема 2.2.Производящие функции

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

2

2

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

2

2

Экспоненциальные производящие функции.

2

2

Метод включений и исключений. Функция Эйлера. Функция Мебиуса.

2

2,3

Практическая работа №6.Производящие функции и рекуррентные соотношения.

2

Практическая работа №7. Формула включений и исключений.

2

Самостоятельная работа обучающихся. Решение задач по теме «Производящие функции. Разбиения».

2

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

20

2

Тема 3.1.Основные понятия теории графов

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

2

2

Связность графа. Ориентированные графы.

2

2

Самостоятельная работа обучающихся. Решение задач по теме «Операции над графами. Поиск минимального пути в графе. Поиск максимального пути в графе».

4

Тема 3.2.Основные операции над графами

Упорядочивание дуг и вершин орграфа. Выявление маршрутов с заданным количеством ребер.

2

Алгоритмы нахождения максимального пути.

2

2

Обходы графов. Фундаментальные циклы. Планарность графа.

2

2

Практическая работа №8.Решение задач на нахождение характеристик графов. Нахождение максимального и минимального пути в графах. Построение матриц смежности и инциденций.

2

Самостоятельная работа обучающихся. Подготовка сообщения по теме «Бесконечные графы. Раскраска графа. Гипотеза о четырех красках». Решение задач по теме «Раскраска графа»

4

Раздел 4. Элементы математической логики

24

2

Тема 4.1.Основы алгебры логики

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

2

2

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

2

2

Равносильные группы формул и равносильные преобразования.

2

2

Практическая работа №9.Построение логических схем. Построение таблиц истинности. Доказательство равносильности логических формул

2

Практическая работа № 10.Логические операции.

2

Самостоятельная работа обучающихся. Решение логических задач. Подготовка сообщения по теме «Тавтологии алгебры высказываний».

4

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

Алгебра Буля. Функции алгебры логики.

2

2

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

2

2

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

2

2

Практическая работа №11. Функции алгебры логики.

2

Самостоятельная работа обучающихся. Решение задач по теме «Равносильные преобразования формул и логическое следование формул логики предикатов. Исчисление предикатов».

2

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

20

2

Тема 5.1.Основы теории кодирования

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

2

2

Помехоустойчивое кодирование. Канал связи. Криптология. Алфавитное кодирование. Математическое изучение алфавитного кодирования.

2

2

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

2

2

Практическая работа № 12Алфавитное кодирование

2

Самостоятельная работа обучающихся. Решение задач по теме «Наибольший общий делитель. Наименьшее общее кратное. Простые числа».

2

Тема 5.2.Коды Хемминга

Двоичный код. Самокорректирующиеся коды.

2

2

Коды Хемминга. Алгоритм построения кода Хемминга. Декодирование (получение исходного сообщения)

2

2

Практическая работа № 13Коды Хемминга.

2

Самостоятельная работа обучающихся. Решение задач по теме «Коды Хемминга. Алгоритм построения кода Хемминга».

4

Раздел 6. Элементы теории автоматов

8

2

Тема 6.1.Конечные автоматы

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

2

2

Тема 6.2.Каноническое уравнение автомата

Примеры конечных автоматов. Каноническое уравнение автомата.

2

2

Практическая работа № 14 Конечные автоматы

2

Самостоятельная работа обучающихся. Разработка конспекта по теме «Каноническое уравнение автомата».

2

Раздел 7. Элементы теории автоматов

14

2

Тема 7.1.Рекурсивные функции

Вычислимые функции и алгоритмы. Теория рекурсивных функций

2

2

Практическая работа № 15 Рекурсивные функции

2

Самостоятельная работа обучающихся.Теория рекурсивных функций

2

Тема 7.2.Нормальный алгоритм Маркова

Основные понятия. Алгоритм Маркова. Нормально вычислимая функция

2

2

Практическая работа № 16Нормальные алгоритмы

2

Самостоятельная работа обучающихся. Решение задач по теме «Схемы из функциональных элементов. Релейно-контактные схемы».

4

Раздел 7. Элементы теории алгоритмов

10

2

Тема 7.1.Алгоритмы Тьюринга

Основные понятия и теоремы. Формализация машины Тьюринга. Тезис Черча – Тьюринга.

2

2

Практическая работа № 17Машина Тьюринга

2

Практическая работа № 18Машина Тьюринга

2

Самостоятельная работа обучающихся. Решение задач по теме «Формализация машины Тьюринга».

2

Консультация к экзамену

2

2

Итого:

136

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

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

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

умения:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

знания:

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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

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

тестовые задания открытой формы,

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