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

__________ОП.8. Дискретная математика__________________
название дисциплины

по специальности 230701 Прикладная информатика (по отраслям)
на базе основного общего образования

Константиновск 2012 г.

Примерная программа учебной дисциплины разработана на основе Федерального государственного образовательного стандарта (далее – ФГОС) по специальности (специальностям) среднего профессионального образования (далее СПО) / профессии (профессиям) начального профессионального образования (далее НПО) специальности 230701 Прикладная информатика (по отраслям)
код наименование специальности(ей) / профессии(ий)
Указать специальность (специальности) / профессию (профессии), укрупненную группу (группы) специальностей / профессий или направление (направления) подготовки в зависимости от широты использования примерной программы учебной дисциплины.

Организация-разработчик: ГБОУ СПО РО «КПК»

Разработчики: Алексей Юлия Вадимовна, преподаватель
Ф.И.О., ученая степень, звание, должность

СОДЕРЖАНИЕ

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

1. ПАСПОРТ ПРИМЕРНОЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ
ОП.8. Дискретная математика

1.1. Область применения программы
Примерная программа учебной дисциплины является частью примерной основной профессиональной образовательной программы в соответствии с ФГОС по специальности (специальностям) СПО / профессии (профессиям) НПО специальности 230701 Прикладная информатика (по отраслям).
Указать специальность (специальности) / профессию (профессии), укрупненную группу (группы) специальностей / профессий или направление (направления) подготовки в зависимости от широты использования примерной программы учебной дисциплины.

1.2. Место дисциплины в структуре основной профессиональной образовательной программы: общепрофессиональные дисциплины
указать принадлежность дисциплины к учебному циклу

1.3. Цели и задачи дисциплины – требования к результатам освоения дисциплины:

В результате освоения дисциплины обучающийся должен уметь:
 применять методы дискретной математики;
 строить таблицы истинности для формул логики;
 представлять булевы функции в виде формул заданного типа;
 выполнять операции над множествами, применять аппарат теории множеств для решения задач;
 выполнять операции над предикатами;
 исследовать бинарные отношения на заданные свойства;
 выполнять операции над отображениями и подстановками;
 выполнять операции в алгебре вычетов;
 применять простейшие криптографические шифры для шифрования текстов;
 генерировать основные комбинаторные объекты;
 находить характеристики графов;
В результате освоения дисциплины обучающийся должен знать:
 логические операции, формулы логики, законы алгебры логики;
 основные классы функций, полноту множеств функций, теорему Поста;
 основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями;
 логику предикатов, бинарные отношения и их виды;
 элементы теории отображений и алгебры подстановок;
 основы алгебры вычетов и их приложение к простейшим криптографическим шифрам;
 метод математической индукции;
 алгоритмическое перечисление основных комбинаторных объектов;
 основы теории графов;
 элементы теории автоматов.
1.4. Рекомендуемое количество часов на освоение программы дисциплины:
максимальной учебной нагрузки обучающегося 154 часов, в том числе:
обязательной аудиторной учебной нагрузки обучающегося 108 часов;
самостоятельной работы обучающегося 46 часов.

2. СТРУКТУРА И ПРИМЕРНОЕ СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ
2.1. Объем учебной дисциплины и виды учебной работы

Вид учебной работы Объем часов
Максимальная учебная нагрузка (всего) 154
Обязательная аудиторная учебная нагрузка (всего) 108
в том числе:
практические занятия 54
контрольные работы (дифференцированный зачет) 1 (4 сем)
курсовая работа (проект) (если предусмотрено) Нет
Самостоятельная работа обучающегося (всего) 46

2.2. Примерный тематический план и содержание учебной дисциплины ДИСКРЕТНАЯ МАТЕМАТИКА

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

Введение
Цели изучения дисциплины «Дискретная математика». Совокупность дисциплин и математический аппарат дискретного анализ, составляющих «Дискретную математику». Взаимосвязь дискретной математики с другими дисциплинами. Практические проблемы, изучаемые методами дискретной математики. 1

Тема 1.1. Общие понятия теории множеств Язык теории множеств.
Понятие «множество», элемент множества. Способы задания множеств: указание характеристического свойства, перечисление элементов. Пустое множество. 1
Изображение множеств (круги Эйлера, диаграммы Венна). Понятие «подмножества». Универсальное множество. Равные множества. Мощность множества.
Практические занятия 1
Изображение множеств с помощью кругов Эйлера.
Самостоятельная работа обучающихся 2
Изучить свойства счетных множеств.
Тема 1.2 Основные операции над множествами
Введение операций над множествами. Свойства операций над множествами. 3
Теоретико - множественные операции и их связь с логическими операциями: включение, объединение, пересечение, разность, дополнение множеств.
Законы пересечения и объединения множеств. Прямое (декартово) произведение множеств. Основные тождества алгебры множеств.
Практические занятия 3
Законы пресечения и объединения множеств. Доказательство основных тождеств алгебры множеств
Декартово произведение множеств. Изображение декартово произведения множеств на координатной плоскости
Решение задач с использованием аппарата теории множеств.
Самостоятельная работа обучающихся 3
Изучить аксиомы множеств, алгоритм доказательства тождества множеств, доказать законы двойственности, законы поглощения
Тема 1.3 Соответствие между множествами. Отображения
Основные понятия: соответствие между множествами, образ и прообраз элемента, множество значений, область определений, обратное соответствие. Задание соответствий: аналитический, табличный, графический. 2
Виды отображений: взаимно-однозначное, обратное отображение, равносильное, эквивалентное, равномощные. Композиция функций. Тождественное отображение.
Практические занятия 2
Составление отношений и построение графиков. Определение выполнимости свойств отношений на заданных множествах.
Установление взаимно-однозначного соответствия
Самостоятельная работа обучающихся 3
Элементы теории отображения и алгебры подстановок
Тема 1.4 Отношения. Бинарные отношения и их свойства
Отношение. Бинарное отношение. Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, антитранзитивность, асимметричность, связность. 2
Отношение эквивалентности. Отношение толетарности. Отношение порядка. Функциональные отношения.
Практические занятия 3
Задание отношения, соответствия, отображения разными способами.
Исследовать бинарные отношения на заданные свойства.
Выявление отношений эквивалентности, толетарности, порядка, функциональности.
Самостоятельная работа обучающихся 3
Изучить понятие равномощного множества.
Установить связь равномощного множества с понятием взаимно-однозначного соответствия, привести примеры решения задач по теме.
Тема 1.5 Элементы комбинаторики.
Комбинаторика. Правило суммы. Правило произведения. Комбинаторные объекты: размещения с повторениями, перестановки, размещения без повторений, перестановки с повторениями, сочетания с повторениями и без повторений. 2
Применение комбинаторики при вычислении дискретных математических структур.
Практические занятия 2
Генерировать основные комбинаторные объекты в данной практической ситуации.
Применение комбинаторики при вычислении дискретных математических структур.
Тема 1.6 Алгебра подстановок
Понятие подстановки. Каноническая и тождественная подстановки. 2
Подстановки. Свойства умножения подстановки. Инверсия. Порядок подстановки.
Произведение подстановок и его свойства. Инверсия, порядок, транспозиция подстановок.
Практические занятия 2
Выполнение операции над подстановками (инверсия, произведение, возведение в степень).
Применение подстановки и композиции при решении задач.
Самостоятельная работа обучающихся 2
Элементы теории отображения и алгебры подстановок
25
Тема 2.1. Основные понятия и определения графа и его элементов
Понятие графа, его элементов: вершина, ребро, петля, инцидентные вершины, смежные вершины, кратные и параллельные ребра, кратность и степень ребер. Изолированная и висячая вершина. Нуль-граф. 3
Полный и неполный граф. Дополнение графа. Ориентированный и неориентированный граф. Степени входа и выхода графа. Маршрут, длина маршрута, цикл, расстояние, цепь, путь. Связный граф, компоненты связности.
Изоморфные графы. Планарные (плоские) графы. Эйлеров граф. Уникурсальная фигура. Гамильтонов путь (цикл).
Практические занятия 3
Строить граф, находить его характеристики.
Применять аппарат теории графов для решения задач
Самостоятельная работа обучающихся 3
Изучить правило игры, придуманные Гамильтоном в XIX веке, задачу о коммивояжере - задачу математического программирования.
Тема 2.2. Операции над графами
Основные операции над графами: объединение, пересечение, нахождение подграфа. 1
Практические занятия 1
Выполнение основных операций над графами.
Самостоятельная работа обучающихся 2
Операции над графами. Кольцевая сумма.
Тема 2.3. Способы задания графа.
Изоморфные графы Изоморфные графы. 2
Способы задания: табличный, матричный (матрица инцидентности, матрица смежности).
Практические занятия 2
Построение диаграммы графа по заданным матрицам смежности или инцидентности.
Определение матриц (смежности или инцидентности) по заданной диаграмме графа.
Самостоятельная работа обучающихся 2
Граф Эйлера.
Тема 2.4. Сети. Сетевые модели представления информации
Взвешенный граф (сеть).семантическая сеть. Фрейм. Сети Петри. Иерархическая структура сложных систем. 2
Практические занятия 4
Применение графов и сетей при решении задач планирования.
Представление иерархических структур с помощью графов.
36
Тема 3.1. Понятие как форма мышления
Связь между логикой и математикой. Основные понятия математической логики: понятие, признак, анализ, сравнение, синтез, абстрагирование, обобщение. Семиотика. Синтаксические и семантические отношения. Логические характеристики понятий: содержание, объем. Закон обратного отношения между объемом и содержанием понятия. 1 2
Практические занятия 1 2
Определение родового понятия и видового отличия. Определение объема и содержания данного понятия.
Тема 3.2. Суждение как форма мышления.
Простые высказывания Алгебра логики. Суждение как форма мышления. Высказывание. Простое и составное высказывание. Формализация высказывания. 1 2
Практические занятия 1 2
Составление простых и составных высказываний. Формализация высказывания.
Самостоятельная работа обучающихся 2 3
Определение понятий. Операции над понятиями. Деление понятий. Классификация.
Тема 3.3. Булевы функции
Логические функции. Равенство функций. Формулы. Булевы функции одной переменной: тождественный нуль, тождественная единица, отрицание. Булевы функции двух перменных: симметрические функции (конъюнкция, дизъюнкция, эквиваленция, сумма по модулю два, стрелка Пирса, штрих Шеффера, импликация). 4 2
Способы задания булевых функций. Соглашение о написании формул.
Сложные высказывания. Операции над сложными высказываниями. Логические связки. Словарь перевода на язык алгебры логики. Обратное и противоположное высказывание.
Таблицы истинности для операций от одной (двух и более переменных).
Формулы алгебры логики. Свойство двойственности. Законы алгебры логики. Законы правильного мышления.
Практические занятия 4 2
Составление таблиц истинности для формул логики. Выявление эквивалентных булевых функций.
Доказательство законов алгебры логики.
Тождественные преобразования формул с использованием законов алгебры логики.
Самостоятельная работа обучающихся 2 3
Логика вопросов и ответов
Тема 3.4. Минимизация булевых функций
Разложение функций по переменным. Нормальные формы (ДНФ, СДНФ, КНФ, СКНФ). Построение нормальных форм для заданной булевой функции. 4 2
Логические схемы. Инвертор. Комбинационная схема, алгоритм построения функциональных схем для разработки устройства ПК.
Практические занятия 4 2
Представление функций в современных нормативных формах. Представление функций в виде СДФН и СКНФ
Составление логической схемы для заданной булевой функции (таблице истинности). Представление булевых функций в виде формул заданного типа.
Самостоятельная работа обучающихся 3 3
Карты Карно для булевых функций трех (четырех переменных). Связь булевых функций с суммой по модулю два.
Тема 3.5. Полином Жегалкина.
Функционально замкнутые классы Канонический полином Жегалкина. Функциональная замкнутость класса функций алгебры логики. Классы функций: класс функций, сохраняющих константу 0, класс функций, сохраняющих константу 1, класс самодвойственных функций, класс линейных функций, класс монотонных функций. 3 2
Функционально полные системы функций. Критерий полноты системы функций. Теорема Поста-Яблонского.
Практические занятия 3 2
Проверка полноты множества функций.
Использования теоремы Поста.
Выявление связи теоретико-множественных операций с логическими.
Самостоятельная работа обучающихся 3 3
Проверить, являются ли функционально замкнутыми классы:
а) S - класс самодвойственных функций;
б) L - класс линейных функций;
в) М - класс монотонных функций.
Изучить примеры доказательства полноты системы, например {+, V, 1}, составив таблицы Поста.

Тема 4.1. Формальные системы
Понятие о формальных системах. Задание формальных систем. Метатеория, метаязык. Требования, предъявляемые к формальным системам. 3 2
Исчисление высказываний. Правила подстановки, правило modus ponens. Правила введения и удаления логических знаков. Автоматизация исчисления высказываний.
Практические занятия 3 2
Соответствие формальных систем указанным требованиям.
Исчисление предикатов. Автоматизация исчисления высказываний с использованием установленных правил.
Самостоятельная работа обучающихся 2 3
Отличительные особенности геометрии Лобачевского и геометрии Евклида.
Тема 4.2. Логика предикатов
Язык логики предикатов: предикат, предикат-свойство, предикат-отношение, множество истинности предиката, тождественно-истинный предикат. 4 2
Логические операции (связки) над предикатами: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция, следование.
Кванторы. Классификация многоместных высказывательных форм. Формулы. Правила вывода исчисления предикатов. Свойства отношения классификации.
Практические занятия 4 2
Применение аппарата алгебры высказываний для работы с предикатами.
Исчисление предикатов, выполнение операций над предикатами.
Самостоятельная работа обучающихся 3 3
Умозаключения как форма мышления. Дедуктивные умозаключения и их виды.
Простые категорические силлогизмы. Энтимемы.
Тема 4.3. Методы научного познания
Роль аналогии в научном познании. Полная индукция. Индкутивные умозаключения и их виды. 2 2
Виды индукции: полная, неполная. Метод (полной) математической индкуции.
Практические занятия 1 2
Проведение доказательства методом полной математической индукции.
Самостоятельная работа обучающихся 2 3
Методы установления причинных связей. Метод Милли.
Тема 5.1. Основные понятия вероятностной теории информации
Теория кодирования. Кодирование и декодирование. Защита информации. Криптология. Криптография. Криптоанализ. 4 2
Системы счисления для представления информации в ЭВМ.
Основные понятия вероятностной теории информации: сигнал, дискретный и аналоговый, дискретизация. Измерение информации. Энтропия. Формула Хартли. Формула Шеннона.
Обработка сообщений как кодирования. Основные понятия теории кодирования: алфавит, префикс, постфикс, кодирующий алфавит, кодирование и декодирование. Равномерное, блочное, алфавитное кодирование. Кодирование с минимальной избыточностью.
Практические занятия 4 2
Обработка сообщений как кодирования.
Кодирование и декодирование различной информации с использованием известным видов кодирования.
Самостоятельная работа обучающихся 2 3
История кодирования от древности до наших дней. Защита информации.
Кодирование информации как средство обеспечения контроля работы автомата. Помехоустойчивое кодирование.
Тема 5.2. Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам.
Сравнение по модулю. Свойства сравнений. Вычеты по модулю. Контроль по модулю. 3 2
Цифровой метод контроля. Выбор модуля для контроля. Цифровая подпись.
Практические занятия 2 2
Выполнение операций в алгебре вычетов.
Приложение алгебры вычетов к простейшим криптографическим шифрам
Самостоятельная работа обучающихся 2 3
Шифрование с открытым ключом (СОК).
Тема 6.1. Определения конечных автоматов.
Автомат. Алгоритм. Виды автоматов: информационные, вычислительные, конечные, цифровые, синхронные, асинхронные, бесконечные, детерминированные, вероятностные, автоматы Мили, автоматы Мура, комбинационные. 2 2
Представление событий в автомате.
Практические занятия 2 2
Определение характеристик автомата.
Представление событий в автомате.
Самостоятельная работа обучающихся 3 3
Автоматы Мили, автоматы Мура.
Тема 6.2. Способы задания конечных автоматов.
Аналитический способ. Табличный способ. Графический способ. 2 2
Общие задачи теории автоматов: задача синтеза, задача анализа и задача декомпозиции.
Практические занятия 2 2
Описание работы кодового замка, составление таблицы переходов и соответствующего графа.
Сравнительный анализ возможностей человека и автомата.
Самостоятельная работа обучающихся 2 3
Двухкодовый триггер.
Сравнительный анализ возможностей человека и автомата.
Всего: 154

3. УСЛОВИЯ РЕАЛИЗАЦИИ ПРОГРАММЫ ДИСЦИПЛИНЫ
3.1. Требования к минимальному материально-техническому обеспечению
Реализация программы дисциплины требует наличия учебного кабинета математики; лабораторий ИКТ и вычислительной техники.
указывается наименование указываются при наличии

Оборудование учебного кабинета:
- посадочные места по количеству обучающихся;
- рабочее место преподавателя, оборудованное ЭВМ.
Технические средства обучения: стандартное.

Оборудование лаборатории и рабочих мест лаборатории: наличие персональных компьютеров, объединенных в сеть.

3.2. Информационное обеспечение обучения
Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы
Основные источники:
1. М.С.Спирина, П.А.Спирин Дискретная математика. Изд-во Академия/Academia", 2010 г.
Дополнительные источники:
1. Вентцель Е.С. «Исследование операций, задачи, принципы, методология» М. Наука 1988 г.
2. Гончарова Г.А., Мочалин А.А. «Элементы дискретной математики». М. Форум - инфри - м 2003 г.
3. Горбатов В.А. «Основы дискретной математики» М. Наука 1986 г.
4. Карпов В.Г., Мощенский В.А. «Математическая наука и Дискретная математика» Минск. Винца школа 1977 г.
5. Кузнецов О.П., Адельсон - Вильский Г.М. «Дискретная математика для инженера». Энергоатомиздат, 1998 г. I
6. Нефедов В.Н., Осипова В.А. «Курс дискретной математики» М. Издательство МАИ 1992 г.
7. Нефедов Ф.А. «Дискретная математика для программистов» СПб - Питер 2001 г.
8. Яблонский СВ. «Введение в дискретную математику» М. Наука.
4. КОНТРОЛЬ И ОЦЕНКА РЕЗУЛЬТАТОВ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Контроль и оценка результатов освоения дисциплины осуществляется преподавателем в процессе проведения практических занятий и лабораторных работ, тестирования, а также выполнения обучающимися индивидуальных заданий, проектов, исследований.

Результаты обучения
(освоенные умения, усвоенные знания) Формы и методы контроля и оценки результатов обучения
Знания:
логические операции, формулы логики, законы алгебры логики; индивидуальная, тестирование
основные классы функций, полноту множеств функций, теорему Поста; фронтальная, тестирование
основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями; фронтальная, практическая работа
логику предикатов, бинарные отношения и их виды; фронтальная, самостоятельная работа
элементы теории отображений и алгебры подстановок; индивидуальная, тестирование
основы алгебры вычетов и их приложение к простейшим криптографическим шифрам; фронтальная, практическая работа
метод математической индукции; фронтальная, самостоятельная работа
алгоритмическое перечисление основных комбинаторных объектов; фронтальная, тестирование
основы теории графов;
элементы теории автоматов. фронтальная, тестирование
Умения:
применять методы дискретной математики; индивидуальная, практическая работа
строить таблицы истинности для формул логики; групповая, практическая работа
представлять булевы функции в виде формул заданного типа; групповая, практическая работа
выполнять операции над множествами, применять аппарат теории множеств для решения задач; индивидуальная, практическая работа
выполнять операции над предикатами; групповая, практическая работа
исследовать бинарные отношения на заданные свойства; групповая, практическая работа
выполнять операции над отображениями и подстановками; индивидуальная, практическая работа
выполнять операции в алгебре вычетов; групповая, практическая работа
применять простейшие криптографические шифры для шифрования текстов; групповая, практическая работа
генерировать основные комбинаторные объекты; индивидуальная, практическая работа
находить характеристики графов; групповая, практическая работа
[center][right][center]