Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Московский государственный технический университет имени

(национальный исследовательский университет)»

Московский техникум космического приборостроения


РАБОЧАЯ ПРОГРАММА


учебной дисциплины

Дискретная математика


  код, специальности


09.02.01  Компьютерные системы и комплексы



Москва

2016


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

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

5
условия реализации РАБОЧЕЙ программы учебной дисциплины

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

14

СОДЕРЖАНИЕ



1. паспорт РАБОЧЕЙ ПРОГРАММЫ УЧЕБНОЙ ДИСЦИПЛИНЫ

Дискретная математика

1.1. Область применения программы

Реализация среднего (полного) общего образования в пределах  программы подготовки специалистов среднего звена (ППССЗ)  специальности 09.02.01 Компьютерные системы и комплексы.

Рабочая программа учебной дисциплины может быть использована в дополнительном профессиональном образовании (курсы повышения квалификации и переподготовки) и профессиональной подготовке.

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

Входит в профессиональный учебный цикл ППСЗ.

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

В результате освоения дисциплины обучающийся должен уметь:

У1- формулировать задачи логического характера и применять средства математической логики для их решения;

У2- применять законы алгебры логики;

У3- определять типы графов и давать их характеристики;

У4- строить простейшие автоматы;

В результате освоения дисциплины обучающийся должен знать:

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

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

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

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

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

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

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

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

З9- основные понятия теории графов, характеристики и виды графов;

З10- элементы теории автоматов;

1.4. Рекомендуемое количество часов на освоение программы дисциплины:

максимальной учебной нагрузки обучающегося 102 часов, в том числе:

обязательной аудиторной учебной нагрузки обучающегося 68 часа;

самостоятельной работы обучающегося 34 часа.

2. СТРУКТУРА И СОДЕРЖАНИЕ УЧЕБНОЙ ДИСЦИПЛИНЫ

2.1. Объем учебной дисциплины и виды учебной работы


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

НЕ нашли? Не то? Что вы ищете?

Объем часов

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

102

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

68

в том числе:

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

-

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

34

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

-

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

34

в том числе:

  Домашняя работа.

Проработка конспектов занятий, учебной литературы.

Оформление отчёта по практической работе.

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


2.2. Тематический план и содержание учебной дисциплины «Дискретная математика»

                       

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

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

Объем часов

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

1

2

3

4

Раздел 1. Логика высказываний

12

Тема 1.1. Логика высказываний.

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

4

2

1

Предмет и задачи дискретной математики. Связь дискретной математики с другими науками.

2

2

Введение в логику.

2

3

Понятие высказывания.

2

4

Логические операции над высказываниями. Отрицание. Конъюнкция. Дизъюнкция. Импликация. Эквиваленция. Порядок выполнения операций.

2

5

Формулы логики высказываний.

2

6

Построение таблиц истинности.

2

7

Тавтология(тождественно-истинная формула). Противоречие(тождественно-ложная формула).

2

8

Равносильные формулы.

2

9

Законы алгебры логики.

2

10

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

2

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

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

№2 «Упрощение формул логики с помощью равносильных преобразований»

4

2

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

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе.

4

2

Раздел 2. Основные понятия теории множеств

8

Тема 2.1.

Основные понятия теории множеств

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

4

1

Понятие множества по Кантору.

2

Способы задания множеств.

2

Подмножество, собственное подмножество, отношение включения, пустое множество, универсальное множество, дополнение.

2

Конечные и бесконечные множества. Количество подмножеств конечного множества. Парадокс Рассела.

2

Основные операции над множествами. Диаграммы Эйлера-Венна.

2

Свойства операций над множествами(идемпотентность объединения, пересечения, коммутативность объединения, пересечения, ассоциативность объединения, пересечения, дистрибутивность ).

2

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

2

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

2

Применение аппарата теории множеств к решению задач

2

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

№3 «Решение задач на выполнение теоретико-множественных операций и подсчет количества элементов»

2

2

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

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

2

2

Раздел 3. Логика предикатов.

6

Тема 3.1. Логика предикатов.

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

2

2

1

Понятие предиката.

2

2

Область определения и область истинности предиката.

2

3

Операции над предикатами.

2

4

Законы логики предикатов.

2

5

Свободные и связанные переменные

2

6

Кванторы. Квантор общности. Квантор существования.

2

7

Построение отрицаний к предикатам, содержащим кванторные операции

2

8

Запись высказываний на языке логики предикатов (перевод с естественного языка на формальный и обратно).

2

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

№4 «Выполнение операций над предикатами»

2

2

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

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

2

2

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

14

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

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

2

2

1

Множество всех подмножеств. Перестановки. Сочетания. Размещения. Перестановки с повторениями. Сочетания с повторениями.

2

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

«Генерирование комбинаторных объектов заданного типа»

2

2

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

-

-

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

2

2

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

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

2

2

1

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

2

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

№5 «Доказательство методом математической индукции»

4

2

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

-

-

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

2

2

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

22

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

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

8

2

1

Понятие графа.

2

2

Виды графов.

2

3

Способы задания графов.

2

4

Операции на графах

2

5

Путь в графе.

2

6

Связность.

2

7

Нахождение простых цепей.

2

8

Изоморфизм графов.

2

9

Эйлеровы графы. Нахождение эйлеровых циклов.

2

10

Взвешенные графы. Деревья. Остов графа. Минимальное остовное дерево.

2

11

Алгоритм Краскала и алгоритм Прима для построения минимального остовного дерева.

2

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

№6 «Определение вида графа. Проведение операций на графах»

№7 «Нахождение всех простых цепей в графе»

№8 «Проверка графа на эйлеровость. Нахождение эйлеровых циклов и полуэйлеровых цепей»

№9 «Нахождение остова минимального веса с помощью алгоритмов Краскала и Прима»

8

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

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

6

2

Раздел 6. Булевы функции.

10

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

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

4

2

1

Понятие булевой функции. Способы задания.

2

2

Понятие элементарной дизъюнкции, конъюнкции.

2

3

Дизъюнктивная нормальная форма (ДНФ)

2

4

Конъюнктивная нормальная форма (КНФ)

2

5

Понятие совершенной ДНФ.

2

6

Понятие совершенной КНФ.

2

7

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

2

8

Основные классы булевых функций.

2

9

Полнота множеств функций.

2

10

Замкнутые классы.

2

11

Теорема Поста.

2

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

№10 ««Представление булевой функции в виде совершенной ДНФ и КНФ, минимальной КНФ, полином Жегалкина»»

№11 «Проверка булевой функции на принадлежность к замкнутым классам, на полноту»

4

2

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

-

-

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

4

2

Раздел 7. Бинарные отношения и соответствия

6

Тема 7.1.

Бинарные отношения и их виды

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

2

2

1

Кортеж.

2

Прямое произведение множеств.

2

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

2

Область определения. Область значения.

2

Композиция. Инверсия. Расширение. Ограничение.

2

n-местное отношение. Представление бинарных отношений орграфами.

2

Некоторые виды бинарных отношений.

2

Отношение эквивалентности.

2

Класс эквивалентности.

2

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

Работа № 12 «Исследование бинарных отношений на рефлексивность, симметричность и транзитивность; выделение классов эквивалентности»

2

2

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

2

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

4

2

Раздел 8. Элементы  теории отображений и алгебры подстановок.

6

Тема 8.1. Элементы  теории отображений и алгебры подстановок.

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

2

2

1

Функции(отображения).

2

Область определения. Область значения. Образ. Прообраз.

2

Инъекция. Биекция. Сюръекция.

2

Композиция отображений.

2

Обратимые функции.

2

Подстановка или преобразование.

2

Формула количества подстановок

2

Циклическое разложение подстановок.

2

Обратная подстановка.

2

Степень подстановки.

2

Решение простейших уравнений в алгебре подстановок

2

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

№ 13 «Решение задач на запись циклического разложения подстановки; выполнение операций и решение простейших уравнений в алгебре подстановок»

2

2

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

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

2

2

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

12

Тема 9.1. Основы теории автоматов

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

4

2

1

Базовые множества для автомата: входной алфавит, выходной алфавит, множество состояний.

2

2

Таблица автомата

2

3

Принцип работы автомата.

2

4

Диаграмма автомата.

2

5

Словарная функция автомата. Финальная функция автомата.

2

6

Правильный автомат (автомат Мура)

2

7

Упрощенный вид диаграммы для правильных автоматов.

2

8

Автомат распознающий свойства слова и его построение

2

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

№ 14«Построение автомата, распознающего заданные свойства слова».

4

2

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

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

Проработка конспектов занятий, учебной литературы.

Выполнение домашнего задания.

Оформление отчета по практической работе

4

2

Всего:

108

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

Для характеристики уровня освоения учебного материала используются следующие обозначения:

1. – ознакомительный (узнавание ранее изученных объектов, свойств);

2. – репродуктивный (выполнение деятельности по образцу, инструкции или под руководством)

3. – продуктивный (планирование и самостоятельное выполнение деятельности, решение проблемных задач)

3. условия реализации программы дисциплины

3.1. Требования к минимальному материально-техническому обеспечению

Реализация программы дисциплины требует наличия учебного кабинета математики.

Оборудование учебного кабинета:

    посадочные места по количеству обучающихся; рабочее место преподавателя; комплект учебно-методической документации.

Технические средства обучения:

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

3.2. Информационное обеспечение обучения

Перечень рекомендуемых учебных изданий, Интернет-ресурсов, дополнительной литературы

Основные источники:


Прикладная дискретная математика. Логика. Графы. Автоматы. Алгоритмы. Кодирование.  – М.: Вузовская книга, 2011. – 507 с. , Математическая логика. Дискретные функции. Теория алгоритмов: учебное пособие для вузов – СПб.: Лань, 2012. – 405с. , Дискретная математика: учебник для вузов / , ; ред. - 3-е изд., испр. - М.: Академия, 2014. - 254 с.

Дополнительные источники:

, Теория графов: метод. указания к выполнению домашнего задания по курсу "Дискретная математика" / , ; МГТУ им. . - М.: Изд-во МГТУ им. , 2014. - 36 с. , , Математическая логика и теория алгоритмов: метод. указания к выполнению типового расчета / , , ; МГТУ им. . - М.: Изд-во МГТУ им. , 2011. - 43 с. , , Сборник задач по курсу "Дискретная математика" : метод. указания / , , ; МГТУ им. . - М.: Изд-во МГТУ им. , 2013. - 31 с. Задачник-практикум по математической логике. – М.: Издательский центр “Академия”, 2007. – 302с. , Задачи по теории множеств, математической логике и теории алгоритмов. – М.: ФИЗМАТЛИТ, 2004. – 256с. , Дискретная математика: учебник для втузов / , ; ред. , - 4-е изд., испр. - М.: Изд-во МГТУ им. , 2006. - 743 с. , Дискретная математика: М, Издательский центр Академия, 2007. – 367с. Шевелев, математика: учеб. пособие / . – СПб.: Лань, 2008. – 591 с.

Интернет-ресурсы:

1. , ``Элементы теории графов, схем и автоматов'' (учебное пособие для студентов) - М.: Издательский отдел ф-та ВМиК МГУ (лицензия ЛР N 040777 от 01.01.2001), 2000 г. - 58 с. http://212.cmc-msu. ru/files/kniga. html

3.3. Общие требования к организации образовательного процесса

Занятия проводятся в интерактивных формах, с использованием мультимедийного оборудования и учебных лабораторий.

Освоению данной дисциплины предшествуют дисциплины математического цикла.

4. Контроль и оценка результатов освоения УЧЕБНОЙ Дисциплины

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


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

Коды формируемых ОК  и ПК

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

1

2

3

Умения

У1- формулировать задачи логического характера и применять средства математической логики для их решения;

У2- применять законы алгебры логики;

У3- определять типы графов и давать их характеристики;

У4- строить простейшие автоматы.

ОК 1-9

ПК – 1.1, 1.3

1.индивидуальный опрос

2. самостоятельная работа,

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

4.практическая работа,

5. решение задач

6. комбинированный метод

7. устный зачёт

Знания

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

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

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

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

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

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

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

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

З9- основные понятия теории графов, характеристики и виды графов;

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

ОК 1-9

ПК – 1.1, 1.3

1.индивидуальный опрос

2. самостоятельная работа,

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

4.практическая работа,

5. решение задач

6. комбинированный метод

7. устный зачёт