Лекция 8. Информация и моделирование

Известно, что модель — это некоторое упрощенное подобие реального объекта. Более полное определение звучит так:

Модель — это объект-заменитель, который в определенных услови­ях может заменять объект-оригинал. Модель воспроизводит интере­сующие нас свойства и характеристики оригинала.

Модели бывают материальными и информационными. Примерами ма­териальных моделей являются глобус — модель Земли; манекен — мо­дель человеческого тела; модели самолетов, кораблей, ракет, автомоби­лей; макет застройки жилого района в городе и многое другое.

Предметом изучения информатики являются информационные модели.

В информационной модели отражаются знания человека об объекте моделирования. Информационная модель — это описание в той или иной форме объекта моделирования.

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

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

Информатика занимается общими методами и средствами созда­ния и использования информационных моделей.

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

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

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

Информационная модель базируется на данных, т. е. на информации об объекте моделирования. Любой реальный объект обладает бесконечным множеством различных свойств. Для создания его информационной модели требуется выделить лишь те свойства, которые необходимы с точ­ки зрения цели моделирования; четко сформулировать эту цель необходи­мо до начала моделирования.

Система основных понятий

Компьютерное информационное моделирование
Модель — это объект-заменитель реального объекта
Виды моделей:
Материальные (натурные) модели	Информационные модели
	Компьютерная информационная модель — модель, реализованная на компьютере
	Этапы построения компьютерной информационной модели:
	Определение цели моделирования	Системный анализ объекта моделирования: результат — теоре­тическая информа­ционная модель	Реализация модели на компьютере: используется специаль­ное программное обес­печение или языки вы­сокого уровня

Структуры данных: деревья, сети, графы, таблицы.

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

Рассмотрим несколько часто используе­мых видов описания структур данных: графы, иерархические структуры (деревья) и таблицы.

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

Вот, например, словесное описание некото­рой местности: «Наш район состоит из пяти поселков: Дедкино, Бабки­но, Репкино, Кошкино и Мышкино. Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Бабкино и Кошкино, Кошкино и Репкино». По такому описанию доволь­но трудно представить себе эту местность, нелегко и запомнить описание. А представьте себе, что поселков не 5, а 25! Всё гораздо понят­нее становится из схемы на рис. 1 (на ней поселки обозначены первыми буквами своих названий).

Рисунок 1. Неориентированный граф (сеть)

Это не карта местности. Здесь не выдержаны направления по сторонам света, не соблюден масштаб. На этой схеме отражен лишь факт существо­вания пяти поселков и дорожной связи между ними. Такая схема называ­ется графом.

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

Составными частями графа являются вершины и ребра. Здесь верши­ны изображены кружками, обозначающими элементы системы, а ребра изображены линиями, показывающими связи (отношения) между эле­ментами. Глядя на этот граф, легко понять структуру дорожной системы в данной местности.

Построенный граф позволяет, например, ответить на вопрос: через ка­кие поселки надо проехать, чтобы добраться из Репкино в Мышкино. Вид­но, что есть два возможных пути; обозначим их так:

1)Р —К —Б —М;

2)Р —К —Д —Б —М.

Очевидно, первый путь более выгодный, потому что он короче. Однако если по какой-то причине дорога между К и Б окажется непроезжей (нач­нутся ремонтные работы или дорогу занесет снегом), то единственным остается второй путь. Граф на рисунке 1 еще называют сетью.

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

Для сетей также характерно наличие замкнутых путей, которые назы­ваются циклами. На рис. 1 имеется цикл: К - Д - Б - К.

Граф, изображенный на рис. 1, является неориентированным гра­фом. На нем каждое ребро обозначает наличие дорожной связи между дву­мя пунктами. Но дорожная связь действует одинаково в обе стороны: если по дороге можно проехать от Б к М, то по ней же можно проехать и от М к Б. Такую связь еще называют симметричной.

А теперь рассмотрим другой пример графа — на рисунке 2.

Этот пример относится к медицине. Известно, что существуют четыре группы крови человека. Оказывается, что при переливании крови от одно­го человека к другому не все группы совместимы. Граф на рис. 2 показывает возможные варианты переливания крови.

Рисунок 2. Ориентированный граф

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

Связи между вершинами данного графа несимметричны и поэтому изображаются направленными линиями со стрелками. Такие линии при­нято называть дугами (в отличие от ребер неориентированных графов). Граф с такими свойствами называется ориентированным. Линия, выхо­дящая и входящая в одну и ту же вершину, называется петлей. На рис. 2 присутствуют четыре такие петли.

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

При построении информационных моделей многих систем приходится иметь дело с иерархической структурой. Как правило, иерархическую структуру имеют системы административного управления, между эле­ментами которых установлены отношения подчиненности.

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

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

Таблицы.

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

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

Другой тип таблиц называется «объект—объект». Такие таблицы отра­жают взаимосвязь между различными объектами. Примером является таблица успеваемости учеников по разным предметам. Эта таблица отражает связь между объектами двух типов: учениками и изучаемыми дисциплинами.

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

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

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

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

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

Многие компьютерные технологии работают с таблицами (базы данных, электронные таблицы); обработку таблиц удобно описывать на универсальных языках программирования. Поэтому представление систе­мы в форме графа обычно используется в теоретических моделях, а в ком­пьютерном моделировании чаще работают с табличным представлением.

Система основных понятий

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

Задание: Привести свои примеры структуры данных в виде графов и таблицы.