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

Муромский институт (филиал)

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

 «Владимирский государственный университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

(МИ ВлГУ)

 

Кафедра  ИС 

 

 

 

«   11   »       04       2015 г.

 

 

 

 

Рабочая программа ДИСЦИПЛИНЫ

 

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

 




Направление подготовки

09.03.03 Прикладная информатика

Профиль подготовки

Квалификация (степень)выпускника

бакалавр









          

Семестр

Трудоем-кость,

час. / зач. ед.

Лек-ции,

час.

 

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

час.

Лабора-торные работы,

час.

Консуль-тация,

час.

Конт-роль,

час.

Всего (контак-тная работа),

час.

СРС,

час.

Форма

промежу-точного контр.

(экз., зач., зач. с оц.)

2

216 / 6  

32  

32  

32  

5,2  

0,35  

101,55  

87,8  

Экз.(26,65)  

Итого

216 / 6  

32  

32  

32  

5,2  

0,35  

101,55  

87,8  

26,65  

 

Муром, 2015 г.


1. Цель освоения дисциплины

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

Задачи изучения дисциплины:

- освоить теоретические основы дискретной математики;

- получить практические навыки решения задач дискретной математики.

2. Место дисциплины в структуре ОПОП ВО (Цикл (Б1.Б.07))

Дисциплина Дискретная математика связана с такими дисциплинами как Основы теории алгоритмов, Теория информации, Информатика и программирование, Моделирование информационных процессов и систем.

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

ПК-23 способность применять системный подход и математические методы в формализации решения прикладных задач.

 

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

1) Знать:

Алгоритмы решения типовых задач теории множеств, математической логики, теории графов, комбинаторики, области и способы их применения (ПК-23).

2) Уметь:

Применять стандартные алгоритмы в соответствующих областях (ПК-23).

 


4. Структура и содержание дисциплины

Общая трудоемкость дисциплины составляет 6 зачетных единиц, 216 часов.

 

4.1. Форма обучения: очная

Уровень базового образования: среднее общее.

Срок обучения 4г.

 

4.1.1. Структура дисциплины


 

Раздел (тема)

дисциплины

 

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость

(в часах)

 

Форма  текущего контроля успеваемости (по неделям семестра), форма промежуточной аттестации

  (по семестрам)

 

п\п

Семестр

Лекции

Семинары

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

Лабораторные работы

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

СРС

КП / КР

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

Контроль

1

Теория множеств

2

8

4

8

21

Устный опрос, тестирование

2

Математическая логика

2

12

14

12

21

Устный опрос, тестирование

3

Теория графов

2

8

6

12

21,2

Устный опрос, тестирование

4

Комбинаторика

2

2

2

2,8

Устный опрос, тестирование

5

Теория алгоритмов

2

2

6

21,8

Устный опрос, тестирование

Всего за  семестр

216

32

32

32

87,8

5,2

0,35

Экз.(26,65)

Итого   

216

32

32

32

87,8

5,2

0,35

26,65

 

4.1.2. Содержание дисциплины

4.1.2.1. Перечень лекций

Семестр 2

Раздел 1. Теория множеств

Лекция 1.

Множества и способы задания множеств (2 часа).

Лекция 2.

Операции на множествах и их свойства (2 часа).

Лекция 3.

Соответствия и функции (2 часа).

Лекция 4.

Отношения (2 часа).

Раздел 2. Математическая логика

Лекция 5.

Основные понятия математической логики (2 часа).

Лекция 6.

Формулы и логические функции (2 часа).

Лекция 7.

Нормальные формы логических формул (2 часа).

Лекция 8.

Булева алгебра и алгебра Жегалкина (2 часа).

Лекция 9.

Язык логики предикатов (2 часа).

Лекция 10.

Переключательные схемы (2 часа).

Раздел 3. Теория графов

Лекция 11.

Основные понятия теории графов (2 часа).

Лекция 12.

Пути и связность в графах (2 часа).

Лекция 13.

Деревья (2 часа).

Лекция 14.

Алгоритмы на графах (2 часа).

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

Лекция 15.

Элементы комбинаторики (2 часа).

Раздел 5. Теория алгоритмов

Лекция 16.

Основные понятия теории графов (2 часа).

 

4.1.2.2. Перечень практических занятий

Семестр 2

Раздел 1. Теория множеств

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

Понятие множества. Способы задания множеств (2 часа).

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

Отношения (2 часа).

Раздел 2. Математическая логика

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

Логические функции (2 часа).

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

Дизъюнктивная и конъюнктивная нормальные формы (ДНФ и КНФ) (2 часа).

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

Полином Жегалкина (2 часа).

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

Синтез логических схем (2 часа).

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

Базис и-не, или-не (2 часа).

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

Логика предикатов. Кванторы (2 часа).

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

Предваренная (префиксная) нормальная форма (2 часа).

Раздел 3. Теория графов

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

Графы. способы задания графов (2 часа).

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

Пути и связность в неориентированных графах (2 часа).

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

Пути и связность в ориентированных графах (2 часа).

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

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

Комбинаторика (2 часа).

Раздел 5. Теория алгоритмов

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

Теория алгоритмов. Машины Тьюринга (2 часа).

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

Нормальные алгоритмы Маркова (2 часа).

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

Основные понятия теории алгоритмов (2 часа).

 

Методические указания для практических занятий приведены в https://www.mivlgu.ru/iop/course/view.php?id=267

 

4.1.2.3. Перечень лабораторных работ

Семестр 2

Раздел 1. Теория множеств

Лабораторная 1.

Операции над множествами (4 часа).

Лабораторная 2.

Соответствия и функции (4 часа).

Раздел 2. Математическая логика

Лабораторная 3.

Свойства логических операций (4 часа).

Лабораторная 4.

Совершенные ДНФ и КНФ (СДНФ и СКНФ) (4 часа).

Лабораторная 5.

Минимизация булевых функций с помощью карт Карно (4 часа).

Раздел 3. Теория графов

Лабораторная 6.

Обход графа. Алгоритмы поиска в глубину и ширину (4 часа).

Лабораторная 7.

Остов минимального веса (4 часа).

Лабораторная 8.

Кратчайшие пути на графах (4 часа).

 

Методические указания к лабораторным работам приведены в https://www.mivlgu.ru/iop/course/view.php?id=267

 

4.1.2.4. Перечень учебно-методического обеспечения для самостоятельной работы

Методические указания для самостоятельной работы размещены на информационно-образовательном портале института по ссылке https://www.mivlgu.ru/iop/course/view.php?id=5058.

Для самостоятельной работы также используются издания из списка приведенной ниже основной и дополнительной литературы.

Перечень тем, вынесенных на самостоятельное изучение:

1. Понятие алгебры. Фундаментальные алгебры.

2. Понятие модели. Алгебраическая система.

3. Покрытия и независимые множества.

4. Диаграммы Эйлера-Венна.

5. Основные тождества алгебры множеств.

6. Свойства бинарных отношений.

7. Эквивалентность и порядок.

8. Операции над бинарными отношениями.

9. Проблемы минимизации булевых функций.

10. Порождение простых импликантов.

11. Алгоритм Куайна и Мак-Клоски.

12. Полнота и замкнутость систем логических функций.

13. Скулемовская стандартная форма.

14. Алгоритм унификации.

15. Цикломатика.

16. Планарность.

17. Разрешимые и неразрешимые проблемы.

18. Цепи Маркова.

19. Задача о коммивояжере.

20. Контактные схемы.

21. Гомеоморффизм графов.

22. Комбинационные устройства.

23. Синтез комбинационных схем.

24. Бином Ньютона.

 

4.1.2.5. Перечень тем контрольных работ, рефератов, ТР, РГР, РПР

Не планируется.

 

4.1.2.6. Примерный перечень тем курсовых работ (проектов)

Не планируется.

 


4. 2. Форма обучения: заочная

Уровень базового образования: среднее профессиональное.

Срок обучения 3г 6м.

 

Семестр

Трудоем-кость,

час. / зач. ед.

Лек-ции,

час.

 

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

час.

Лабора-торные работы, час.

Консуль-тация,

час.

Конт-роль,

час.

Всего (контак-тная работа),

час.

СРС,

час.

Форма

промежуточного контроля

(экз., зач., зач. с оц.)

2

216 / 6  

4  

6  

6  

2  

0,6  

18,6  

188,75  

Экз.(8,65)  

Итого

216 / 6  

4  

6  

6  

2  

0,6  

18,6  

188,75  

8,65  

 

4.2.1. Структура дисциплины


 

Раздел (тема)

дисциплины

 

Виды учебной работы, включая самостоятельную работу студентов и трудоемкость

(в часах)

 

Форма  текущего контроля успеваемости (по неделям семестра), форма промежу-точной аттестации

  (по семестрам)

 

п\п

Семестр

Лекции

Семинары

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

Лабораторные работы

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

СРС

КП / КР

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

Контроль

1

Теория множеств

2

2

2

4

76

Устный опрос, тестирование

2

Математическая логика

2

2

2

58

Устный опрос, тестирование

3

Теория графов

2

2

2

54,75

Устный опрос, тестирование

Всего за  семестр

216

4

6

6

+

188,75

2

0,6

Экз.(8,65)

Итого   

216

4

6

6

188,75

2

0,6

8,65

 

4.2.2. Содержание дисциплины

4.2.2.1. Перечень лекций

Семестр 2

Раздел 1. Теория множеств

Лекция 1.

Множества и способы задания множеств. Операции на множествах и их свойства (2 часа).

Раздел 2. Математическая логика

Лекция 2.

Основные понятия математической логики. Формулы и логические функции (2 часа).

 

4.2.2.2. Перечень практических занятий

Семестр 2

Раздел 1. Теория множеств

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

Понятие множества. Способы задания множеств (2 часа).

Раздел 2. Математическая логика

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

Логические функции (2 часа).

Раздел 3. Теория графов

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

Графы. Способы задания графов (2 часа).

 

4.2.2.3. Перечень лабораторных работ

Семестр 2

Раздел 1. Теория множеств

Лабораторная 1.

Операции над множествами (4 часа).

Раздел 2. Теория графов

Лабораторная 2.

Обход графа. Алгоритмы поиска в глубину и ширину (2 часа).

 

4.2.2.4. Перечень учебно-методического обеспечения для самостоятельной работы

Методические указания для самостоятельной работы размещены на информационно-образовательном портале института по ссылке https://www.mivlgu.ru/iop/course/view.php?id=5058.

Для самостоятельной работы также используются издания из списка приведенной ниже основной и дополнительной литературы.

Перечень тем, вынесенных на самостоятельное изучение:

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. Задача о коммивояжере.

34. Контактные схемы.

35. Гомеоморффизм графов.

 

4.2.2.5. Перечень тем контрольных работ, рефератов, ТР, РГР, РПР

1. Отношения.

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

3. Полином Жегалкина.

4. Синтез логических схем.

5. Базис и-не, или-не.

6. Логика предикатов. Кванторы.

7. Предваренная (префиксная) нормальная форма.

8. Пути и связность в неориентированных графах.

9. Пути и связность в ориентированных графах.

10. Комбинаторика.

11. Теория алгоритмов. Машины Тьюринга.

12. Нормальные алгоритмы Маркова.

13. Основные понятия теории алгоритмов.

14. Соответствия и функции.

15. Свойства логических операций.

16. Совершенные ДНФ и КНФ (СДНФ и СКНФ).

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

18. Остов минимального веса.

19. Кратчайшие пути на графах.

 

4.2.2.6. Примерный перечень тем курсовых работ (проектов)

Не планируется.

 

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

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

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

 

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

Фонды оценочных средств приведены в приложении.

 

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

7.1. Основная учебно-методическая литература по дисциплине

1. Ковалёва Л.Ф. Дискретная математика в задачах: учебное пособие / Ковалёва Л.Ф. — М.: Евразийский открытый институт, 2011. — 142 c. - http://www.iprbookshop.ru/12467&book_id=10660

2. Громов Ю.Ю. Дискретная математика: учебное пособие / Ю.Ю. Громов, О.Г. Иванова, Ю.В. Кулаков, В.А. Гриднев, В.Г. Однолько. - Тамбов: Изд-во ФГБОУ ВПО "ТГТУ", 2012. - 128 с. - http://window.edu.ru/resource/070/80070/files/gromov.pdf

3. Агарева О.Ю. Дискретная математика: Учебное пособие. - М.: МАТИ, 2012. - 58 с. - http://window.edu.ru/resource/896/76896/files/discr.pdf

4. Алексеев В.Е., Киселева Л.Г., Смирнова Т.Г. Сборник задач по дискретной математике. Электронное учебно-методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2012. - 80 с. - http://window.edu.ru/resource/151/79151/files/alekseev.pdf

 

7.2. Дополнительная учебно-методическая литература по дисциплине

1. Павленкова Е.В., Чекмарев Д.Т. Сборник заданий по дискретной математике. Электронное учебно-методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2012. - 68 с. - http://window.edu.ru/resource/286/79286/files/DiscreteMath.pdf

2. Зарипова Э.Р., Кокотчикова М.Г., Севастьянов Л.А. Лекции по дискретной математике: Учебное пособие. Математическая логика. - М.: РУДН, 2011. - 79 с. - http://window.edu.ru/resource/615/73615/files/mathlogic-2011.pdf

3. Бернюков, А.К. Избранные главы дискретной математики: учеб. пособие / А.К. Бернюков; Владим. гос. ун-т. – Владимир: Изд-во Владим. гос. ун-та, 2009. – 108 c. - http://e.lib.vlsu.ru/bitstream/123456789/1432/3/00938.pdf

4. Довгий П.С., Поляков В.И. Учебно-методическое пособие по выполнению домашних заданий по дисциплине "Дискретная математика". АРИФМЕТИЧЕСКИЕ ОСНОВЫ ЭВМ. - 2010. - 56 с. - http://books.ifmo.ru/file/pdf/638.pdf

 

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

В образовательном процессе используются информационные технологии, реализованные на основе информационно-образовательного портала института (www.mivlgu.ru/iop), и инфокоммуникационной сети института:

- предоставление учебно-методических материалов в электроном виде;

- взаимодействие участников образовательного процесса через локальную сеть института и Интернет;

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

Информационные справочные системы:

1. Электронно-библиотечная система BOOK.ru (https://www.book.ru).

2. Электронно-библиотечная система ibooks.ru (http://ibooks.ru).

3. Электронно-библиотечная система IPRBooks (http://www.iprbookshop.ru).

4. Сеть разработчиков Microsoft - MSDN (http://msdn.microsoft.com).

5. Единое окно доступа к образовательным ресурсам (window.edu.ru).

6. Учебные издания НИУ ИТМО (http://books.ifmo.ru).

7. Электронная библиотека ВлГУ (http://e.lib.vlsu.ru).

Программное обеспечение:

не предусмотрено

 

7.4. Перечень ресурсов информационно-телекоммуникационной сети «Интернет», необходимых для освоения дисциплины

iprbookshop.ru

window.edu.ru

e.lib.vlsu.ru

books.ifmo.ru

 

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

Лекционная аудитория.

Лаборатория ГИС и САПР:

Сервер на базе 2 процессоров Intel Xeon;

12 персональных компьютеров;

проектор Sanyo PDG-DSU20;

экран настенный Drapper Apex Star.

 

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

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

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

 


лист_утверждения


РЕЦЕНЗИЯ

на  рабочую программу дисциплины

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

по направлению подготовки 09.03.03 Прикладная информатика

 

Рабочая программа дисциплины «Дискретная математика» составлена в соответствии с требованиями федерального государственного образовательного стандарта по направлению подготовки 09.03.03 Прикладная информатика.

На изучение данного курса по учебному плану отводится 216 час. (6 ЗЕТ). Формой итогового контроля изучения дисциплины является экзамен .

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

Задачи изучения дисциплины:

- освоить теоретические основы дискретной математики;

- получить практические навыки решения задач дискретной математики.

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

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

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

Перечень учебно-методической литературы достаточен для изучения дисциплины. Имеются ссылки на электронно-библиотечные системы.

Рабочая программа дисциплины «Дискретная математика» рекомендуется для использования в учебном процессе по направлению подготовки 09.03.03 Прикладная информатика.

 

11.04.2015 г.