shkolaput.ru 1

СТРУКТУРА ДАННЫХ


Понятие структуры данных появилось и связано с понятием базы данных в конце 60-х годов. В свою очередь, понятие базы данных было связано с понятием автоматизированной системы управления (АСУ, АСУП), используемой в сфере экономики и являющейся, по существу, информационной системой фактографического типа.


В общем случае, информационная система (ИС) может быть представлена в следующем виде.




Предметная

область


Рис. 1 Обобщенная схема ИС


Под ИС понимаем совокупность методов и средств, обеспечивающих представление некоторой предметной области в виде информационной модели (ИМПО), и представление пользователям необходимой информации об объектах предметной области.

Основные сферы применения ИС:


  • образование (получение новых знаний о предметных областях);

  • экономика (использование информации о состоянии объектов и процессов в предметной области с целью управления ее функционированием).

Принципиальное отличие ИС для этих сфер применения заключается в следующем:

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

  • в сфере экономики используются в основном некоторые фактические данные, отражающие определенные свойства, характеристики, параметры, атрибуты, описывающие состояние объектов предметной области.

В соответствии с отмеченными характеристиками представления информации ИС классифицируют на документальные и фактографические.






Предметная

область


Обобщенная схема ИС


Зачем надо иметь информационную модель предметной области, к тому же компьютерную модель?


Моделирование – это замещение одного объекта (оригинала) другим (моделью) и фиксация или изучение свойств оригинала путем исследования свойств модели.


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


Теория моделирования представляет собой взаимосвязанную совокупность положений, определений, методов и средств создания и изучения моделей. Эти положения, определения, методы и средства, как и сами модели, являются предметом теории моделирования.


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


Трудно переоценить роль моделирования в научных изысканиях, инженерном творчестве и, вообще, в жизни человека. Разработка и познание любой системы сводится по существу, к созданию ее модели. Особую ценность имеют конструктивные модели, то есть такие, которые допускают не только фиксацию свойств, но и исследование зависимостей характеристик от параметров системы. Такие модели позволяют оптимизировать функционирование систем.


Специфика предметной области (ПрО) моделируемой фактографической ИС заключается в следующем.

Объектами такой ПрО могут быть объекты самой различной природы (ву вузе, например, личности, подразделения, учебные планы, научные исследования, книги, фирмы и др.). Главное, что объекты в ПрО обладают (могут быть описаны) некоторыми свойствами (параметрами, характеристиками, показателями и т.п.).


При этом для любого объекта значение одноименного параметра может быть различным, но выбирается из одного множества возможных значений, называемого словарем (классификатором) или является числом.

При информационном моделировании на ЭВМ предметная область отображается в компьютерные данные следующим образом:


Предметная область База данных


  1. Параметр (свойство, хар-ка) 1. Данное




  1. Значение параметра 2. Значение данного




  1. Перечень возможных значений 3. Классификатор (словарь)

значений параметра для

объектов одного типа

  1. Группа параметров, описывающих

однотипные объекты с определенной 4. Схема файла

стороны

  1. Описание множества однотипных 4.1. Файл базы данных

объектов по этой группе параметров

  1. Описание одного объекта по этой 4.2. Одна либо несколько

группе параметров (значения пара- записей файла

метров для объекта)

5. Описание однотипных объектов 5. Система файлов с различных сторон (база данных)



  1. Описание предметной области 6. Система баз данных

в целом (все множество типов объектов)


Очевидно, что информационная модель ПрО представляется множеством информационных элементов и связей между ними, т.е. некоторой структурой, называемой структурой данных. Вопрос в том, что является элементами, и какие виды связей между элементами наиболее точно отражают связи между объектами предметной области.


Примеры.


Данные в записи

Записи различного типа (состава данных) между собой


1:1, 1:М, N:М

Студент


Шифр студента

Ф.И.О.

Дата рождения

Пол



Дисциплина

Шифр студента

Дисциплина

Оценка

Рейтинг студента по дисциплине







Шифр студента

Ф.И.О.

Дата рождения

Пол




.

.













Р07109

Иванов И.И.

01.01.78

М



Р07110

Петров П.П.

23.02.78

М



Р07112

Сидорова Е.И.

08.03.79

Ж




.

.
















Шифр студента


Дисциплина


Оценка

Рейтинг студента по дисциплине




.













Р07109

матанализ

5

950




Р07110

матанализ

4

900



Р07112

матанализ

5

1000



.













Р07109

программирование

5

980




Р07110

программирование

5

950



Р07112

программирование

4

850

Студент

Шифр студента

Ф.И.О.

Дата рождения

Пол

Дисциплина

Шифр студента

Дисциплина

Оценка

Рейтинг студента по дисциплине







Шифр студента


Дисциплина



Оценка

Рейтинг студента по дисциплине







.
















Р07109

матанализ

5

950







Р07110

матанализ

4

900






Р07112

матанализ

5

1000







.
















Р07109

программирование

5

980







Р07110

программирование

5

950






Р07112

программирование

4

850







.













Шифр студента

Дисциплина

Месяц

Кол-во пропусков

Оценка по аттестации

.

.













Р07109

матанализ

сентябрь

10

5

Р07110

матанализ


сентябрь

0

5

Р07112

матанализ

сентябрь

40

3

.

.













Р07109

матанализ

октябрь

6

4

Р07110

матанализ

октябрь

16

4

Р07112

матанализ

октябрь

0

5

.

.











Р07109


программирование

декабрь

0

5

Р07110

программирование

декабрь

20

3




Шифр студента

Дисциплина

Оценка

Рейтинг студента по дисциплине





Шифр студента

Дисциплина

Месяц

Кол-во пропусков

Оценка по аттестации


Обращаем внимание, что связь 1:М это не только несколько (М) экземпляров-записей подчиненного для каждого экземпляра старшего, но и всегда только 1 экземпляр старшего, для каждого экземпляра подчиненного


Семестр

Шифр студента

Семестр

Рейтинг за семестр


Дисциплина

Шифр студента

Дисциплина


Средний балл по дисциплине

Рейтинг по дисциплине


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

НО и одному экземпляру структуры Дисциплина можно поставить в соответствие несколько экземпляров структуры Семестр (для дисциплин, изучаемых в течение нескольких семестров) – т.е. связь М:N


А вот связь между структурой Студент и Семестр -

иерархическая (1:М)



Шифр студента

Ф.И.О.

Дата рождения

Пол
Студент


Семестр

Шифр студента

Семестр

Рейтинг за семестр


Отметим, что для студентов 1-го курса и 1-го семестра

для каждого экземпляра структуры Студент имеем только

1 экз. структуры Семестр.


Рассмотрим еще одну структуру


Группа

Группа


Год создания группы

Число студентов в группе

Ф.И.О. старосты




Группа


Год создания группы

Число студентов в группе

Ф.И.О. старосты




Шифр студента





Напоминаю, что в определении ИС мы говорили – МОЖНО

поставить в соответствие М экземпляров подчиненного


Рассмотрим еще одну структуру



Шифр студента

Дата посещения поликлиники

Диаг-ноз

Способ лечения

Дата выздоровления
Посещение поликлиники

Имеем ИС со старшей структурой Студент НО для тех студентов, которые ни разу не обращались в поликлинику не будет ни одного экземпляра подчиненной структуры Посещение поликлиники, т.е.

для этих экземпляров фактически связь 1:0


Т.О. уточним определение ИС – …можно поставить в соответствие ни одного, один или несколько экземпляров подчиненной структуры

Еще примеры 1:1 и N:M