Предмет и задачи дисциплины "Структуры и алгоритмы обработки данных"

Лекция № 1 Предмет и задачи дисциплины.

Предметом теории структур данных являются:

- формализованное описание данных и операций над ними;

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

В результате изучения курса требуется знать:

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

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

- методы физической организации и обработки базы данных.

Можно выделить по уровню абстракции представления данных следующие слои (рис. 1).

Рис. 1

Актуальность изучения дисциплины:

1.   Изменение акцентов в использовании ВТ и в технологии программирования (Вирт Н. «Алгоритм + структура данных = программы»)

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

2.   Одно из ключевых направлений научно-технического прогресса - разработка и внедрение НИТ, обучающихся на концепции базы данных.

Практическая реализация базы данных опирается на использовании эффективных структуры данных.

3.   Современные программные продукты рассчитаны на конечного пользователя. Это интерактивные  системы , где представление данных для пользователя адекватно адекватным внутри машинным представлениям структуры данных.

Структура курса отражена на схеме.

Литература.

1.   Вирт Н. Алгоритмы + структуры данных = программы. М.: Мир 1985.

2.   Ленгсаи Й., Огенстайн М., Таненбаум А. Структуры данных для программных ЭВМ М.: Мир 1983

3.   Бауэр Ф.Л., Гооз, Информатика. Вводный курс. М.: Мир 1990

4.   Костин А.Е., Шапыгин В.Ф. Организация и обработка структур данных в вычислительной системе. М.:     Высшая школа 1987

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

1.   Костин А.Е., Шапыгин В.Ф. Организация и обработка структуры данных в вычислительных системах. М.: Высшая школа 1987.

2.   Трамбле Ж., Соренсен П. Введение в структуры данных. М.: Машиностроение 1982

3.   Мартин Дж., Организация базы данных в вычислительных системах. М.: Мир 1980.

Задачи курса

При выборе решения практических задач информационного типа мы сталкиваемся с тремя взаимосвязанными задачами:

n изучение существенных для решения задачи взаимоотношений между данными;

n определение необходимой совокупности операций над логически связанными элементами данных;

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

Рассмотрим каждую из этих операций:

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

Возможные способы, посредством которых атомарные данные оказываются логически связанными друг с другом характеризуют различные структуры данных.

Структуры данных в значительной степени является следствием смысла (семантики)данных и происхождение структур будет рассматриваться в курсе «Модели и базы данных».

Вторая задача - выбор операций над структурой данных. Это обычно:

n создание и уничтожение структур;

n доступ к элементам структур;

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

n включение и исключение элементов из структур.

Разумеется эти операции функционально различны для разных структур. Но в любом случае способ манипулирования данными зависит от представления структуры данных в памяти ЭВМ.

Представление структуры данных в памяти ЭВМ называется структурой хранения.

Рис.1.1

Одной и той же структурe данных может соответствовать несколько структур хранения  (рис.1.1). Иногда неадекватный выбор структур хранения приводит к снижению эффективности программ, так как реализация операций структуры данных опирается на выбранные структуры хранения.