- •Понятие о структуре данного. Уровни представления структур данных.
- •Классификация сд в программах пользователя и в памяти эвм
- •Сд в оперативной памяти
- •Сд типа массив.
- •Сд типа запись (прямое декартово произведение).
- •Сд типа таблица.
- •Операции над таблицей:
- •Временная сложность алгоритмов.
- •Сд типа хеш-таблица.
- •Операция включения элемента в таблицу.
- •Операция исключения элемента из таблицы:
- •Сортировки. Улучшенные методы сортировок.
- •Классификация задач по временной сложности.
- •Сд типа стек.
- •Алгоритм сортировки Хоара (стек используется для хранения границ сортируемой области в таблице):
- •Сд типа очередь.
- •Связное распределение памяти.
- •Сд типа линейный односвязный список.
- •Сд типа указатель.
- •Статические и динамические переменные.
- •Сд типа циклический линейный список.
- •Сд типа двусвязный линейный список.
- •Сд типа дек.
- •Многосвязные списки.
- •Средства объектно-ориентированного программирования.
- •Объекты и свойства инкапсуляции.
- •Наследование и переопределение.
- •Полиморфизм. Виртуальные методы.
- •Динамические объекты. Деструкторы.
- •Обработка ошибок при работе с динамическими объектами.
- •Модули, экспортирующие объекты.
- •Нелинейные структуры данных.
- •Сд типа дерево.
- •Представление деревьев в связной памяти эвм.
- •Алгоритмы прохождения деревьев в глубину и в ширину.
- •Представление деревьев в виде бинарных.
- •Представление бинарных деревьев в связной памяти. Прошитые деревья
- •Формирование бинарного дерева.
- •Применение бинарных деревьев в алгоритмах поиска.
- •Операция включения в сд типа бинарное дерево.
- •Операция исключения из бинарного дерева.
- •Представление бинарного дерева в прямоугольной памяти.
- •Применение бинарных деревьев.
- •Сд типа граф.
- •Представление графа в памяти эвм.
- •Алгоритмы прохождения графа.
- •Топологическая сортировка.
- •Организация данных во внешней памяти. Типы и характеристики устройств внешней памяти.
- •Сд типа последовательный файл.
- •Сд типа файл прямого доступа.
- •Сд типа индексно-последовательный файл.
- •Сд типа хеш-файл.
- •Внешняя сортировка.
- •Алгоритм прямого слияния.
- •Многофазная сортировка.
- •Сущность базы данных. Системы управления базами данных.
- •Общая структура субд.
- •Реляционная модель субд.
- •Язык реляционной алгебры.
Сущность базы данных. Системы управления базами данных.
Любое предприятие или учреждение в той или иной форме занимается обработкой разнообразных данных. Характер обработки зависит от специфики задачи и функций предприятия. Но в любом случае имеются операции первоначального создания совокупности данных, модификации данных и операции доступа с целью их использования.
Совокупность взаимосвязанных наименованных данных, расположенных на носителях, доступных для ЭВМ, и используемых сотрудниками для решения различных информационных задач на предприятиях, называется базой данных.
Для создания и доступа к базам данных необходимо определить системные программные компоненты. Комплекс, состоящий из технических средств и системных программных компонентов, которые обеспечивают использование и обслуживание баз данных, называют системой управления баз данных (СУБд). Обычно сюда не входят прикладные программы, что обеспечивает независимость баз данных от программ пользователя.
Общая структура субд.
П1
П2
П3
ПN
Уровень пользователя
Внешняя модель 1
Внешняя модель 2
Внешняя модель N
Уровень внешних моделей
Системные программные компоненты
Логическая модель
Логический уровень
Физическая модель
Физический уровень
База данных
Самый нижний уровень является физическим. Здесь указываются форматы записей, физические уровни данных, организация записей. Логический уровень предлагается пользователю (абстрактное представление данных в терминах логических характеристик данных и отношений между ними). Различают три основных типа баз данных на логическом уровне: иерархические, сетевые, реляционные.
Уровень внешних моделей характеризует собой ту часть логической модели, которая видима определенному пользователю при решении данного класса задач.
Прикладной уровень СУБД охватывает прикладные программы, предназначенные для работы в среде СУБД.
Реляционная модель субд.
В основе реляционной модели лежит математическое понятие отношения. Пусть заданы множества Di , i = 1, 2,…,n и определим декартово произведение этих множеств: D = D1 D2 … Dn. Множества эти не обязательно разные. D также будет являться множеством, элементами которого являются последовательности d = <d1, d2,…,dn>, di Di , d = 1, 2,…,n. D – домен различного характера и размерности:
D1 = {Иванов, Сидоров, …}; D2 = {1967, 1970, …}, …
Rn-местным отношением называют подмножество D: Rn D, где n – количество элементов последовательности (степень отношения). Количество этих последовательностей называется кардинальным числом. Отношение удобно представлять в виде таблицы ,в которой строки – кортежи, а столбцы – домены (все значения этого множества). Расположение строк не имеет значения. Если каждому столбцу дать имя, то их можно различать по-разному. Столбец еще называют атрибутом.
Отношение можно представить в виде символьной строки (название и имена атрибутов): R(A1, A2,…,AN). Например: Студент (личный номер, Ф.И.О., факультет, группа). Таблица тогда имеет вид:
С
R4 D1
D2
D3
D4
Личный номер |
Ф.И.О. |
Факультет |
Группа |
|
|
|
|
|
|
|
|
|
|
|
|
Как правило, один или несколько атрибутов используют в качестве ключа, относительно которого осуществляют сортировки.
В реляционной модели БД отношение должно быть нормализовано, т.е. каждое значение нового атрибута должно быть неделимым (атомарным), т.е. представлять собой скалярный или строковый тип. Любая взаимосвязанная совокупность данных может быть преобразована в несколько нормализованных отношений.
Преподаватель
Семейное положение
квалификация
Ф.И.О.
дети
адрес
Преподаватель (личный номер, Ф,И,О,, зарплата);
Квалификация (личный номер, ВУЗ, ученая степень, дисциплина);
Семейное положение (личный номер, адрес, …).
С точки зрения пользователя, реляционная модель БД представляется в виде совокупности наименованных нормализованных отношений, который различаются степенью, кардинальным числами и разным количеством строк. Каждому отношению можно поставить в соответствие файл последовательного доступа.