Информатика 23-24гг Тема. Модели и моделирование. Графы и деревья.

 

Модели и моделирование. Графы и деревья.

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

Моделирование — это создание и исследование моделей с целью их изучения.

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

Информационные модели — это информация о свойствах оригиналах и его связях с внешним миром.

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

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

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

По характеру связей выделяются детерминированные и стохастические (случайные).

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

Детерминированность (от латинского-определяющий) — определяемость. Детерминированность -это процесс, исход которого полностью определен алгоритмом.

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

При моделировании всегда возникает вопрос: «Можно ли верить полученным результата?» Для этого проверяется свойство модели — АДЕКВАТНОСТЬ.

Адекватность — это совпадение существенных свойств модели и оригинала в рассматриваемой задаче. Доказать адекватность модели можно только в сравнении с оригиналом.

Для этого проверяется:

— не противоречит ли результат моделирования выводам теории,

— подтверждается ли результат моделирования результатами эксперимента.

Таким образом, любое моделирование должно соответствовать следующей схеме.

Такое моделирование позволяет:

1. Существенно расширить круг исследуемых объектов.
2. Исследовать процессы и явления, при необходимости ускорять или замедлять процесс.
3. Находить оптимальное соотношение затрат.
4. Проводить эксперименты без риска негативных последствий.
5. Визуализировать полученные результаты.

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

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

Граф является многосвязной структурой, обладающей следующими свойствами:

— на каждый элемент может быть произвольное количество ссылок;

— каждый элемент может иметь связь с любым количеством элементов;

— каждая связка может иметь направление и вес.

Направленная (без стрелки) линия, соединяющая вершины графа, называется ребром.

Линия направленная (со стрелкой) называется дугой.

Граф называется неориентированным, если его вершины соединены ребрами.

Граф называется ориентированным, если его вершины соединены дугами.

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

Среди информационных моделей можно выделить графические информационные модели, к которым относятся карты, чертежи, схемы, диаграммы, графики и предмет сегодняшнего рассмотрения — графы.

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

Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным).

Вершины графа могут отображаться точками, кругами, прямоугольниками и т.д.

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

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

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

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

Информационные модели в виде графов широко используются в повседневной жизни.

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

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

В этом случае между любыми двумя вершинами существует только один путь.

С помощью дерева удобно представлять иерархическую систему.

У дерева выделяется одна главная вершина, которую называют корнем.

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

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

Существуют задачи, которые удобно решать с помощью графов.

Например, если мы хотим отобразить все возможные варианты трехзначных чисел, которые могут получиться из цифр 7 и 8.

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

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

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

Вводятся понятия — Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра и пути. Дерево. Корень, лист, вершина.