Изучение темы «Информационные модели сложных систем: таблицы, графы, дорожные сети, иерархические структуры»

Дисциплина “Информатика” изучается в соответствии с требованиями Федерального государственного образовательного стандарта (ФГОС) 3 поколения согласно учебному плану на основе примерной программы, утвержденной в 2011 году.

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

Тема “Информационные модели сложных систем: таблицы, графы, дорожные сети, иерархические структуры” изучается после усвоения основных понятий – информация, объем информации, кодирование текстовой, числовой, звуковой и графической информации.

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

Введение – теоретические основы

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

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

Также к категории информационных систем относятся:

1. Системы автоматизации проектирования (САПР)
2. Геоинформационные системы (ГИС)
3. Экспертные системы
4. Системы автоматизации научных исследований
5. Автоматизированные системы управления (логистика)
6. Автоматизированные системы составления расписаний
7. Автоматизированные обучающие системы

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

Таблицы

Мощнейшим инструментом для систематизации информации являются таблицы. Их главные достоинства – ёмкость, точность, наглядность.

Таблица (table) – основная структура для хранения данных.

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

Пример таблицы:

Таблица состоит из строк и столбцов.

В данной таблице – 5 столбцов и 6 строк.

В верхней строке – заголовки столбцов.

Пересечение строки и столбца образует ячейку таблицы.

По своей структуре таблицы могут различаться.

Данная таблица относится к типу “объект-свойство” (ОС).

В таких таблицах все свойства относятся к одному объекту.

В данном примере объект – определенный день, задается датой. Все остальные столбцы – свойства объекта (метеорологические данные).

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

Другой тип таблиц – “объект-объект” (ОО)

Рассматриваются пары объектов, то есть свойства характеризуют не один объект, а сразу два. Для каждой пары объектов описано только одно свойство. Таким образом, таблица типа “объект-объект” отражает взаимосвязь между различными объектами.

Пример таблицы:

Таблица успеваемости учеников

Эта таблица отражает связь между объектами – учениками и предметами.

Оценка в баллах – характеристика связи.

Еще один пример:

Таблица расстояний между областными центрами

Такая таблица называется матрицей смежности – цифра расстояния между городами находится на пересечении столбцов и строк с названиями смежных городов.

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

2. Графы

Система – это сложный объект, состоящий из взаимосвязанных частей (элементов) и существующий как единое целое. Всякая система имеет функцию, цель, назначение.

Все части системы объединяются в единое целое в определенном порядке. Структура – это порядок связей между элементами системы, это внутренняя организация системы.

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

Граф отображает состав системы и структуру связей между элементами.

Графы являются мощной основой для построения информационных моделей, решения огромного числа задач моделирования.

Составные части графа:

• вершины графа (обозначаются кружками) – обозначают элементы системы;
• ребра (линии) – показывают связи между элементами

Пример неориентированного графа:

В данном графе 4 вершины (A,B,C,D) и 5 ребер (линии, соединяющие вершины и указывающие взаимосвязи между ними)

Существует 3 способа задания графа:

1 способ - список всех ребер – указывается в круглых скобках через запятую:

(АС, AD, AB, BC, BD)

2 способ – матрица смежности

Матрица смежности - таблица типа “объект-объект”, в названиях столбцов и строк – названия вершин графа. Правило заполнения ячеек таблицы:

1 – ребро между вершинами есть

0 – ребра между вершинами нет

Таблица симметрична относительно главной диагонали матрицы смежности (диагональ выделена зеленым цветом) [2].

3 способ – таблица инцидентности

Для заполнения этой таблицы необходимо пронумеровать ребра графа:

Правило заполнения:

1 – вершина с ребром соединена

0 – вершина с ребром не соединяется

Названия строк таблицы инцидентности – названия вершин графа, названия столбцов – номера ребер графа. Эта таблица не является симметричной и не имеет главной диагонали.

Примером применения неориентированного графа служит дорожная сеть.

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

Пример:

Дано словесное описание:

“Район состоит из пяти поселков: Марьино, Прокшино, Софьино, Булатово и Лукино. Автомобильные дороги проложены между: Марьино и Прокшино, Марьино и Булатово, Прокшино и Лукино, Прокшино и Булатово, от Булатово до Софьино”

Пример схемы по этому описанию:

Поселки обозначены первыми буквами названий:

М - Марьино

П - Прокшино

С - Софьино

Б - Булатово

Л - Лукино

Глядя на этот граф, можно ответить на вопрос – через какие поселки нужно проехать, чтобы добраться из Софьино в Лукино?

Возможно два пути:

• 1 вариант С – Б – П – Л (Софьино-Булатово-Прокшино-Лукино)
• 2 вариант С – Б – М – П – Л (Софьино-Булатово-Марьино-Прокшино-Лукино)

Для сетей характерно наличие замкнутых путей, которые называются циклами.

В примере цикл: Б – М – П – Б (Булатово-Марьино-Прокшино-Булатово).

Дорожную сеть можно представить и в табличном виде:

Такая таблица – двоичная матрица, соответствующая структуре сети:

1 – дорога между поселками есть

0 – дороги нет

Таблица – симметрична относительно главной диагонали (выделена синим цветом).

3. Иерархические структуры – деревья

Иерархия - (греч. hierarchia, от hieros — священный и arche — власть), принцип структурной организации многоуровневых систем, состоящий в упорядочении взаимодействий между уровнями по закону от высшего к низшему.

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

Основное свойство дерева - между любыми его двумя вершинами (на графе обозначаются кружками) существует единственный путь. Деревья не содержат циклов и петель.

Пример – граф административной структуры Российской Федерации

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

Вершины, связанные с корнем образуют первый уровень.

Вершины последнего уровня называются листьями.В примере: корень - РФ, первый уровень – округа, второй уровень - области, листья – города.[3]

Заключение

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

1. Семакин И.Г., Хеннер Е.К. Информатика и ИКТ Базовый уровень М.: БИНОМ. Лаборатория знаний, 2008. - 246 с.
2. Андреева Е.В. Математические основы информатики. М.: БИНОМ. Лаборатория знаний, 2007. – 248 с.
3. Задачник-практикум по информатике. Под ред. И.Семакина, Е.Хеннера, М: БИНОМ. Лаборатория знаний, 2008. - 120 с.