МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Саратовский государственный университет имени
Факультет компьютерных наук и информационных технологий
УТВЕРЖДАЮ
___________________________
"__" __________________20__ г.
Рабочая программа дисциплины
Типы и структуры данных
Направление подготовки
231000 Программная инженерия
Профиль подготовки
Разработка программно-информационных систем
Квалификация (степень) выпускника
Бакалавр
Форма обучения
очная
Саратов,
2011 год
1. Цели освоения дисциплины «Типы и структуры данных»
Целями освоения данной дисциплины являются формирование общих представлений о типах и структурах данных, способах представления данных в ЭВМ, алгоритмах обработки структур данных, развитие у студентов компетенций в области применения различных типов и структур данных при решении конкретной задачи.
2.Место дисциплины «Типы и структуры данных» в структуре ООП бакалавриата «Программная инженерия»
Дисциплина «Типы и структуры данных» входит в раздел «Профессиональный цикл. Базовая часть» ФГОС-3 направления подготовки «Программная инженерия». Для успешного усвоения данной дисциплины необходимы компетенции, сформированные у обучающихся в результате обучения в средней общеобразовательной школе, а также при изучении таких дисциплин как «Основы программирования».
Сформированные в процессе изучения дисциплины «Типы и структуры данных» компетенции, необходимы студенту при освоении таких дисциплин профессионального цикла, как «Объектно-ориентированное программирование», «Теория кодирования и передачи данных».
3 Компетенции обучающегося, формируемые в результате освоения дисциплины «Типы и структуры данных»
В результате освоения дисциплины «Типы и структуры данных» студент должен обладать следующими профессиональными компетенциями:
- Способность к формализации в своей предметной области с учетом ограничений используемых методов исследования (ПК-2);
- Способность формализовать предметную область программного проекта и разработать спецификации для компонентов программного продукта (ПК-6);
В результате освоения дисциплины обучающийся должен:
· Знать:
- способы представления различных структур данных в ЭВМ;
- алгоритмы обработки структур данных;
- технологии программирования с использованием абстрактных типов данных.
· Уметь:
- выбрать наиболее эффективный алгоритм для решения задачи;
- выбрать подходящие структуры данных;
- разрабатывать спецификации для конкретных компонентов программного продукта.
· Владеть:
- навыками самостоятельной оценки использования структур данных и алгоритмов их обработки;
- навыками реализации абстрактных типов данных в конкретные структуры данных на языке программирования;
- навыками реализации выбранного алгоритма на языке программирования;
- навыками формализации предметной области программного продукта.
4. Структура и содержание дисциплины «Типы и структуры данных»
Общая трудоемкость дисциплины составляет 4 зачетных единицы 144 часа (из них 72 часа аудиторных).
№ п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам) | |||
Лек. | Лаб | ПР | С | |||||
1 | Понятие типа данных | 3 | 1 | 2 | 2 | 2 | Участие в лабораторных занятиях – 1 нед. Контрольная работа №1– 10 нед. | |
2 | Основные абстрактные типы данных | 3 | 2-4 | 6 | 6 | 6 | Участие в лабораторных занятиях – 2-4 нед. Контрольная работа №1– 10 нед. | |
3 | Деревья | 3 | 5-7 | 6 | 6 | 6 | Участие в лабораторных занятиях – 5-7 нед. Контрольная работа №1 – 10 нед. | |
4 | Множества | 3 | 8-10 | 6 | 6 | 6 | Участие в лабораторных занятиях – 8-10 нед. Контрольная работа №1– 10 нед. | |
5 | Ориентированные графы | 3 | 11-13 | 6 | 6 | 6 | Участие в лабораторных занятиях – 11-13 нед. Контрольная работа №2– 17 нед. | |
6 | Неориентированные графы | 3 | 14-16 | 6 | 6 | 6 | Участие в лабораторных занятиях – 14-16 нед. Контрольная работа №2– 17 нед. | |
7 | Структуры данных для внешней памяти. Управление памятью. | 3 | 17 | 2 | 2 | 2 | Участие в лабораторных занятиях – 17 нед. Контрольная работа №2 – 17 нед. | |
8 | Понятие эффективности алгоритмов | 3 | 18 | 2 | 2 | 2 | Участие в лабораторных занятиях – 18 нед. | |
Промежуточная аттестация | Зачет | |||||||
ИТОГО | 3 | 36 | 36 | 36 |
1. Понятие типа данных
Простые типы данных. Представление различных типов данных в ЭВМ.
Самостоятельная работа – подробное изучение представления различных типов данных в ЭВМ, подготовка к контрольной работе.
2. Основные абстрактные типы данных.
Списки. Реализация списков посредством массивов и указателей. Связанные списки. Стеки. Очереди. Стеки и рекурсивные процедуры.
Самостоятельная работа – изучение и сравнение различных абстрактных типов данных, подготовка к контрольной работе.
3. Деревья
Основная терминология. Способы обхода деревьев. Реализация деревьев. Двоичные деревья. Реализация двоичных деревьев с помощью указателей. Коды Хаффмана.
Самостоятельная работа – подробное изучение реализации деревьев, подготовка к контрольной работе.
4. Множества
Система обозначений для множеств. Реализация множеств. Словари. Структуры данных, основанные на хеш-таблицах. Оценка эффективности хеш-функций. Деревья двоичного поиска. Нагруженные деревья. Реализация множеств посредством сбалансированных деревьев.
Самостоятельная работа – подробное изучение реализаций множеств, подготовка к контрольной работе.
Контрольная работа №1.
5. Ориентированные графы
Основные определения. Представление ориентированных графов. Задача нахождения кратчайшего пути. Алгоритм Дейкстры. Кратчайший путь между двумя парами вершин. Алгоритм Флойда.
Обход ориентированных графов. Орграфы. Сильная связность.
Самостоятельная работа – сравнение алгоритмов Дейкстры и Флойда, подготовка к контрольной работе.
6. Неориентированные графы
Основные определения. Представление неориентированных графов. Остовные деревья минимальной стоимости. Алгоритм Прима. Алгоритмы Крускала. Обход неориентированных графов. Поиск в глубину, поиск в ширину. Точки сочленения и двусвязные компоненты.
Самостоятельная работа – сравнение алгоритмов Прима и Крускала, подробное изучение поиска в глубину и ширину, подготовка к контрольной работе.
7. Структуры данных для внешней памяти. Управление памятью
Модель внешних вычислений. Хранение данных в файлах. Ускорение операций с файлами. Хешированные файлы, индексированные файлы, несортированные файлы с плотным индексом. Внешние деревья поиска. В-деревья. Проблемы управления памятью. Управление блоками одинакового размера. Алгоритм Дойча-Шорра-Уэйта. Фрагментация и уплотнение пустых блоков. Уплотнение памяти. Алгоритм Морриса.
Самостоятельная работа – подробное изучение алгоритмов управления памятью, подготовка к контрольной работе.
Контрольная работа №2.
8. Понятие эффективности алгоритмов
Эффективность алгоритмов. Анализ рекурсивных программ. Алгоритмы «разделяй и властвуй». «Жадные» алгоритмы.
Самостоятельная работа – подробное изучение эффективности алгоритмов, подготовка к экзамену.
5. Образовательные технологии
В учебном процессе при реализации компетентностного подхода используются такие активные и интерактивные формы проведения занятий как модельный метод обучения, метод развивающей кооперации, разбор конкретных ситуаций, командное выполнение заданий с распределением ролей. Широко используются мультимедийные презентации при представлении лекционного материала.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины «Типы и структуры данных».
7. Учебно-методическое и информационное обеспечение дисциплины «Типы и структуры данных»
а) основная литература:
1. Круз Р. Л. Структуры данных и проектирование программ (Data Structures and Program Design) — М.: БИНОМ. Лаб. Знаний, 2008.
2. Ахо А. В., Хопкрофт Дж. Э., Ульман Дж. Д. Структуры данных и алгоритмы (Data Structures and Algorithms).— Киев: Вильямс, 2007.
б) дополнительная литература:
1. Кузнецов В. А., Караваев А. М. Оптимизация на графах (алгоритмы и реализация) — Петрозаводск: Изд-во ПетрГУ, 2007.
2. Каррано Фр. М., Причард Дж. Дж. Абстракция данных и решение задач на C++: Стены и зеркала (Data Abstraction and Problem Solving with C++) — Киев: Изд. дом "Вильямс", 20с.
в) программное обеспечение и Интернет-ресурсы
1. Алексеев В. Е., Таланов В. А. Структуры данных и модели вычислений.http://www. *****/department/algorithms/dscm/
8. Материально-техническое обеспечение дисциплины «Типы и структуры данных»
Для данного курса необходимо наличие компьютерного класса, оборудованного соответствующим программным обеспечением для работы на языке С++ (например, Visual Studio или подобной средой разработки программ).
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по направлению и профилю подготовки «Разработка программно-информационных систем».
Автор доцент каф. МКиКН | ___________ |
Программа одобрена на заседании кафедры математической кибернетики и компьютерных наук от года 22.02.2011, протокол
Заведующий кафедрой математической кибернетики и компьютерных наук | ___________ | |
Декан факультета КНиИТ, доцент | ___________ |
