Учебно-методический комплекс для студентов специальности 351400. 65 «Прикладная информатика (по областям)» «подготовлено к изданию»

Вид материала

Учебно-методический комплекс

Содержание «подготовлено к изданию» «рекомендовано к электронному изданию» Российская федерация Тюменская государственная академия культуры, искусств и социальных технологий 1.3. Требования к результатам освоения образовательной программы по структурам и алгоритмам компьютерной обработки данных 5 1.7. Темы практических занятий (5-й семестр) 9 1. Рабочая программа 1.1. Федеральный компонент Государственного образовательного стандарта 1.2. Цели и задачи дисциплины, ее место в учебном процессе Основной целью 1.3. Требования к результатам освоения образовательной программы по структурам и алгоритмам компьютерной обработки данных 1.4. Распределение часов по семестрам 1.5. Тематический план дисциплины 1.6. Темы лекционных занятий (5-й семестр) Тема 2. Динамическое программирование. Тема 3. Линейные однонаправленные списки. Операции над списками. Тема 4. Линейные двунаправленные списки. Тема 6. Работа с графами. Тема 7.Сложность алгоритмов. 1.7. Темы практических занятий (5-й семестр) Вопросы к экзамену (5-й семестр) ... Полное содержание

Подобный материал:

• Учебно-методический комплекс для студентов специальности 351400. 65 «Прикладная информатика, 333.71kb.
• Учебно-методический комплекс для студентов специальности 351400. 65 «Прикладная информатика, 370.85kb.
• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 81.9kb.
• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 172.73kb.
• Учебно-методический комплекс для студентов специальности 080801. 65 «Прикладная информатика, 478.17kb.
• Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика, 292.77kb.
• Рабочая программа по дисциплине «теория алгоритмов и сложности» для специальности 351400, 390.46kb.
• Учебно-методический комплекс для студентов заочного обучения специальности Прикладная, 88.44kb.
• Паспорт (государственный стандарт) Специальности «прикладная информатика (по областям)», 504.1kb.
• Учебно-методический комплекс для студентов специальностей 080801. 65 «Прикладная информатика, 830.45kb.

РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНКУЛЬТУРЫ РОССИИ

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

высшего профессионального образования

ТЮМЕНСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ КУЛЬТУРЫ, ИСКУССТВ И СОЦИАЛЬНЫХ ТЕХНОЛОГИЙ


«УТВЕРЖДАЮ»:

Директор института

интеллектуальных ресурсов

и информационных технологий

_______________________ /________________ /

^{(подпись) (расшифровка подписи)}

«____» ____________ 201_года.


Дисциплина «Структуры и алгоритмы компьютерной обработки данных»


Учебно-методический комплекс

для студентов специальности 351400.65 «Прикладная информатика (по областям)»


^ «ПОДГОТОВЛЕНО К ИЗДАНИЮ»:

Автор работы ______________________ / _______________________ /

^{(подпись) (расшифровка подписи)}

«______»___________201__ г.


Рассмотрено на заседании кафедр:

Информатики и информационных технологий ___ _________ 201__г. Протокол № _____

Зав. кафедрой __________________________ / Гусева В.Е. /

«______»___________ 201__ г.


Соответствует требованиям к содержанию, структуре и оформлению.

^ «РЕКОМЕНДОВАНО К ЭЛЕКТРОННОМУ ИЗДАНИЮ»:


Рассмотрено на заседании УМК Института интеллектуальных ресурсов и информационных технологий «___» ___ 201__ Протокол № ____

Соответствует ФГОС ВПО и учебному плану образовательной программы.

«СОГЛАСОВАНО»:

Председатель УМК __________________ /_____________________ /

^{(подпись) (расшифровка подписи)}

«______»_____________201__ г.


«СОГЛАСОВАНО»

Директор научной библиотеки_______________ / ________________________ /

^{(подпись) (расшифровка подписи)}


«______»_____________201__ г.

^ РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНКУЛЬТУРЫ РОССИИ

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

высшего профессионального образования

^ ТЮМЕНСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ КУЛЬТУРЫ, ИСКУССТВ И СОЦИАЛЬНЫХ ТЕХНОЛОГИЙ


Кафедра информатики и информационных технологий


Учебно-методический комплекс


по дисциплине цикла ДВ. Ф.01.


«Структуры и алгоритмы компьютерной обработки данных»


для студентов специальности «Прикладная информатика»


Учебно-методический комплекс составлен на основании Государственного образовательного стандарта высшего профессионального образования для специальности 351400.65 Прикладная информатика (по областям)


Составитель: _________________________


УМК обсужден и утвержден

на заседании кафедры ИИТ

«__» _______________ 201__ г.

Протокол № _____


Зав. кафедрой ______________________________ / Гусева В.Е. /

Оглавление

^

1. Рабочая программа

1.1. Федеральный компонент Государственного образовательного стандарта

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

1.2. Цели и задачи дисциплины, ее место в учебном процессе

Курс ориентирован на студентов специальности 351400 – Прикладная информатика (по областям) и может быть полезен специалистам, желающим углубить свои знания в области структур и алгоритмов компьютерной обработки данных.

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

В итоге студенты должны уметь компетентно и ответственно решать на основе полученных знаний следующие комплексные задачи:

- разработки, выбора и преобразования алгоритмов;

- эффективной реализации программного продукта и проведении с его помощью исследований средствами ВТ;

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

Изучение курса направлено также на освоение международных характеристик и особенностей областей Computer science в части построения алгоритмов.


В результате изучения дисциплины каждый студент должен:

• иметь представление о:
  

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

• знать:
  

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

• уметь:
  

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

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


^

1.3. Требования к результатам освоения образовательной программы по структурам и алгоритмам компьютерной обработки данных

Выпускник должен обладать следующими общекультурными компетенциями (ОК):

- способен использовать, обобщать и анализировать информацию, ставить цели и находить пути их достижения в условиях формирования и развития информационного общества (ОК-1)

- способен логически верно, аргументировано и ясно строить устную и письменную речь, владеть навыками ведения дискуссии и полемики (ОК-2);

- способен самостоятельно приобретать и использовать в практической деятельности новые знания и умения, стремиться к саморазвитию (ОК-5);

- способен осознавать социальную значимость своей будущей профессии, обладать высокой мотивацией к выполнению профессиональной деятельности (ОК-6);

-способен понимать сущность и проблемы развития современного информационного общества (ОК-7);

- способен работать с информацией в глобальных компьютерных сетях (ОК-8);

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

- способен понимать сущность и значение информации в развитии современного информационного общества, сознавать опасности и угрозы, возникающие в этом процессе, соблюдать основные требования информационной безопасности, в том числе защиты государственной тайны (ОК-14)

Выпускник должен обладать следующими профессиональными компетенциями (ПК):

общепрофессиональными:

- способен использовать основные законы естественнонаучных дисциплин в профессиональной деятельности и эксплуатировать современное электронное оборудование и информационно-коммуникационные технологии в соответствии с целями образовательной программы (ПК-3);

проектная деятельность:

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

- способен осуществлять и обосновывать выбор проектных решений по видам обеспечения информационных систем (ПК-5);

- способен документировать процессы создания информационных систем на всех стадиях жизненного цикла (ПК-6);

- способен применять к решению прикладных задач базовые алгоритмы обработки информации, выполнять оценку сложности алгоритмов, программировать и тестировать программы (ПК-10);

организационно-управленческая и производственно-технологическая деятельность:

- способен принимать участие в реализации профессиональных коммуникаций в рамках проектных групп, презентовать результаты проектов и обучать пользователей ИС (ПК-14);

аналитическая деятельность:

- способен проводить оценку экономических затрат на проекты по информатизации и автоматизации решения прикладных задач (ПК-15);

- способен оценивать и выбирать современные операционные среды и информационно-коммуникационные технологии для информатизации и автоматизации решения прикладных задач и создания ИС (ПК-16);

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

- способен анализировать и выбирать методы и средства обеспечения информационной безопасности (ПК-18);

- способен анализировать рынок программно-технических средств, информационных продуктов и услуг для решения прикладных задач и создания информационных систем (ПК-19);

научно-исследовательская деятельность:

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

^

1.4. Распределение часов по семестрам

Семестр	Предмет	Объем учебной работы студентов (в час.)						Курсовая работа	Итоговая аттестация
		Общий объем	В том числе
			Аудиторные				Самостоятельная работа студента
			Всего	Из них
				Лекций	Лабораторных работ	Практических занятий
2	Структуры и алгоритмы компьютерной обработки данных	72	72	18	0	18	36	-	зачет
ИТОГО		72	72	18	0	18	36

^

1.5. Тематический план дисциплины

№ п/п	Темы лекционных занятий	Все-го
	5-й семестр
	Модуль 1. Алгоритмы
	Тема 1. Алгоритмы и их свойства	4
	Тема 2. Динамическое программирование.	6
	Тема 3. Линейные однонаправленные списки. Операции над списками.	4
	Тема 4. Линейные двунаправленные списки.	4
	Всего по модулю 1:	18
	Модуль 2. Сложные алгоритмы
	Тема 5. Бинарные деревья поиска.	6
	Тема 6. Работа с графами.	6
	Тема 7.Сложность алгоритмов.	6
	Всего по модулю 2:	18
	ИТОГО за 5-й семестр	36

^

1.6. Темы лекционных занятий (5-й семестр)

	Модуль 1. Алгоритмы
	Тема 1. Алгоритмы и их свойства Программа и алгоритм. Основные свойства алгоритма. Понятие данных. Способы представления алгоритма. Словесное описание алгоритма. Основные конструкции алгоритма. Графическое представление алгоритма. Понятие алгоритмического языка. Методы разработки алгоритмов: итерации, рекурсии, полный перебор, балансировка.	2
	^ Тема 2. Динамическое программирование. Организация массивов. Многомерные массивы. Операции над массивами. Динамические массивы. Быстрый поиск: бинарный и последовательный поиски в массивах, хеширование.	2
	^ Тема 3. Линейные однонаправленные списки. Операции над списками. Построение списка. Операции над списками. Кольцевые списки. Построение и вывод кольца. Построение других структур на базе однонаправленных списков в динамической памяти: очереди, стеки, деки. Проведение операций над элементами структур.	2
	^ Тема 4. Линейные двунаправленные списки. Формирование линейного двунаправленного списка. Способы организации поиска. Двунаправленные кольцевые списки. Деки на базе двунаправленных списков. Формирование дека и его просмотр. Проведение операций над элементами структур.	4
	Модуль 2. Сложные алгоритмы
	Тема 5. Бинарные деревья поиска. Построение бинарного дерева поиска. Дерево отрезков. Способы обхода дерева. Изображение бинарного дерева. Поиск вершины в бинарном дереве. Операции над вершинами в деревьях. Идеально сбалансированные бинарные деревья. Балансированные по высоте деревья (АВЛ-деревья). Математический анализ АВЛ-деpевьев. Построение АВЛ-дерева. Деревья Фибоначчи. Алгоритмы балансировки. Файлы: организация и обработка, представление двоичными деревьями.	2
	^ Тема 6. Работа с графами. Представления графов. Список ребер. Списки смежности. Реализация простейших операций над графами. Ортогональные списки смежности. Структуры Вирта. Модифицированные структуры Вирта. Обходы графов. Путь между фиксированными вершинами. Кратчайшие пути между всеми парами вершин. Вычисление длин кратчайших путей между вершинами. Контуры в ориентированных графах. Вычисление компонент связности, двусвязности. Остовы. Построение остова наименьшей стоимости. Построение алгоритмов с возвратом. Алгоритмы раскраски графа. Задачи поиска; исчерпывающий поиск: перебор с возвратом, метод ветвей и границ.	2
	^ Тема 7.Сложность алгоритмов. Понятие о сложности алгоритма. Временная и емкостная оценки сложности. Верхние и средние оценки сложности алгоритма. Анализ сложности рекурсивных алгоритмов. Сложность операций с бинарными деревьями. Оптимизация алгоритмов.	4
	ИТОГО:	18

^

1.7. Темы практических занятий (5-й семестр)

	Модуль 1. Алгоритмы
	Организация массивов. Операции над массивами. Сортировки. Однонаправленные списки. Операции над списками. Очередь. Операции над элементами очереди. Кольца. Операции над кольцами.	2
	Стек. Работа со стеком. Дек. Работа с деком. Двунаправленные списки. Работа с производными структурами: кольцами и деком.	2
	Деревья. Построение дерева. Обходы деревьев. Операции с деревьями. Поиск заданной вершины в дереве. Построение идеально сбалансированного дерева. Деревья Фибоначчи. Построение АВЛ-дерева. Представление формул с помощью дерева. Вычисление формул. Представление графов с помощью ортогональных списков смежности.	4
	Представление ориентированного графа с помощью динамической структуры Вирта. Представление графа. Обходы графов. Реализация программы отыскания множества вершин, принадлежащих контуру заданной длины.	2
	Модуль 2. Сложные алгоритмы
	Представление графа. Вычисление компонент связности, двусвязности. Реализация программы нахождения стягивающего дерева связного графа (рекурсивный обход графа в глубину).	2
	Реализация программы нахождения стягивающего дерева связного графа с использованием нерекурсивного обхода графа в ширину. Реализация программы поиска гамильтонова пути в связном неориентированном графе. Реализация программы нахождения всех клик в графе, заданном структурой Вирта.	4
	Реализация программы последовательной раскраски вершин графа при помощи обхода графа в глубину. Реализация программы последовательной раскраски графа при помощи обхода графа в ширину. Реализация программы последовательной раскраски графа, представленного с помощью модифицированных списков смежности.	2
	ИТОГО:	18

8. ^

   Вопросы к экзамену (5-й семестр)

1.Алгоритмы, основные свойства. Временная сложность алгоритмов. Асимптотическая нотация.

2.Способы вычисления рекуррентных отношений.

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

4.Линейные списки. Основные операции. Представление и реализация.

5.Стеки. Основные операции. Представление и реализация.

6.FIFO-Очереди. Очереди с приоритетами. Деки. Основные операции. Представление и реализация.

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.Алгоритм многофазного слияния. Алгоритм горизонтального распределения серий.

8. Литература

Основная литература

1. Марка, Д.А. SADT — методология структурного анализа и проектирования / Д. А. Марка, К. М. Мак-Гоуэн. – Москва : Метатехнология, 2008 – 604 с.
   
2. Уайс, М. А. Организация структур данных и решение задач на С++ : учебник / М. А. Уайс, - Москва : Эком, 2009 – 308 с.
   
3. Фридман, А. Л. Язык программирования Си++ : учебник / А. Л. Фридман. – Москва : Интернет-университет информационных технологий - ИНТУИТ.ру, 2011 – 652 с.
   

Дополнительная литература

1. Вендров, А. М. Проектирование программного обеспечения экономических информационных систем : учеб. пособие / А. М. Вендров. – Москва : Финансы и статистика, 2010 – 228 с.
   
2. Заботина, Н. Н. Проектирование информационных систем : учеб. пособие / Н. Н. Заботина. – Москва : ИНФРА-М, 2011 – 329 с.
   
3. Лисицин, Д. В. Объектно-ориентированное программирование. Конспект лекций. : учеб. пособие / Д. В. Лисицин. – Новосибирск : Издательство НГТУ, 2010 – 230 с.
   
4. Смирнова, Г. Н. Проектирование экономических информационных систем : учебник / Г. Н. Смирнова, А. А. Сорокин, Ю. Ф. Тельнов. – Москва : Финансы и статистика, 2010 – 329 с.
   
5. ГОСТ 34.601-90 Автоматизированные Системы Стадии создания.
   

^

2. Контрольная работа для студентов заочной формы обучения (5 семестр)

дисциплина Структуры и алгоритмы компьютерной обработки данных

для студентов заочной формы обучения

Рекомендации по выполнению контрольной работы

1. Контрольная работа выполняется и сдается на любом цифровом носителе.
   
2. Контрольная работа сдается за две недели до сессии (иногородние студенты в первый день сессии).
   
3. Контрольная работа– это краткие ответы на 3 вопроса для контрольной работы. Вопросы выбираются по последней цифре номера зачетной книжки, например: № 0325 – 010, вопросы № 5, 15, 25.
   
4. Контрольная работа оформляются как текстовый документ: (имя файла ОЗО ПИ Фамилия.doc). В документе должен быть оформлен титульный лист (приложение) и оглавление.
   
5. Текст контрольной работы должен удовлетворять следующим требованиям: шрифт 14 Times New Roman, междустрочный интервал 1,5. Каждый абзац должен начинаться с красной строки.
   
6. В тексте должны быть следующие элементы: список, автофигуры в тексте, таблица, рисунок в тексте, номера страниц в нижнем колонтитуле, в верхнем колонтитуле: Ф.И.О., курс и специальность.
   
7. Объем контрольной работы 10 – 12 печатных страниц.
   
8. Для защиты контрольной работы необходимо подготовить презентацию, используя Microsoft Office PowerPoint.
   

Вопросы для контрольной работы

1. Алгоритмы, основные свойства. Временная сложность алгоритмов. Асимптотическая нотация. Способы вычисления рекуррентных отношений.
   
2. Основные методы построения алгоритмов: «разделяй и властвуй», динамическое программирование.
   
3. Линейные списки. Основные операции. Представление и реализация.
   
4. Стеки. Основные операции. Представление и реализация.
   
5. FIFO-Очереди. Очереди с приоритетами. Деки. Основные операции. Представление и реализация.
   
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. Алгоритм многофазного слияния. Алгоритм горизонтального распределения серий.
    

^

3. Приложение: Титульный лист

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ТЮМЕНСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ КУЛЬТУРЫ, ИСКУССТВ и СОЦИАЛЬНЫХ ТЕХНОЛОГИЙ»


Кафедра информатики и информационных технологий

Контрольная работа

по дисциплине Высокоуровневые методы информатики и программирования

___ семестр


Выполнил: Ф.И.О., специальность, курс, группа,

№ зачетной книжки.

Вариант

Проверил: Ф.И.О. преподавателя


Тюмень, 20__ г.