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

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

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

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

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

(МИ ВлГУ)

 

Кафедра  ПИн 

 

 

 

«   06   »       06       2017 г.

 

 

 

 

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

 

     Структуры и алгоритмы обработки данных     

 




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

09.03.04 Программная инженерия

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

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

бакалавр









          

Семестр

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

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

Лек-ции,

час.

 

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

час.

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

час.

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

час.

Конт-роль,

час.

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

час.

СРС,

час.

Форма

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

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

3

108 / 3  

18  

 

24  

1,8  

0,25  

44,05  

63,95  

Зач.  

Итого

108 / 3  

18  

 

24  

1,8  

0,25  

44,05  

63,95  

 

 

Муром, 2017 г.


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

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

Задачи дисциплины:

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

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

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

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

ПК-20 способность оценивать временную и емкостную сложность программного обеспечения.

 

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

1) Знать:

Базовые понятия теории алгоритмов (ПК-20).

Методы оценки сложности алгоритмов (ПК-20).

2) Уметь:

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

Применять методы и средства оценки сложности, трудоемкости алгоритмов (ПК-20).

3) Владеть:

Методами определения критериев (показателей) оценки сложности, трудоемкости (ПК-20).

 


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

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

 

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

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

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

 

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


 

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

дисциплины

 

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

(в часах)

 

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

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

 

п\п

Семестр

Лекции

Семинары

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

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

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

СРС

КП / КР

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

Контроль

1

Структуры данных

3

6

8

12

тестирование

2

Алгоритмы обработки данных

3

6

12

36

тестирование

3

Вычислительная сложность алгоритмов

3

6

4

15,95

тестирование

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

108

18

24

63,95

1,8

0,25

Зач.

Итого   

108

18

24

63,95

1,8

0,25

 

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

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

Семестр 3

Раздел 1. Структуры данных

Лекция 1.

Введение. Понятие структур данных (2 часа).

Лекция 2.

Классификация структур данных (2 часа).

Лекция 3.

Виды алгоритмов и их реализация (2 часа).

Раздел 2. Алгоритмы обработки данных

Лекция 4.

Базовые структуры алгоритмов (2 часа).

Лекция 5.

Итеративные и рекурсивные алгоритмы (2 часа).

Лекция 6.

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

Раздел 3. Вычислительная сложность алгоритмов

Лекция 7.

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

Лекция 8.

Временная и пространственная сложность алгоритмов (2 часа).

Лекция 9.

Классы сложности (2 часа).

 

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

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

 

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

Семестр 3

Раздел 1. Структуры данных

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

Изучение структур данных (4 часа).

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

Полустатические структуры данных. Стеки и очереди (4 часа).

Раздел 2. Алгоритмы обработки данных

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

Изучение алгоритмов сортировки данных (4 часа).

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

Изучение алгоритмов быстрой сортировки данных (4 часа).

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

Изучение алгоритмов поиска (4 часа).

Раздел 3. Вычислительная сложность алгоритмов

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

Оценка сложности алгоритмов сортировки и сортировки (4 часа).

 

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

 

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

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

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

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

1. Задача сортировки (внешней и внутренней).

2. Структуры данных и алгоритмы.

3. Стек, очередь и дек как абстрактные типы данных: функциональные спецификации и аксиомы.

4. Примеры алгоритмов, использующих стек, очередь, дек.

5. Процедура разделения.

6. Рекурсивный и не рекурсивный алгоритмы быстрой сортировки. Анализ сложности.

7. Оптимизация программы (неполная сортировка).

8. Распределяющая (поразрядная) сортировка.

9. Рандомизированные бинарные деревья поиска (Treaps).

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

11. Алгоритм построения оптимального дерева.

12. Сбалансированные по высоте бинарные деревья (АВЛ-деревья).

13. Включение в АВЛ-дерево. Исключение из АВЛ-дерева.

14. Реализация упорядоченных линейных списков на базе АВЛ-деревьев или рандомизированных деревьев.

15. Операции поиска, вставки и удаления элементов; операции сцепления и расщепления списков.

 

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

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

 

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

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

 

 

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

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

 

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

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

 

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

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

1. Шутов А. В., Медведев Ю. А. Структуры и алгоритмы компьютерной обработки данных. Часть 1 (Курс лекций). – Владимир: ВлГУ, 2013. – 101 с. - http://e.lib.vlsu.ru/bitstream/123456789/3518/1/00464.docx

2. Шутов А. В., Медведев Ю. А. Структуры и алгоритмы компьютерной обработки данных. Часть 2 (Лабораторный практикум). – Владимир: ВлГУ, 2013. – 109 с - http://e.lib.vlsu.ru/bitstream/123456789/3519/1/00465.docx

3. Шутов А. В., Медведев Ю. А. Структуры и алгоритмы компьютерной обработки данных. Часть 3 (Практикум). – Владимир: ВлГУ, 2013. – 87 с. - http://e.lib.vlsu.ru/handle/123456789/3520

4. Бураков П.В., Косовцева Т.Р. Информатика. Алгоритмы и программирование. Учебное пособие. - СПб НИУ ИТМО, 2013. - 83 с. - http://window.edu.ru/resource/424/80424/files/itmo1372.pdf

 

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

1. Вирт, Н. Алгоритмы и структуры данных / Пер. с англ. Ф.В. Ткачев - М.:ДМК Пресс. - 2010. - 272 с. - http://ibooks.ru/reading.php?productid=339714

2. Мозговой М.В., Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход / Под ред. М.В. Финкова. - Спб.: Наука и Техника, 2006. - 320 с.: ил. - 100 экз.

3. Журнал "Алгоритмы, методы и системы обработки данных" - http://amisod.ru/

 

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

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

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

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

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

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

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

электронная библиотечная система "BOOK.ru" (http://book.ru/);

электронная библиотечная системы "IPRBooks" (http://www.iprbookshop.ru/);

электронная библиотечная система "iBooks.ru" (http://www.ibooks.ru/);

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

Лаборатория системного и прикладного программирования

Microsoft Visual Studio 2008 (подписка DreamSpark Premium Electronic Software Delivery (3 year) Renewal, договор №453 от 16.12.2014 года)

Libre Office v.5 (free software, GPL)

 

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

e.lib.vlsu.ru

window.edu.ru

ibooks.ru

amisod.ru

 

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

Лаборатория системного и прикладного программирования

6 компьютеров Intel Core i5, 3500 MHz/ ОЗУ 4гб/ LG 21’; 1 компьютер Intel Core i5-2400 3,10 GHz, 4гб, DVD-R/ Philips 19’; проектор ACER P1100 DLP Projector EMEA; экран настенный; маршрутизатор TP-Link TL-SG1016D; Компьютер Intel Core 2 -,10 GHz, 2гб, DVD-R/ Philips 19’

 

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

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

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

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

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

 


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


РЕЦЕНЗИЯ

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

«Структуры и алгоритмы обработки данных»

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

 

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

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

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

Задачи дисциплины:

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

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

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

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

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

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

 

06.06.2017 г.