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

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

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

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

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

(МИ ВлГУ)

 

Кафедра  ЭиВТ 

 

 

 

«   24   »       02       2016 г.

 

 

 

 

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

 

     Дискретные структуры данных     

 




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

09.03.01 Информатика и вычислительная техника

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

"Вычислительные машины, комплексы, системы и сети"

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

бакалавр








          

Семестр

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

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

Лек-ции,

час.

 

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

час.

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

час.

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

час.

Конт-роль,

час.

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

час.

СРС,

час.

Форма

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

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

2

72 / 2  

16  

 

16  

1,6  

0,25  

33,85  

38,15  

Зач.  

3

180 / 5  

16  

18  

 

3,6  

0,35  

37,95  

115,4  

Экз.(26,65)  

Итого

252 / 7  

32  

18  

16  

5,2  

0,6  

71,8  

153,55  

26,65  

 

Муром, 2016 г.


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

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

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

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

Курс базируется на знаниях, полученных студентами в области математических и естественно-научных дисциплин. Базовые дисциплины: «Информатика», «Математика», «Математическая логика и теория алгоритмов». Углубление и расширение вопросов, изложенных в данном курсе, будет осуществляться во время работы студентов над дисциплинами: «Теория автоматов», «Программирование».

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

ОПК-2 способность осваивать методики использования программных средств для решения практических задач.

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

 

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

1) Знать:

сферы деятельности, в которых возникают задачи, связанные с дискретными моделями (ОПК-2).

основные операции с дискретными мат. объектами (множествами, графами, логическими функции) (ОПК-5).

2) Уметь:

использовать мат. пакеты для моделирования дискретных мат. объектов (ОПК-2).

выполнять операции над множествами, графами, решать типовые задачи (ОПК-5).

пользоваться методами дискретного моделирования для решения прикладных задач (ОПК-5).

3) Владеть:

навыками решения задач дискретного моделирования, в том числе и с использованием инструментальных средств (ОПК-2).

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

 


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

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

 

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

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

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

 

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


 

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

дисциплины

 

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

(в часах)

 

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

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

 

п\п

Семестр

Лекции

Семинары

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

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

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

СРС

КП / КР

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

Контроль

1

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

2

6

4

10

тестирование, отчет по лабораторной работе

2

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

2

4

4

10

тестирование, отчет по лабораторной работе

3

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

2

6

8

18,15

тестирование, отчеты по лабораторным и практическим работам

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

72

16

16

38,15

1,6

0,25

Зач.

4

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

3

8

10

49

тестирование, отчет по практической работе

5

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

3

8

8

66,4

тестирование, отчет по практической работе

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

180

16

18

115,4

3,6

0,35

Экз.(26,65)

Итого   

252

32

18

16

153,55

5,2

0,6

26,65

 

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

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

Семестр 2

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

Лекция 1.

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

Лекция 2.

Перестановки. Сочетания (2 часа).

Лекция 3.

Принцип включений и исключений в комбинаторике (2 часа).

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

Лекция 4.

Кодирование информации. Коды с определением ошибки (2 часа).

Лекция 5.

Статистические характеристики кодирования (2 часа).

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

Лекция 6.

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

Лекция 7.

Бесконечные множества и их свойства (2 часа).

Лекция 8.

Связи между элементами множеств. Отношения (2 часа).

Семестр 3

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

Лекция 9.

Приложения бинарных отношений (2 часа).

Лекция 10.

Начальные понятия и определения логики высказываний (2 часа).

Лекция 11.

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

Лекция 12.

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

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

Лекция 13.

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

Лекция 14.

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

Лекция 15.

Разбиение графа. Алгоритмы разбиения графа (2 часа).

Лекция 16.

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

 

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

Семестр 3

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

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

Теория множеств. Отношения. Отображения. Функции (2 часа).

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

Операции булевой алгебры (2 часа).

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

Переключательные функции и их минимизация (2 часа).

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

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

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

Коды с обнаружением и исправлением ошибок (2 часа).

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

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

Определение числа сочетаний и перестановок (2 часа).

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

Метрические характеристики графов. Определение базиса циклов и коциклов (2 часа).

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

Построение дерева минимальной длины (2 часа).

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

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

 

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

 

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

Семестр 2

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

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

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

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

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

Генерирование графов (4 часа).

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

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

Алгоритмы разрезания графа (4 часа).

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

Деревья. Циклы и коциклы. Раскраска графа (4 часа).

 

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

 

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. Математическое изучение алфавитного кодирования. Проблема взаимной однозначности.

 

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

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

 

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

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

 

 

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

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

 

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

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

 

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

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

1. Дискретная математика: Учебник для вузов./ Новиков Ф.А., СПб: Питер, 2017. - 496 - http://ibooks.ru/product.php?productid=354021

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

3. Дискретная математика. Графы и множества: Практикум/ сост. Кропотов Ю.А. [Электронный ресурс]. - Муром.: МИ ВлГУ, 2016. - http://elib.mivlgu.local/index.php?mod=book_inf&com=view_inf&book_id=2840

4. Дискретная математика. Системы кодирования и представления дискретных структур: Практикум для студентов образовательной / сост. Кропотов Ю.А. [Электронный ресурс]. - Муром.: МИ ВлГУ, 2016. - http://elib.mivlgu.local/index.php?mod=book_inf&com=view_inf&book_id=2851

 

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

1. Ковалёва Л.Ф. Дискретная математика в задачах [Электронный ресурс]: учебное пособие/ Ковалёва Л.Ф.— Электрон. текстовые данные.— М.: Евразийский открытый институт, 2011.— 142 c.— Режим доступа: http://www.iprbookshop.ru/10660.— ЭБС «IPRbooks», по паролю - http://www.iprbookshop.ru/10660

2. Введение в теорию графов. Индивидуальные задания : учебное пособие / Е.К. Годунова. — Москва : Прометей, 2012. — 44 с. - https://www.book.ru/book/911649

3. Шапорев, С.Д. Дискретная математика. Курс лекций и практических занятий. – СПб.: БХВ-Петербург, 2007. – 400 с.: ил. 15 экз. - 15 экз.

4. Дискретная математика: методические указания к практическим занятиям / сост. Г.П. Суворова, Н.Е. Холкина. – Муром: ИПЦ МИ ВлГУ, 2009. – 60 с. - 70 экз.

5. Дискретная математика: методические указания к лабораторному практикуму / МИ ВлГУ; сост. Г.П. Суворова, Н.Е. Холкина. – Муром: ИПЦ МИ ВлГУ, 2009. – 60 с. - 70 экз.

 

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

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

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

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

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

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

Информационно-образовательный портал МИ ВлГУ https://www.mivlgu.ru/iop/

Курс: Дискретная математика http://www.intuit.ru/studies/courses/1049/317/info

Курс:Введение в теорию множеств и комбинаторику http://www.intuit.ru/studies/courses/1035/240/info

Курс: Графы и их применение http://www.intuit.ru/studies/courses/58/58/info

Курс: Графы и алгоритмы http://www.intuit.ru/studies/courses/101/101/info

Электронная библиотека «ЭВРИКА» http://elib.mivlgu.local/

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

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

Лаборатория сетевых технологий и систем пространственного позиционирования

Система для математических вычислений: MathCad Education-University Edition (100 pack) (Государственный контракт №1 от 10.01.2012 года (с ООО «СофтЛайн Проекты»);

Среда программирования Visual Studio (подписка DreamSpark Premium Electronic Software; Delivery (3 year) Renewal, договор №453 от 16.12.2014 года);

 

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

ibooks.ru

window.edu.ru

elib.mivlgu.local

iprbookshop.ru

book.ru

 

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

Лаборатория сетевых технологий и систем пространственного позиционирования

Компьютер Kraftway Credo KC 36 - 12 шт.; проектор NEC Projector NP40G; экран настенный.

 

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

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

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

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

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

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

 


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


РЕЦЕНЗИЯ

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

«Дискретные структуры данных»

по направлению подготовки 09.03.01 Информатика и вычислительная техника

 

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

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

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

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

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

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

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

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

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

 

24.02.2016 г.