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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

высшего образования

«МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ ИМЕНИ К.Г. РАЗУМОВСКОГО

(Первый казачий университет)»

(ФГБОУ ВО «МГУТУ ИМ. К.Г. РАЗУМОВСКОГО (ПКУ)»)

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

ДИСКРЕТНАЯ МАТЕМАТИКА

__________________________________________________________________________________________________________________________

(наименование дисциплины (модуля))

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

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. Объем дисциплины в зачетных единицах

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

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

6.1. Содержание разделов дисциплины:

Тема № 1. Теория множеств

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

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

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

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

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

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

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

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. Зуев Ю.А. Лекции по дискретной математики. – М.: МГУТУ, 2004.

5. Математика для экономистов: от Арифметики до Эконометрики: учебно-справочное пособие для бакалавров / под ред. Н.Ш. Кремера.- 3-е изд., перераб. и доп.- М.: Юрайт, 2012.- 685 с. Гриф.

8. Методические указания для студентов по освоению дисциплины

Работа с учебной литературой

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

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

Особое внимание следует обратить на определение основных понятий курса. Студент должен подробно разбирать примеры, которые поясняют такие определения, и уметь строить аналогичные примеры самостоятельно. Нужно добиваться точного представления о том, что изучаешь. Полезно составлять опорные конспекты.

Самопроверка

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

Консультации

Если в процессе самостоятельной работы над изучением теоретического материала или при решении задач у студента возникают вопросы, разрешить которые самостоятельно не удается, необходимо обратиться к преподавателю для получения у него разъяснений или указаний. В своих вопросах студент должен четко выразить, в чем он испытывает затруднения, характер этого затруднения. За консультацией следует обращаться и в случае, если возникнут сомнения в правильности ответов на вопросы самопроверки.

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

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

9. Основные образовательные технологии

Для достижения поставленных целей преподавания дисциплины реализуются следующие средства, способы и организационные мероприятия:

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

самостоятельное изучение теоретического материала дисциплины с использованием Internet-ресурсов, методических разработок, специальной учебной и научной литературы;

закрепление теоретического материала при проведении практических работ, выполнение проблемно-ориентированных, творческих заданий.

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

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

Эффективность учебного процесса достигается при комплексном применении в качестве средств обучения информационно-методического обеспечения и управления учебным процессом; информационно-поисковой деятельности; автоматизации процессов контроля, коррекции результатов учебной деятельности; отработки навыков и умений самостоятельно решать разного рода задачи по изучаемому предмету.

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

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

10. Требования к результатам освоения дисциплины

Оценочные средства для промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов.

Фонды оценочных средств, для оценки

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

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

Оценка «зачтено» ставится на зачете студентам, которые успешно освоили материал дисциплины и выполнили практические работы согласно плану изучения дисциплины.

Оценка «не зачтено» ставятся студенту, имеющему существенные пробелы в знании основного материала по программе, не выполнившему практические задания, а также допустившему принципиальные ошибки при изложении материала на зачете.

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

для лиц с ограниченными возможностями

Организация образовательного процесса для лиц с ограниченными возможностями осуществляется в соответствии с «Методическими рекомендациями по организации образовательного процесса для инвалидов и лиц с ограниченными возможностями здоровья в образовательных организациях высшего образования, в том числе оснащенности образовательного процесса» Министерства образования и науки РФ от 08.04.2014г. № АК-44/05вн.

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

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

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

Формы контроля

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

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

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

1. Обеспечение полноты объема проверяемого учебного материала.

2. Обобщенный характер контрольных знаний.

3. Продуктивный, прикладной характер контрольных заданий.

4. Направленность содержания контрольных заданий на активизацию познавательной деятельности студентов.

Зачет.

Вопросы для промежуточной аттестации по дисциплине

1. Множества. Операции над множествами.

2. Свойства операций над множествами.

3. Системы множеств. Булеан и разбиение множеств.

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

5. Бинарные отношения и их свойства.

6. Отображение множеств. Эквивалентные множества.

7. Комбинаторика: перестановки, размещения, сочетания (без повтора)

8. Комбинаторика: перестановки, размещения, сочетания (с повтором)

9. Логические переменные и функции.

10. Логические функции одной и двух переменных.

11. Основные логические операции.

12. Булевы операции и булева алгебра.

13. Свойства булевых операций.

14. Виды булевых нормальных форм.

15. Способы минимизации булевых функций.

16. Базис и алгебра Жегалкина.

17. Представление функций полиномами Жегалкина.

18. Полные системы логических функций.

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

20. Операции над графами.

21. Задача обхода графов.

22. Понятие эйлерова и гамильтонова циклов.

23. Понятия маршрута, цепи и циклов в графе.

24. Количественные характеристики графа: ранг и цикломатическое число.

25. Базисные циклы и разрезы в графе.

26. Нахождение кратчайших маршрутов в графе.

27. Маршруты в ориентированных и неориентированных графах. Связность. Достижимость.

28. Дерево. Основные свойства деревьев. Ориентированное дерево. Бинарные деревья. Остов.

29. Задача о построении кратчайшего остовного дерева. Алгоритм Прима

30. Задача о построении дерева кратчайших расстояний. Алгоритм Дейкстры. Алгоритм Флойда.

31. Сеть. Поток в сети. Задача о максимальном потоке в сети. Разрез.

32. Остаточная пропускная способность. Остаточная сеть. Алгоритм Форда – Фалкерсона нахождения максимального потока.

33. Задача коммивояжёра. Метод ветвей и границ.

Примерная балльно-рейтинговая карта по дисциплине

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

Максимальный балл

Зачетный балл

Посещение лекций

30

15

Работа на практических занятиях

30

20

Текущий контроль

10

5

Промежуточная аттекстация – зачет

30

15

Итого по дисциплине:

100

55

11. Материально-техническая база, необходимая для

осуществления образовательного процесса по дисциплине

Учебная аудитория

Оснащена переносным экраном, мультимедийным проектором, ноутбуком, выходом в интернет.

12. Составитель

Заворотний Анатолий Анатольевич - старший преподаватель кафедры естественнонаучных и технических дисциплин ЛКИПТ (филиал МГУТУ им. К.Г. Разумовского (ПКУ) в г. Липецке).