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

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

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

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

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

(МИ ВлГУ)

 

Кафедра  ФПМ 

 

 

 

«   04   »       06       2019 г.

 

 

 

 

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

 

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

 




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

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

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

Интеллектуальный анализ данных

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

бакалавр









          

Семестр

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

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

Лек-ции,

час.

 

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

час.

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

час.

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

час.

Конт-роль,

час.

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

час.

СРС,

час.

Форма

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

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

1

288 / 8  

32  

30  

 

5,2  

0,35  

67,55  

166,8  

Экз.(53,65)  

Итого

288 / 8  

32  

30  

 

5,2  

0,35  

67,55  

166,8  

53,65  

 

Муром, 2019 г.


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

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

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

– формирование практических навыков в области дискретной математики, необходимых в профессиональной деятельности;

– развитие логического мышления;

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

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

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

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

ОПК-1 Способен применять фундаментальные знания, полученные в области математических и (или) естественных наук, и использовать их в профессиональной деятельности.

 

Результатом освоения дисциплины является достижение следующих индикаторов:

Знать основные понятия и методы специальных глав математики.

Уметь решать типовые примеры и задачи специальных глав математики.

 


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

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

 

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

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

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

 

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


 

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

дисциплины

 

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

(в часах)

 

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

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

 

п\п

Семестр

Лекции

Семинары

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

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

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

СРС

КП / КР

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

Контроль

1

Элементы математической логики

1

10

8

24

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

2

Множества и отображения

1

6

6

24

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

3

Элементы комбинаторного анализа

1

2

6

28

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

4

Элементы теории графов

1

12

6

58

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

5

Элементы теории кодирования

1

2

4

32,8

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

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

288

32

30

166,8

5,2

0,35

Экз.(53,65)

Итого   

288

32

30

166,8

5,2

0,35

53,65

 

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

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

Семестр 1

Раздел 1. Элементы математической логики

Лекция 1.

Введение в предмет дискретной математики. Дискретная математика и математическая кибернетика. Высказывания. Логические связки. Логические отношения. Свойства логических операций (2 часа).

Лекция 2.

Функции алгебры логики. Свойства элементарных булевых функций. Функции одной или двух переменых. Суперпозиция функций алгебры логики (2 часа).

Лекция 3.

Нормальные формы логических функций. Дизъюнктивные и конъюктивные нормальные формы алгебры высказываний (2 часа).

Лекция 4.

Совершенные дизъюнктивные и конъюктивные нормальные формы алгебры высказываний. Арифметические полиномы (2 часа).

Лекция 5.

Многочлены Жегалкина. Линейные функции и их свойства (2 часа).

Раздел 2. Множества и отображения

Лекция 6.

Основные понятия и определения теории множеств. Способы задания множеств. Подмножества. Операции над множествами. Соотношение между множествами и составными высказываниями. Операции над множествами (2 часа).

Лекция 7.

Диаграммы Эйлера-Венна. Свойства операций над множествами. Упорядоченные пары и прямое произведение множеств. Бинарные отношения. Теорема о свойствах бинарного отношения (2 часа).

Лекция 8.

Матрицы конечных бинарных отношений. Отображения множеств. Функции. Композиция функции и ее свойства. Ядро функции, свойства ядра (2 часа).

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

Лекция 9.

Основные правила комбинаторики. Комбинации элементов с повторениями. Бином Ньютона (2 часа).

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

Лекция 10.

Основные определения теории графов. Изоморфизм графов. Маршруты, цепи, циклы. Связность графа. Ориентированные графы. Плоские графы (2 часа).

Лекция 11.

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

Лекция 12.

Деревья и их свойства. Ориентированные, упорядоченные, бинарные деревья. Остовные деревья графа.. Минимальные остовные деревья. Алгоритм Краскала построения минимального остовного дерева. Алгоритм Дейкстры-Прима построения минимального остовного дерева (2 часа).

Лекция 13.

Задача о кратчайшем пути и алгоритм Дейкстры для ее решения. Алгоритм Беллмана решения задачи о кратчайшем пути. Теорема Форда. Алгоритм Флойда отыскания кратчайших путей (2 часа).

Лекция 14.

Гамильтоновы циклы и гамильтоновы графы. Теорема Дирака. Задача комивояжера и ее решение методом ветвей и границ (2 часа).

Лекция 15.

Эйлеровы циклы и эйлеровы графы. Критерий эйлеровости графов. Алгоритмы Флёри. Планарный (плоский) граф. Формула Эйлера. Критерий планарности графа (2 часа).

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

Лекция 16.

Кодирование как способ представления информации. Кодирование и декодирование. Помехоустойчивое кодирование. Алфавитное кодирование. Математическое изучение алфавитного кодирования. Проблема взаимной однозначности. Общий критерий взаимной однозначности. Двоичный алфавит (2 часа).

 

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

Семестр 1

Раздел 1. Элементы математической логики

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

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

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

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

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

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

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

Многочлены Жегалкина (2 часа).

Раздел 2. Множества и отображения

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

Множества и отображения (2 часа).

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

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

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

Диаграммы Эйлера-Венна (2 часа).

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

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

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

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

Комбинаторные формулы (2 часа).

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

Бином Ньютона (2 часа).

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

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

Элементы теории графов. Матрица смежности (2 часа).

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

Элементы теории графов. Матрица достижимости (2 часа).

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

Элементы теории графов. Матрица инциденции (2 часа).

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

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

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

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

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

 

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

 

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

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

 

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. Задачи размещения. Поиск центров и медиан в графе.

25. Связность графов. Теорема Холла.

26. Фундаментальные циклы и разрезы.

27. Независимые и покрывающие множества вершин и ребер.

28. Индуктивный граф.

29. Базы.

30. Ядра графа.

31. Полустепени исхода и захода.

32. Паросочетание простого графа.

33. Дефицит простого графа.

34. Венгерский алгорифм.

35. Факторы.

36. Нахождение фактора.

37. Центры графа.

38. Радиус графа.

39. Линейные циклические коды.

40. Порождающий (генераторный) полином.

41. Коды коррекции ошибок Рида — Соломона.

42. Преимущества и недостатки блоковых кодов.

43. Свёрточные коды.

44. Каскадное кодирование. Итеративное декодирование.

45. Сетевое кодирование.

46. Оценка эффективности кодов.

 

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

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

 

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

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

 

 

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

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

 

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

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

 

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

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

1. Дехтярь, М. И. Дискретная математика : учебное пособие / М. И. Дехтярь. — 3-е изд. — Москва : Интернет-Университет Информационных Технологий (ИНТУИТ), Ай Пи Ар Медиа, 2020. — 181 c. - https://www.iprbookshop.ru/94851.html

2. Горюшкин, А. П. Математическая логика и теория алгоритмов : учебник / А. П. Горюшкин. — Саратов : Вузовское образование, 2022. — 499 c. - https://www.iprbookshop.ru/117296.html

3. Велигура, А. Н. Комбинаторика и теория графов для кибербезопасности. Конспект лекций : учебное пособие / А. Н. Велигура. — Москва : Национальный исследовательский ядерный университет «МИФИ», 2021. — 200 c. - https://www.iprbookshop.ru/125492.html

4. Сагадеева, М. А. Теория графов : учебное пособие / М. А. Сагадеева. — 2-е изд. — Челябинск, Саратов : Южно-Уральский институт управления и экономики, Ай Пи Эр Медиа, 2019. — 143 c. - https://www.iprbookshop.ru/102006.html

 

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

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

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

 

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

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

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

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

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

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

Национальный открытый университет ИНТУИТ - http://www.intuit.ru/

Математический справочник - http://dict.sernam.ru/

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

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

 

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

iprbookshop.ru

dspace.www1.vlsu.ru

books.ifmo.ru

 

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

 

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

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

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

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

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

 


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


РЕЦЕНЗИЯ

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

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

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

 

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

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

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

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

– формирование практических навыков в области дискретной математики, необходимых в профессиональной деятельности;

– развитие логического мышления;

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

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

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

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

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

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

 

04.06.2019 г.