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

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

Понятие модели и моделирования

Модель — упрощённое представление реального объекта, процесса или явления (оригинала), отражающее его существенные для данной задачи свойства и сознательно отбрасывающее второстепенные детали. Моделирование — процесс построения и исследования моделей с целью изучения свойств оригинала, прогнозирования его поведения или проверки некоторой гипотезы без непосредственного эксперимента над самим оригиналом (что часто дорого, опасно или вовсе невозможно). Одному и тому же объекту может соответствовать множество разных моделей, поскольку выбор существенных свойств зависит от конкретной цели моделирования: например, глобус, географическая карта и список координат городов — три разных модели одной и той же Земли, построенные для разных целей.

Формализация

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

Классификация моделей

По форме представления модели принято делить на материальные (натурные) — физические копии или аналоги оригинала (макет здания, глобус, манекен), и информационные — представленные в виде информации: описаний, чисел, изображений, формул, программ. Информационные модели, в свою очередь, делят на знаковые (выраженные с помощью какой-либо системы знаков: текст, формула, таблица, график, схема) и образные (например, рисунок или фотография, передающие внешний облик объекта без формального описания структуры). Далее речь пойдёт о знаковых информационных моделях, наиболее важных для информатики: табличных, иерархических, сетевых и графовых.

Табличные информационные модели

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

Иерархические модели

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

Сетевые модели

Сетевая модель, в отличие от иерархической, допускает, что у одного элемента может быть несколько «родителей» — то есть произвольные связи между объектами без ограничения строгой древовидной структурой. Типичные примеры — схема линий метрополитена (станция может относиться сразу к нескольким пересадочным узлам), карта автомобильных дорог, структура гиперссылок в интернете, где одна веб-страница может ссылаться на множество других и одновременно быть объектом ссылок с разных сторон.

Графовые модели: основные понятия

Универсальным и наиболее формализованным способом представления связей между объектами служит граф — совокупность точек (вершин), некоторые из которых соединены линиями (рёбрами). Если ребро имеет направление (например, обозначает одностороннее движение или ссылку «от — к»), граф называется ориентированным (орграфом), а рёбра — дугами; если направление не имеет значения — неориентированным. Число рёбер, выходящих из вершины (для неориентированного графа — просто примыкающих к ней), называется степенью вершины. Последовательность рёбер, соединяющих одну вершину с другой, называется путём. Деревья и сети, рассмотренные выше, — частные случаи графов: дерево — это связный граф без циклов.

Представление графов: матрица смежности

Для хранения графа в компьютере (а также для удобного анализа «вручную» в задачах ЕГЭ) чаще всего используют матрицу смежности — квадратную таблицу размером N×N (где N — число вершин графа), в которой на пересечении строки i и столбца j стоит 1 (или вес ребра), если между вершинами i и j есть ребро, и 0 — если ребра нет. Для неориентированного графа матрица смежности всегда симметрична относительно главной диагонали, поскольку наличие ребра между вершинами A и B означает одновременно и связь A→B, и связь B→A.

Рассмотрим граф с четырьмя вершинами A, B, C, D, в котором есть рёбра A–B, A–C, B–D и C–D. Его матрица смежности:

Такое представление удобно и для программной обработки. Ниже приведён пример программы на Python, которая по списку рёбер строит матрицу смежности неориентированного графа и выводит её на экран:

vertices = ['A', 'B', 'C', 'D']

edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')]

n = len(vertices)

index = {v: i for i, v in enumerate(vertices)}

matrix = [[0] * n for _ in range(n)]

for v1, v2 in edges:

i, j = index[v1], index[v2]

matrix[i][j] = 1

matrix[j][i] = 1 # граф неориентированный

for row in matrix:

print(row)

Взвешенные графы и деревья

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

Пример: задача на матрицу смежности

Задача. Между четырьмя населёнными пунктами A, B, C и D построены дороги: A–B, A–D, B–C, B–D, C–D. Сколько прямых дорог выходит из пункта D? Постройте матрицу смежности графа дорог.

Решение. Выпишем для вершины D все рёбра, в которые она входит: A–D, B–D, C–D — три ребра. Матрица смежности (0/1) для графа с вершинами A, B, C, D:

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

Ответ. 3 дороги.

Типичные ошибки

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

Краткий словарь терминов

Модель — упрощённое представление объекта, процесса или явления, отражающее его существенные свойства.

Формализация — представление содержательной информации в строгой знаковой (формальной) системе.

Граф — совокупность вершин и соединяющих их рёбер, используемая для представления связей между объектами.

Матрица смежности — квадратная таблица, отражающая наличие (и вес) рёбер между всеми парами вершин графа.

Дерево — связный граф без циклов, частный случай иерархической модели.

Степень вершины — число рёбер, примыкающих к данной вершине графа.

Заключение

Информационное моделирование — универсальный метод формального описания объектов и процессов реального мира средствами, пригодными для компьютерной обработки: от простых табличных моделей до графов произвольной сложности, лежащих в основе навигационных систем, социальных сетей и транспортных задач ЕГЭ. Умение выбрать подходящий вид модели и корректно её формализовать напрямую связано с вопросами защиты информации, которую эти модели описывают, — данной теме, наряду с основами социальной информатики, посвящена заключительная статья раздела.