ТАМБОВСКОЕ ОБЛАСТНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
«ПРИБОРОСТРОИТЕЛЬНЫЙ КОЛЛЕДЖ»
УТВЕРЖДАЮ
Заместитель директора по учебной работе
_____________
ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
ОП.08 Дискретная математика
Разработал: Шаршова О.П.
ТОГБПОУ «Приборостроительный колледж», г. Тамбов
2018г.
Программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта по специальности среднего профессионального образования 09.02.01 Компьютерные системы и комплексы утвержденного приказом Минобрнауки России от 28.07.2014 №849 "Об утверждении федерального государственного образовательного стандарта среднего профессионального образования по специальности 09.02.01 Компьютерные системы и комплексы" (Зарегистрировано в Минюсте России 21.08.2014 №33748)
для специальности среднего профессионального образования технического профиля 09.02.01 Компьютерные системы и комплексы
Организация – разработчик:
ТОГБПОУ «Приборостроительный колледж»
Разработчик:
Шаршова О.П., преподаватель ТОГБПОУ «Приборостроительный колледж»
Рассмотрено на заседании Управляющего совета ТОГБПОУ «Приборостроительный колледж»
Протокол № ____ от "_____" ________________ 2018г.
СОДЕРЖАНИЕ
ПАСПОРТ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ | 4 |
СТРУКТУРА И СОДЕРЖАНИЕ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ | 5 |
УСЛОВИЯ РЕАЛИЗАЦИИ УЧЕБНОЙ ДИСЦИПЛИНЫ | 9 |
КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ | 11 |
паспорт ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ «Дискретная математика»
Область применения программы
Программа учебной дисциплины является частью основной профессиональной образовательной программы в соответствии с ФГОС по специальности среднего профессионального образования 09.02.01 Компьютерные системы и комплексы
1.2. Место дисциплины в структуре основной профессиональной образовательной программы: общепрофессиональная дисциплина профессионального цикла.
1.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины:
В результате изучения дисциплины «Дискретная математика» обучающийся должен уметь:
– строить таблицы истинности для формул логики и упрощать формулы логики;
– представлять булевы функции в виде формул заданного типа, проверять множество булевых функций на полноту;
– выполнять операции над множествами, применять аппарат теории множеств для решения задач;
– выполнять операции над предикатами;
– исследовать бинарные отношения на заданные свойства;
– находить характеристики графов, выделять структурные особенности графов, исследовать графы на заданные свойства.
В результате изучения дисциплины «Дискретная математика» обучающийся должен знать:
– основные понятия и приемы дискретной математики;
– логические операции, формулы логики, законы алгебры логики;
– основы теории множеств;
– логику предикатов, бинарных отношений и их виды;
– элементы теории отображений и алгебры подстановок;
– метод математической индукции;
– основные понятия теории графов, характеристики и виды графов;
– элементы теории автоматов.
1.4. Количество часов на освоение программы учебной дисциплины:
максимальной учебной нагрузки обучающегося _48__ часов,
в том числе:
обязательной аудиторной учебной нагрузки обучающегося_32_ часа;
самостоятельной работы обучающегося _16_ часов.
2.СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
2.1. Объем учебной дисциплины и виды учебной работы
Вид учебной работы | Объем часов |
Максимальная учебная нагрузка (всего) | 48 |
Обязательная аудиторная учебная нагрузка (всего) | 32 |
в том числе: | |
лабораторные работы (не предусмотрено) | - |
практические занятия (не предусмотрено) | - |
контрольные работы (не предусмотрено) | - |
курсовая работа (проект) (не предусмотрено) | - |
Внеаудиторная (самостоятельная) учебная работа (всего) | 16 |
в том числе: | |
самостоятельная работа над курсовой работой (проектом)(не предусмотрено) | - |
Мультимедийная презентация | 4 |
Решение задач | 8 |
Написание конспекта | 4 |
Итоговая аттестация в форме экзамена | |
2.2. Тематический план и содержание учебной дисциплины «Дискретная математика»
Наименование разделов и тем | Содержание учебного материала и формы организации деятельности обучающихся | Объем часов | Уровень освоения | |
Раздел 1. Основы теории множеств | 6 | |||
Тема 1.1. Основы теории множеств | Содержание учебного материала | 2 | 3 | |
1 | Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество; количество подмножеств конечного множества. Операции над множествами: пересечение, объединение, дополнение, теоретико-множественная разность. Свойства. Универсальное множество. | |||
Лабораторные работы(не предусмотрено) | - | |||
Практические занятия Решение задач на выполнение теоретико-множественных операций и на подсчет количества элементов. | 2 | |||
Самостоятельная работа обучающихся Написание конспекта на тему «Декартово произведение множеств», «Метод математической индукции» | 2 | |||
Раздел 2. Формулы логики | 8 | |||
Тема 2.1. Логические операции. Формулы логики. Законы алгебры логики. Равносильные преобразования | Содержание учебного материала | 2 | 3 | |
1 | Понятие высказывания. Основные логические операции. Понятие формулы логики. Таблица истинности и методика ее построения. Тождественно-истинные формулы. Понятие элементарного произведения; понятие дизъюнктивной нормальной формы (ДНФ). Понятие элементарной дизъюнкции и конъюнктивной нормальной формы (КНФ). Равносильные формулы. Законы логики. Методика упрощения формул логики с помощью равносильных преобразований. | |||
Лабораторные работы(не предусмотрено) | - | |||
Практические занятия Решение задач на упрощение формул логики с помощью равносильных преобразований | 4 | |||
Самостоятельная работа обучающихся Решение задач с использованием формул логики | 2 | |||
Раздел 3. Булевы функции | 12 | |||
Тема 3.1. Функции алгебры логики. Полнота множества функций. | Содержание учебного материала | 2 | 2 | |
1 | Понятие булева вектора (двоичного вектора). Соседние, противоположные векторы. Понятие булевой функции (функции алгебры логики). Способы задания булевой функции. Проблема представления булевой функции в виде формулы логики. Понятие совершенной ДНФ. Понятие совершенной КНФ. | |||
Лабораторные работы(не предусмотрено) | - | |||
Практические занятия Решение задач на представление булевой функции в виде совершенной ДНФ, совершенной КНФ. | 2 | |||
Самостоятельная работа обучающихся Мультимедийная презентация на тему «Методика представления булевой функции в виде совершенной КНФ и ДНФ» | 4 | |||
Тема 3.2. Полнота множества функций. Важнейшие замкнутые классы | 1 | Понятие выражения одних булевых функций через другие. Полнота множества функций. Замыкание множества функций. Полнота замкнутого класса функций. Важнейшие замкнутые классы: Т0 (класс функций, сохраняющих константу 0), Т1 (класс функций, сохраняющих константу 1), S (класс самодвойственных функций), L (класс линейных функций), М (класс монотонных функций). Теорема Поста. | 2 | 2 |
Лабораторные работы(не предусмотрено) | - | |||
Практические занятия Решение задач на проверку булевой функции на принадлежность к классам Т0, Т1, S, L, М; на проверку множества на полноту. | 2 | |||
Самостоятельная работа обучающихся (не предусмотрено) | - | |||
Раздел 4. Предикаты. Бинарные отношения | 12 | |||
Тема 4.1. Предикаты. Бинарные отношения | Содержание учебного материала | 4 | 2 | |
1 | Понятие предиката. Область определения и область истинности предиката. Обычные логические операции над предикатами. Кванторные операции над предикатами. Понятие предикатной формулы; свободные и связанные переменные. Построение отрицаний к предикатам, содержащим кванторные операции. Понятие бинарного отношения; примеры бинарных отношений. Свойства отношений. Рефлексивные, симметричные, транзитивные отношения. | |||
Лабораторные работы(не предусмотрено) | - | |||
Практические занятия Решение задач на определение логического значения для высказываний.. Формализация предложений с помощью логики предикатов. | 4 | |||
Самостоятельная работа обучающихся Написание конспекта на тему «Отношение эквивалентности. Классы эквивалентности. Теорема о разбиении множества на классы эквивалентности» Решение задач на тему «Построение отрицаний к предикатам» | 2 2 | |||
Раздел 5. Основы теории графов | 10 | |||
Тема 5.1. Основные понятия теории графов | Содержание учебного материала | 4 | 3 | |
1 | Понятие графа и их виды. Способы задания графов. Основные характеристики графов. Операции над графами. Понятие неориентированного графа. Матрица смежности. Связный граф. Полный граф; формула количества ребер в полном графе. Расстояние между вершинами в графе. Радиус и диметр графа. Центральные вершины. Изоморфные графы. Эйлеровы графы. Методика нахождения эйлерова цикла в эйлеровом графе. Понятие ориентированного графа (орграфа). Ориентированный путь (контур). Матрица достижимости. Эйлеровы орграфы. Критерий эйлеровости орграфа. Понятие ориентированного дерева. Понятие бинарного дерева. | |||
Лабораторные работы(не предусмотрено) | ||||
Практические занятия Решение упражнений на проверку графа на эйлеровость. Запись матрицы достижимости, построение диаграммы для ориентированного графа. | 2 | |||
Самостоятельная работа обучающихся Решение задач на тему «Бинарные деревья» | 4 | |||
Примерная тематика курсовой работы (проекта) (не предусмотрено) | - | |||
Самостоятельная работа обучающихся над курсовой работой (проектом) (не предусмотрено) | - | |||
Всего | 48 | |||
3. УСЛОВИЯ РЕАЛИЗАЦИИ ПРОГРАММЫ ДИСЦИПЛИНЫ
3.1. Требования к минимальному материально-техническому обеспечению
Реализация программы модуля предполагает наличие учебного кабинета «Математика», библиотеки с читальным залом и выходом в сеть Интернет.
Оборудование учебного кабинета: стенды, плакаты, раздаточный материал.
Технические средства обучения: персональный компьютер, мультимедийный проектор.
3.2. Информационное обеспечение обучения
Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы.
Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы
Основные источники:
Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика. – Таганрог: изд-во ТРТУ, 2015;
Кузнецов О.П. Дискретная математика для инженера. – СПб: Лань, 2014;
Мелихова З.А., Мелихова О.А. Основы теории булевых функций и конечных автоматов. – Таганрог: ТРТУ, 2013;
Мелихова З.А., Мелихова О.А. Прикладные задачи теории графов. Учебное пособие. – Таганрог: ТРТУ, 2014;
Спирина М.С., Спирин П.А. Дискретная математика. – М: Академия, 2013.
Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2013.
Дополнительные источники:
Горбатов В.А. Основы дискретной математики. – М.: Наука, 2011;
Данко П.Е., Попов А.Г., Кожевников Т.Я. Высшая математика в упражнениях и задачах. – М.: Мир и образование, 2010;
Мелихова З.А., Мелихова О.А. Программа, методические указания и контрольные задания по курсу «Дискретная математика». – Таганрог: ТРТУ, 2014;
Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Изд-во МАИ, 2011;
Новиков Ф.А. Дискретная математика для программистов.– М.: Питер, 2012.
Интернет-ресурсы:
1.http://www.matburo.ru/ Математическое Бюро: Учебники по дискретной математике.
2.http://www.math.by/Образовательный сайт по математике. Представляет собой сборник часто встречаемых задач по математике и решений этих задач. Цель сайта – помочь учащимся решить задачи и проверить свое решение.
4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Контроль и оценка результатов освоения дисциплины осуществляется преподавателем в процессе проведения практических занятий и лабораторных работ, тестирования, а также выполнения обучающимися индивидуальных заданий.
Результаты обучения (освоенные умения, усвоенные знания) | Формы и методы контроля и оценки результатов обучения |
Знать понятия множества и подмножества; формулу количества подмножеств конечного множества; операции над множествами и их свойства; формулу количества элементов в объединении нескольких (двух, трех) конечных множеств. | Тестирование, практическая работа, письменная работа |
Знать основные логические операции; понятия: формулы логики, таблицы истинностиформулы логики и методику ее построения, тождественно-истинной формулы; дизъюнктивной нормальной формы (ДНФ),понятие элементарной дизъюнкции и конъюнктивной нормальной формы (КНФ). | Тестирование, практическая работа, письменная работа |
Знать понятие равносильности двух формул логики; законы логики; методику упрощения формул логики с помощью равносильных преобразований. | Тестирование, фронтальный опрос, самостоятельная работа |
Знать понятия булева вектора, соседних и противоположных булевых векторов; булевой функции (функции алгебры логики) и способы ее задания; совершенной ДФН; методику представления булевой функции в виде совершенной ДФН; понятие совершенной КФН. | Тестирование, фронтальный опрос, самостоятельная работа |
Знать понятия: выражение одних булевых функций через другие, полноты множества функций, замкнутого класса, важнейшие замкнутые классы: Т0, Т1, S,L, М; теорему Поста. | Тестирование, фронтальный опрос, самостоятельная работа |
Уметь проверять булеву функцию на принадлежность к классам: Т0, Т1, S,L, М; проверять множество булевых функций на полноту (с помощью теоремы Поста). | Тестирование, фронтальный опрос, самостоятельная работа |
Знать понятие предиката; области определения и области истинности предиката; операции над предикатами; понятие предикатной формулы; свободные и связанные переменные; методику построения отрицаний к предикатам, содержащим кванторные операции; понятия бинарных отношений; примеры бинарных отношений; свойства отношений; отношения эквивалентности; теорему о разбиении множества на классы эквивалентности. | Тестирование, фронтальный опрос, самостоятельная работа |
Уметь записывать область истинности предиката; определять логическое значение для высказываний типов ∀xP(x), ∃x P(x), ∀ x ∃у P(x,у), ∃x ∀у Р(х, у); выделять в предикатной формуле свободные переменные и связанные переменные; строить отрицания к предикатам, содержащим кванторные операции; формализовывать предложения с помощью логики предикатов. | Тестирование, фронтальный опрос, самостоятельная работа |
Знать понятие графа и их виды; способы задания графов; основные характеристики графов; операции над графами; понятие неориентированного графа; основные определения, связанные с ним; теорему о сумме степеней вершин графа; формулу количества ребер в полном графе; методику выполнения компонент связности в графе; понятие расстояния между вершинами в графе и методику его нахождения; понятия радиуса и диметра графа, центральной вершины; понятие изоморфности двух графов, методику проверки пары графов на изоморфность; понятие эйлерова графа, теорему Эйлера, методику нахождения эйлерова цикла в эйлеровом графе. | Тестирование, фронтальный опрос, самостоятельная работа |
Уметь записывать матрицу смежности для графа; находить количество ребер в графе (с помощью теоремы о сумме степеней вершин графа); выделять компоненты связности в графе; находить расстояние между вершинами в графе, находить радиус и диметр графа; проверять являются ли два графа изоморфными (в простейших случаях); проверять является ли граф эйлеровым; находить эйлеров цикл в эйлеровом графе. | Тестирование, фронтальный опрос, самостоятельная работа |
Знать понятие ориентированного графа (орграфа) и основные определения, связанные с ним; понятие достижимости вершин в орграфе; методику записи матрицы достижимости орграфа; понятие эквивалентности вершин в орграфе; понятие бесконтурного орграфа, теорему о существовании источника и стока в бесконтурном орграфе; понятие эйлерова орграфа, критерий эйлеровости орграфа; понятие ориентированного дерева; кодирование бинарного дерева. | Тестирование, фронтальный опрос, самостоятельная работа |
Уметь записывать матрицу смежности для орграфа; находить степени входа и выхода вершин; находить множество достижимости вершины в орграфе; записывать матрицу достижимости орграфа; выделять классы эквивалентных вершин в орграфе; записывать код бинарного дерева; по коду восстанавливать бинарное дерево. | Письменная работа, тестирование, практическая работа. |
.png)
