Рабочая программа по дисциплине Дискретная математика для специальности Автоматизация технологических процессов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение
высшего образования
«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ ИМЕНИ К.Г. РАЗУМОВСКОГО
(Первый казачий университет)»
(ФГБОУ ВО «МГУТУ ИМ. К.Г. РАЗУМОВСКОГО (ПКУ)»)




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

ДИСКРЕТНАЯ МАТЕМАТИКА
__________________________________________________________________________________________________________________________
(наименование дисциплины (модуля))


По направлению подготовки (специальности):

15.03.04, Автоматизация технологических процессов и производств
___________________________________________________________________________________________________________________________________________________________________________________________
(код, наименование)

Профиль подготовки (специализация):


________________________________________________________________________________________________________________________________________

Квалификация выпускника

бакалавр
_______________________________________________________________________________________
(специалист, бакалавр, магистр)


Одобрено на заседании кафедры Естественнонаучных и технических дисциплин Липецкого казачего института пищевых технологий (филиал ФГБОУ ВО «МГУТУ им. К.Г. Разумовского (ПКУ) в г. Липецке)

(протокол №___ от __________ 20___ г.)

Зав. кафедрой _____________ (Борков В.П.)




Липецк 20___
Рабочая учебная программа дисциплины составлена в соответствии с требованиями ФГОС ВПО, утвержденного приказом Министерства образования и науки Российской Федерации и учебным планом, утвержденным Ученым советом университета от _01_._09__.2014г., протокол №_1_.
Рабочая программа дисциплины обсуждена и рекомендована к утверждению решением УМС ФГБОУ ВО «МГУТУ им. К.Г. Разумовского (ПКУ)» от «_01_» ___09____ 2014 г., протокол №1.


Председатель УМС Г.П. Капица
















2. Цель изучения дисциплины

Целями преподавания дисциплины являются:
формирование фундаментальных знаний у студентов при изучении вопросов теоретико-множественного описания математических объектов, основных проблем теории графов и методологии использования аппарата математической логики, составляющих теоретический фундамент описания функциональных систем;
приобретение навыков решения основных задач по ряду разделов дискретной математики: теория множеств и отношения на множествах, теория графов, функции алгебры логики, комбинаторика;
приобретение навыков самостоятельного изучения отдельных тем дисциплины и решения типовых задач;
усвоение полученных знаний студентами, а также формирование у них мотивации к самообразованию за счет активизации их познавательной деятельности.
Поставленные цели полностью соответствуют целям ООП.

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

В результате освоения дисциплины студент будет:
Знать:

· способы задания множеств, основные операции над ними, отношения между элементами множеств, их свойства и виды отношений;
теоремы и формулы комбинаторики, основные приемы и методы решения комбинаторных задач;

· отображения и функции, виды отображений, основные операции над отображениями;

· основные комбинаторные конфигурации, метод включения-исключения;

· основные понятия теории графов, связные графы, изоморфизм графов;

· методы решения экстремальных задач на графах, алгоритмы раскраски вершин и ребер графа.
Уметь:

· употреблять специальную математическую символику для выражения количественных и качественных отношений между объектами;

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

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

· решать оптимизационные задачи на графах.
Владеть:

· практическим опытом решения задач теории множеств, математической логики комбинаторных и теоретико-графовых задач;

· навыками применения языка и средств дискретной математики.

4. Место дисциплины в структуре образовательной программы, в модульной структуре ОП

Дисциплина «Дискретная математика» (Б2.ДВ1.1) относится к базовой части профессионального цикла дисциплин ООП.
Пререквизитами данной дисциплины являются дисциплины математического и естественнонаучного цикла (Б2): «Математический анализ» (Б2.Б1.1), «Геометрия и алгебра» (Б2.Б1.2).
Для изучения дисциплины «Дискретная математика» студент должен:
Знать:

· основы математического анализа, алгебры и геометрии;

· современные тенденции развития информатики и вычислительной техники, компьютерных технологий.
Уметь:

· применять математические методы и вычислительную технику для решения практических задач;

· программировать на одном из алгоритмических языков;

· проводить сравнительный анализ параметров.
Владеть:

· элементами математического анализа;

· основами алгоритмизации.
При изучении дисциплины бакалавры должны изучить общие принципы теоретико-множественного описания математических объектов, основные проблемы теории графов и методологию использования аппарата математической логики; основные приемы и формулы комбинаторики; знать способы задания множеств, булевых функций и графов, а также основные методы оперирования с ними; выбирать оптимальные методики при решении задач теории множеств, математической логики и теории графов.
Соответствие результатов освоения дисциплины «Дискретная математика» формируемым компетенциям ООП представлено в таблице

Результат обучения
Код
Знания
Код
Умения
Код
Владения

Р6
З.6.1
Теоретические основы теории множеств; комбинаторики; математической логики, теории графов
У.6.1
Выполнять операции над множествами, применять аппарат теории множеств для решения задач, решать задачи с применением комбинаторных формул; исследовать бинарные отношения на заданные свойства
В.6.1
Навыками применения языка и средств дискретной математики



5. Объем дисциплины в зачетных единицах

№
Вид учебной работы
Трудоемкость в соответствии с учебным планом
Количество зачетных единиц






1
Аудиторные занятия:
14
0,4


Лекции
6
0,17


Практические занятия
6
0,17


Другие виды аудиторных работ
2
0,06

2
Самостоятельная работа:
92
2,6


Контрольная работа
4
0,11

3
Формы промежуточной
аттестации
2
0,06

4
Итого
108
3


Общее количество часов и фактическая трудоемкость дисциплины «Дискретная математика» приведено в таблице:

Дисциплина
Общая норматив. трудоемкость
Общая фактическая трудоемкость
Всего часов с преподавателем
СРС
Контроль (зач.)
ЗЕТ
ЗЕТ экспер.
ЗЕТ по плану
Часов в интерактив. форме




Лек.
Прак.







Дискрет. математика
108
108
6
6
92
4
3
3
3
2


6. Содержание дисциплины (модуля)

6.1. Содержание разделов дисциплины:
Тема № 1. Теория множеств

Понятие множества. Конечные и бесконечные множества. Способы задания множеств. Подмножества. Множество всех подмножеств данного множества. Определение мощности множества всех подмножеств конечного множества (с использованием формулы бинома Ньютона). Универсальное множество. Понятие алгебры. Алгебра множеств. Понятия алгебраических и кардинальных операций. Алгебраические операции над множествами. Законы алгебры множеств. Двойственность в алгебре множеств. Уравнения и системы уравнений в алгебре множеств. Основные леммы, используемые при решении уравнений в алгебре множеств. Мощность множества. Понятие счетного множества и континуума. Канторовская диагональная процедура. Примеры счетных множеств. Доказательство счетности множества алгебраических чисел. Свойства счетных множеств. Необходимые и достаточные условия бесконечности множества. Примеры континуальных множеств. Теорема Кантора-Бернштейна.

Тема № 2. Математическая логика

Высказывания. Операции над высказываниями. Алгебра логики. Табличный способ задания функций. Таблица истинности. Формулы и функции алгебры логики. О числе функций алгебры логики от n переменных. Равносильные формулы. Законы алгебры логики. Логические следствия. Проблема разрешимости в алгебре логики. Тавтологии и противоречия. Основные схемы доказательств: если x то y, доказательство от противного, доказательство построением цепочки импликаций, доказательство разбором случаев. Суперпозиция функций алгебры логики. Полные системы функций. Понятие базиса. Алгебра Жегалкина. Полином Жегалкина. Теорема Жегалкина. Замкнутые классы функций. Линейные функции. Монотонные функции. Теорема о монотонных функциях. Двойственность в алгебре высказываний. Самодвойственные функции. Функции, сохраняющие константы 0, 1. Теорема Поста о функциональной полноте.
Комбинаторные схемы с повторениями и без повторений, перестановки с повторениями, размещения с повторениями, сочетания с повторениями, перестановки без повторений, размещения без повторений, сочетания без повторений, бином Ньютона, полиномиальная формула.

Тема № 3. Теория графов

Основные понятия. Способы представления графов, перечисление графов. Матрицы инцидентности и смежности. Эйлеровы циклы. Теорема Эйлера. укладки графов. Укладка графов в трехмерном пространстве. Планарность. Формула Эйлера для плоских графов. Деревья и их свойства. Связность графа. Раскраска графа. Хроматическое число. Теорема о целочисленности. Задача о назначениях. Дискретные экстремальные задачи: алгоритм Краскаля нахождения минимального основного дерева. Методы определения крат-чайших путей в графе. Алгоритм Форда-Беллмана. Алгоритм Дейкстры.


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

Название раздела/темы
Аудиторная работа (час)
СРС
(час)
Перечень компетенций


Лекции
Практ./сем.
занятия







ОК-2
ОК-10
ОК-16
ОК-17
ОК-18
ПК 1
ПК 3
ПК 4
ПК 7
ПК 17

Тема 1. Теория множеств
2
 2
30
х
х
х
х
х
х

х

х

Тема 2. Математическая логика, комбинаторика
2
 2
30
х
х

х


х
х
х


Тема 3. Теория графов
2
2
32
х

х
х
х
х
х
х
х
х

Итого
6
6
92












7. Учебно-методическое и информационное обеспечение дисциплины

Основная:
1. Иванов Б.Н. Дискретная математика. Алгоритмы и программы. Полный курс. – М.: ФИЗМАТЛИТ, 2007.
2. Новиков Ф.А. Дискретная математика для программистов. - СПб: «Питер», 2008.
3. Данко, П.Е. Высшая математика в упражнениях и задачах. В 2-х ч. Ч. 1.: учебное пособие / П.Е. Данко, А.Г. Попов, Т.Я. Кожевникова.- 6-е изд.- М.: Оникс, 2006.- 304 с.: ил.
4. Данко, П.Е. Высшая математика в упражнениях и задачах. В 2-х ч. Ч. 2.: учебное пособие / П.Е. Данко, А.Г. Попов, Т.Я. Кожевникова.- 6-е изд.- М.: Оникс, 2005.- 416 с.: ил.
5. Владимирский, Б.М. Математика. Общий курс: учебник для вузов / Б.М. Владимирский.- 3-е изд., стер.- СПб.: Лань, 2006.- 960 с. Гриф.
Дополнительная:
1. Андерсон Д.А. Дискретная математика и комбинаторика. – М.: “Вильямс”, 2003.
2. Нефёдов В.Н., Осипова В.А. Курс дискретной математики. – М.: “МАИ”, 2002.
3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: “Наука”, 2004.
4. Зуев Ю.А.