Нижний Тагил, 2016 г.
Программа учебной дисциплины является частью программы подготовки специалистов среднего звена по специальности среднего профессионального образования 09.02.05 Прикладная информатика (по отраслям) укрупненной группы направлений подготовки специалистов среднего звена 09.00.00 Информатика и вычислительная техника.
самостоятельной работы - 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 | |
Для характеристики уровня освоения учебного материала используются следующие обозначения:
1. – ознакомительный (узнавание ранее изученных объектов, свойств);
2. – репродуктивный (выполнение деятельности по образцу, инструкции или под руководством)
3. – продуктивный (планирование и самостоятельное выполнение деятельности, решение проблемных задач)
Реализация учебной дисциплины требует наличия: учебного кабинета математических дисциплин.
Оборудование учебного кабинета: посадочные места по количеству обучающихся, рабочее место преподавателя, учебно-планирующая документация, рекомендуемые учебники, дидактический материал, раздаточный материала.
Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы
Акимов О.Е. Дискретная математика: логика, группы, графы. – 2-е изд., доп. – М.:Лаборатория Базовых Знаний, 2003.
Березина Л.Ю. Графы и их применение: пособие для учителей. – М.: Просвещение,1979.
Гончарова Г.А., Мочалин А.А Элементы дискретной математики: Учебноепособие. – М.:ФОРУМ: ИНФРА-М, 2004.
Елисеев Е.М., Елисеев М.Е. Элементы дискретной математики. Учебное пособие. –Арзамас, АГПИим. А. П. Гайдара, 2003.
Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб.пособие. – М.:Лаборатория Базовых Знаний, 2002.
Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2002.
Р. Хаггарти. Дискретная математика для программистов. – М.: Техносфера, 2004.
Редькин .П. Дискретная математика: Курс лекций для студентов-механиков. –СПб.:Издательство «Лань», 2003.
Роганов Е.А. Информатика и математика: Конспект лекций. – М.: МГИУ, 2003.
Романовский И.В. Дискретный анализ. Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – Издание 2-е, исправленное. – СПб.: Невский диалект, 2000.
Яблонский С.В. Введение в дискретную математику: Учеб. Пособие для вузов. – 4-е изд., стер. – М.: Высшшк.; 2003.
Реализация программы учебной дисциплины требует дополнительного обеспечения специальных условий обучения лиц с ограниченными возможностями здоровья:
Контроль и оценка результатов освоения дисциплины осуществляется преподавателем в процессе проведения практических занятий, контрольных работ, тестирования.
Результаты обучения (освоенные умения, усвоенные знания) | Формы и методы контроля и оценки результатов обучения |
умения: |
строить таблицы истинности для формул логики; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
представлять булевы функции в видеформул заданного типа; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
выполнять операции над множествами,применять аппарат теории множеств длярешения задач; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
выполнять операции над предикатами; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
исследовать бинарные отношения назаданные свойства; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
выполнять операции над отображениями иподстановками; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
выполнять операции в алгебре вычетов; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
применять простейшиекриптографические шифры дляшифрования текстов; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
генерировать основные комбинаторныеобъекты; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
находить характеристики графов; | Индивидуальный опрос на занятии.Оценка домашней самостоятельной работы.Практическая работа. |
знания: |
логические операции, формулы логики, законы алгебры логики; | тестовые задания открытой формы, контрольная работа |
основные классы функций, полноту множеств функций, теорему Поста; | тестовые задания открытой формы, контрольная работа |
основные понятия теории множеств, теоретико-множественные операции и их связь с логическими операциями; | тестовые задания открытой формы, контрольная работа |
логику предикатов, бинарные отношения и их виды; | тестовые задания открытой формы, контрольная работа |
элементы теории отображений и алгебры подстановок; | тестовые задания открытой формы, контрольная работа |
основы алгебры вычетов и их приложение к простейшим криптографическим шифрам; | тестовые задания открытой формы, контрольная работа |
метод математической индукции; | тестовые задания открытой формы, контрольная работа |
алгоритмическое перечисление основных комбинаторных объектов; | тестовые задания открытой формы, контрольная работа |
основы теории графов; | тестовые задания открытой формы, контрольная работа |
элементы теории автоматов. | тестовые задания открытой формы, контрольная работа |