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

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

В результате изучения курса «Структуры и алгоритмы обработки данных» студенты должны

знать:

- основные методы построения статических и динамических структур данных;

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

- языки программирования для эффективной организации данных в различных приложениях;

- перспективы развития теории проектирования эффективных структур данных при использовании различных языков программирования;

уметь характеризовать:

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

уметь анализировать:

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

приобрести навыки:

- в проектировании эффективных структур данных;

- в применении алгоритмов обработки структур данных.

Программа рассчитана на объем 88 учебных часов, из них 50 – аудиторных. Примерное распределение учебных часов по видам занятий: лекций – 34 часа, практических работ – 16 часов.

СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

№ п.п.п.	Название и содержание тем (по типовой или учебной программе)	Контрольная работа (номер и тема по п.2)	Индивидуальные практические работы (по п.1)	Оснащение контрольных и индивидуальных работ (по п.4)	Литература (по п.3)	Рекомендуемый объ-ем для изучения (в часах)	Форма контроля знаний (зачет по контрольной работе, защита индивидуальной работы, зачет)
Раздел 1. Основные приемы работы с информацией
11.	Тема 1. Представление информации в памяти. Введение. Цели и задачи курса. Адресация памяти. Адресное пространство, базирование, смещение				3.1.1. 3.2.1.
	Тема 2. Базовые структуры данных.Примитивные структуры данных и основные операции над ними: создать, уничтожить, выбрать, обновить.				3.1.1- 3.1.3
	Тема 3. Типы данных и их хранение.Целые и действительные числа. Символьная информация. Логическая информация. Указатели.				3.1.1- 3.1.2, 3.2.3
Раздел 2. Статические структуры данных
	Тема 1. Основные структуры и операции над ними.Вектор. Матрица. Массив. Записи и таблицы. Множества.		1.1.А	4.1 4.2	3.1.4, 3.2.2		Защита лабораторной работы
	Тема 2. Работа со словарями.Хеширование данных. Функции хеширования. Коллизии. Открытое и закрытое хеширование. Качество хеш-функции.				3.1.3, 3.2.1
Раздел 3. Динамические структуры данных
	Тема 1. Списки.Односвязный линейный список. Двусвязный список. Применение списков. Ассоциативные списки. Связанные словари		^1.2	4.1 4.2	3.1.1, 3.1.3		Защита лабораторной работы
	Тема 2. Стек.Операция со стеком. Вычисления с помощью стека.	2.1		4.1 4.2	3.1.1, 3.1.3		Защита контрольной работы
	Тема 3. Преобразование выражения.Инфиксная, суффиксная и Префиксная формы				3.1.1, 3.1.3
	Тема 4. Очередь.Основные операции. Простые и циклические очереди. Использование очереди несколькими процессами.		1.1.Б	4.1 4.2	3.1.1, 3.1.3		Защита лабораторной работы
Раздел 4. Нелинейные динамические структуры
	Тема 1. Деревья.Способы представления. Бинарные деревья. Операции.	2.2		4.1, 4.2	3.1.2, 3.1.3		Защита контрольной работы,
111.	Тема 2. Применение деревьев.Рекурсия и итерация. Преобразование выражений. Представление списков.	2.2		4.1, 4.2	3.1.2, 3.1.3		Защита контрольной работы
112.	Тема 3. Преобразование деревьев.Прошивка бинарных деревьев. Представление произвольного дерева в виде эквивалентного бинарного.				3.1.2, 3.1.3
113.	Тема 4. Графы.Формы представления. Алгоритм определения цикличности.				3.2.1, 3.2.2
114.	Тема 5. Применение графов.Определение центра и критического пути в ориентированном графе. Алгоритм Дейкстры.				3.2.1, 3.2.2
Раздел 5. Структуры данных для внешней памяти
115.	Тема 1. Файлы.Индексное размещение. B-­деревья.				3.1.1, 3.2.2
	Итого			Зачет

Дата добавления: 2015-07-16