Информационные модели

При изучении информатики вам не однажды приходилось встречаться  с иерархическими системами. Например, система хранения файлов намагнитных дисках  организована по иерархическому принципу. Операционная система позволяет получить на экране компьютера изображение файловой структуры в виде дерева (Рис. 5). Корнем этого дерева является корневой каталог диска, вершинами — подкаталоги различных уровней.

Как известно, путь к файлу —  это путь от корневого каталога до каталога, непосредственно содержащего данный файл. И для каждого файла такой путь единственный. Например, путь к файлам, содержащимся в папке Other на рис. 5, описывается так:

 

 

 

 

C:\Downloads\moviemir.com\Other

Рис. 5.Иерархическая система хранения файлов

При поиске информации в дереве перемещение по нему может происходить только вверх или вниз (на уровень выше или на уровень ниже). Нельзя осуществить прямой переход между вершинами одного уровня.

Ещё одним примером иерархической  структуры является система доменных адресов в Интернете. Фрагмент этой системы представлен на рис.6 в виде дерева.

Рис. 6. Иерархическая структура доменных адресов в Интернете

В этом дереве от корня отходят  домены первого уровня, затем —  второго и т. д. Овалами изображены компьютеры. Адрес компьютера включает в себя последовательность доменов  и имя компьютера (сначала записывается имя компьютера, затем домен нижнего  уровня и т. д., до домена самого верхнего уровня). Для трех указанных на рис. 6 компьютеров доменные адреса записываются так:

www.pstu.ac.ru                             hydra.psu.ru                             mail.psu.ru

Каждую вершину дерева, не являющуюся листом, можно рассматривать как  корень поддерева, исходящего из этой вершины. Например, на рис. 6 поддерево с корнем в вершине ru представляет структуру доменных имён российского сектора Интернета.

1.2.3. Таблицы

Представление информации в табличной  форме широко распространено. Только в школьной практике вам приходится встречаться с массой таблиц: расписанием занятий, журналом успеваемости, графиком дежурств, таблицей Менделеева, таблицами физических свойств веществ (плотности, теплоёмкости, электрического сопротивления и пр.), таблицами исторических дат и многими другими.

Чаще всего мы пользуемся прямоугольными таблицами (бывают и более «хитрые» формы таблиц, но о них мы говорить не будем). Простейшая таблица состоит из строк и граф (столбцов). В верхней строке таблицы обычно располагаются заголовки столбцов. Пересечение строки и столбца образует ячейку. Таблица 1 — пример прямоугольной таблицы, содержащей сведения о погоде в течение нескольких дней.

Таблица 1.Погода

Дата	Осадки	Температура, °C	Давление, мм рт. ст.	Влажность, %
15.03.2007	снег	–3,5	746	67
16.03.2007	без осадков	0	750	62
17.03.2007	туман	1,0	740	100
18.03.2007	дождь	3,4	745	96
19.03.2007	без осадков	5,2	760	87

 

Обратите внимание на правила оформления таблиц. Над таблицей обычно указывается  её номер и заголовок. Заголовки  столбцов пишутся с прописной  буквы; там, где это необходимо, указываются  размерности величин.

Таблица 1 является примером таблицы  типа «объект–свойство». Каждая строка такой таблицы относится к  конкретному объекту. В нашем  примере объект — это определённый день. Первый столбец обычно идентифицирует этот объект (дата идентифицирует день). Последующие графы отражают свойства объекта. В таблице 1 это метеорологические данные. Обратите внимание на то, что строки таблицы расположены по возрастанию даты, т. е. информация в таблице упорядочена (по дате). Упорядоченность позволяет быстро найти нужные данные.

Другой тип таблиц называется «объект–объект». Такие таблицы отражают взаимосвязь  между различными объектами. Примером является таблица успеваемости учеников по разным предметам (табл.2).

Таблица 2. Успеваемость

Ученик	Предмет
	Русский	Алгебра	Химия	Физика	История	Музыка
Аликин Петр	4	5	5	4	4	5
Ботов Иван	3	3	3	3	3	4
Волков Илья	5	5	5	5	5	5
Галкина Нина	4	4	5	2	4	4

 

Эта таблица отражает связь между  объектами двух типов: учениками  и изучаемыми дисциплинами. Оценка (расположена в ячейке) является характеристикой такой связи. В такой таблице строки и столбцы могут поменяться местами: в строках — информация о предметах, в столбцах — об учениках. Удобнее работать с таблицами, в которых столбцов меньше, чем строк. Обычно учеников в классе больше, чем изучаемых предметов.

Важной разновидностью таблиц типа «объект–объект» являются двоичные матрицы. Двоичные матрицы отображают качественную связь между объектами: есть связь или нет связи. Например, если бы ученики могли выбирать изучаемые предметы по своему усмотрению, то сведения о том, кто что изучает, можно было бы представить в виде таблицы 3:

Таблица 3.Изучаемые предметы

Ученик	Предмет
	Русский	Алгебра	Химия	Физика	История	Музыка
Аликин Петр	0	1	1	1	0	0
Ботов Иван	1	1	0	1	0	1
Волков Илья	1	0	0	0	1	1
Галкина Нина	0	1	1	0	1	0

 

Нетрудно догадаться, что единица  указывает на изучаемый предмет, а  неизучаемый предмет отмечен  нулём.

Табличный способ представления данных является универсальным. Любую структуру  данных, в том числе и представленную в виде графа, можно свести к табличной  форме. Таблица 4 — возможное представление иерархической структуры, изображённой на рис. 2.

Таблица 4. Административная структура Российской федерации

Город	Регион	Округ
Березники	Пермская обл.	Приволжский
Екатеринбург	Свердловская обл.	Уральский
Кунгур	Пермская обл.	Приволжский
Пермь	Пермская обл.	Приволжский
Сергиев Посад	Московская обл.	Центральный

 

Заполнение таблицы происходит путём движения по дереву снизу вверх (от листьев к корню). Получилась таблица типа «объект–свойство». Объекты — города, а свойствами является их принадлежность к соответствующим административно-географическим зонам. Строки в данной таблице упорядочены в алфавитной последовательности названии городов. Нет смысла заводить графу под названием «Государство», поскольку во всех строках в ней будет присутствовать одно значение «Российская Федерация». Лучше это слово вынести в заголовок этой таблицы.

Для табличного представления сетей  используют двоичные матрицы. Таблица 5 представляет собой двоичную матрицу, соответствующую структуре сети на рис. 2.

Таблица 5.Дорожная сеть

Посёлок	Посёлок
	Бабкино	Дедкино	Кошкино	Репкино	Мышкино
Бабкино	0	1	1	0	1
Дедкино	1	0	1	0	0
Кошкино	1	1	0	1	0
Репкино	0	0	1	0	0
Мышкино	1	0	0	0	0

 

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

Замечание: вопрос о том, какую цифру (ноль или единицу) ставить в диагональных клетках, носит условный характер. Можно договориться по-разному. В таблице 5 поставлены нули из тех соображений, что, например, дороги Бабкино–бабкино не существует (хотя, в принципе, можно построить такую петлю).

У матрицы, отображающей ориентированный  граф, такой симметричности не будет. В этом случае надо договориться о  смысле строк и столбцов. Например, пусть для каждой пары смежных  вершин строка обозначает начальную, а  столбец — конечную вершину. Тогда структуру ориентированного графа, изображённого на рис. 3, можно представить следующей двоичной матрицей смежности — табл. 6.

Таблица 6.Переливание крови

Начальная вершина	Конечная вершина
	I	II	III	IV
I	1	1	1	1
II	0	1	0	1
III	0	0	1	1
IV	0	0	0	1

 

Может возникнуть вопрос: зачем мы переводили граф в табличную форму? Ведь граф, с точки зрения человека, гораздо нагляднее и понятнее представляет структуру системы, чем таблица. Для человека это действительно так. Однако для компьютерной обработки табличная форма подходит лучше. Многие компьютерные технологии работают с таблицами (базы данных, электронные таблицы); обработку таблиц удобно описывать на универсальных языках программирования. Поэтому представление системы в форме графа обычно используется в теоретических моделях, а в компьютерном моделировании чаше работают с табличным представлением.

 

 

 

 

 

 

Структуры данных
Графы					Таблицы
Разновидности графа					Элементы прямоугольной  таблицы
Деревья			Сети		Строки	Столбцы	Ячейки
Тип связей в графе					Типы таблиц
Один ко многим			Многие ко многим
Элементы дерева			Элементы сети		Объект–свойство	Объект–объект	Двоичная матрица
Корень	Ветви	Листья	Вершины	Рёбра
Единственность пути между  вершинами			Множественность путей между  вершинами