Тема 3: Информационное
моделирование
Моделирование — это создание и
исследование моделей с целью их изучения.
По природе модели
делятся на материальные и информационные. Материальные модели обычно
представляют собой физическое или предметное представление объекта. Например,
архитектор, чтобы представить заказчику здание, сначала строит его уменьшенную
копию. Для нас же более интересней рассмотреть именно информационные модели.
Информационные модели — это информация
о свойствах оригиналах и его связях с внешним миром.
Среди таких моделей
можно выделить вербальные, то есть представленные в виде слов и описаний и знаковые,
то есть представленные в виде схем, карт, формул, чертежей.
Еще информационные
модели можно различать по фактору времени. Статистические, то есть те, в
которых интересующие нас свойства не изменяются со временем, и динамические —
это модели, которые описывают движение, развитие.
Сами динамические
модели могут быть дискретными и непрерывными. Дискретные модели — это модели,
которые описывают поведение оригинала только в отдельные промежутки времени.
Непрерывными моделями называются модели, описывающие поведение оригинала для
всех промежутков времени.
По характеру связей
выделяются детерминированные и стохастические. Детерминированные модели
описывают четкую связь между исходными данными и результатом, в стохастических
же моделях учитываются случайные события.
При моделировании
всегда возникает вопрос: «Можно ли верить полученным результата?» Для этого
проверяется свойство модели — АДЕКВАТНОСТЬ.
Адекватность — это
совпадение существенных свойств модели и оригинала в рассматриваемой задаче.
Доказать адекватность модели можно только в сравнении с оригиналом.
Для этого проверяется:
— не противоречит ли
результат моделирования выводам теории,
— подтверждается ли
результат моделирования результатами эксперимента.
Таким образом, любое
моделирование должно соответствовать следующей схеме.
Такое моделирование
позволяет:
1.
Существенно расширить круг исследуемых объектов.
2.
Исследовать процессы и явления, при необходимости ускорять или замедлять
процесс.
3.
Находить оптимальное соотношение затрат.
4.
Проводить эксперименты без риска негативных последствий.
5.
Визуализировать полученные результаты.
Между данными,
используемыми в той или иной информационной модели, всегда существует некоторые
связи, определяющие ту или иную структуру данных.
Граф является
многосвязной структурой, обладающей следующими свойствами:
— на каждый элемент
может быть произвольное количество ссылок;
— каждый элемент может
иметь связь с любым количеством элементов;
— каждая связка может
иметь направление и вес.
Направленная (без
стрелки) линия, соединяющая вершины графа, называется ребром.
Линия направленная (со
стрелкой) называется дугой.
Граф называется неориентированным,
если его вершины соединены ребрами.
Граф называется ориентированным,
если его вершины соединены дугами.
Граф называется взвешенным,
если его вершины или ребра характеризуются некоторой дополнительной информацией
— весами вершин или ребер.
Оформляют таблица в
соответствии с ГОСТ 2.105-95 «ЕСКД».
Таблицы могут быть
следующими типами:
«Объект — свойство»,
содержащими информацию о свойствах отдельных объектов, принадлежащих одному
классу.
«Объект — объект»,
содержащими информацию о некотором одном свойстве пар объектов, принадлежащих
одному или разным классам.
Давайте рассмотрим,
пожалуй, самую известную головоломку, придуманную аж в XVIII веке, и
захватившую умы человечества на многие годы. Называется она задача о семи
Кёнигсбергских мостах. В Кёнигсберге начиная с XIV было построено 7 мостов:
Медовый мост, Лавочный мост, Зелёный мост, Рабочий мост, Кузнечный мост,
Деревянный мост и Высокий мост, соединяющий остров и полуострова в единый
город. Тогда и возникла головоломка: «Как пройти по всем мостам, не проходя ни
по одному дважды?»
Десятилетиям жители
города пытались решить эту задачу как практически (гуляя по городу), так и
теоретически.
И только Леонард Эйлер, введя новое понятие — ГРАФ, смог решить ее раз и навсегда.
Граф — абстрактный
математический объект, представляющий собой множество вершин графа (обозначены
красным цветом) и набор рёбер (обозначены синим), то есть соединений между
парами вершин. При этом каждое ребро представляет собой отношение двух вершин.
Графы делятся на:
— Неориентированные
и ориентированные (когда движение по ребру возможно только в одну
сторону).
— Взвешенными (когда
у вершины или у ребра есть вес, отличающий его от другого) и невзвешенный.
— И другие более
сложные графы (мультиграф, псевдограф, изоморфный граф и другие).
Эйлер установил, что:
1. Число нечётных
вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно
или не может существовать граф, который имел бы нечётное число нечётных вершин.
2. Если все вершины
графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при
этом можно начинать с любой вершины графа и завершить его в той же вершине.
3. Граф с более чем
двумя нечётными вершинами невозможно начертить одним росчерком.
ВЫВОД: пройти только
один раз по каждому мосту невозможно.
Графы находят широкое
применение во многих сферах нашей жизни. Например, с их помощью можно
планировать оптимальные транспортные маршруты, упростить решение математических
задач, визуализировать решения компьютерных программ, визуализировать различную
информацию (схема метро, карта звездного неба и т. д.).
Очень часто для
решения задач требуется найти кратчайший путь между двумя вершинами.
Кратчайшим путем мы будем
называть путь, если: эти вершины соединены минимальным числом ребер (в случае,
если граф невзвешенный); сумма ребер, соединяющих эти вершины, минимальна (для
взвешенного графа).
Существует огромное количество алгоритмов, находящих кратчайший путь и один из них — это алгоритм Дейсктры.
Алгоритм заключается в
том, что надо пошагово перебрать все вершины графа, вычеркивая их, которые
будут являются известным минимальным расстоянием от вершины «начала» до
конкретной вершины.
Для примера возьмем
следующий взвешенный ориентированный граф и попытаемся найти кратчайший путь от
вершины A до F. Пошагово переберём все вершины графа, вычеркивая их, которые
будут являются известным минимальным расстоянием от вершины «начала» до
конкретной вершины.
Первым шагом: присвоим вершине А
метку равную 0, потому как эта вершина — начало. Остальным вершинам присвоим
метки равные бесконечности.
Вторым шагом: выберем
не вычеркнутую вершину, вес которой является минимальным («источник»). Сейчас
это вершина А. Вычисляем сумму веса вершины источника и веса ребра
То есть для:
B=0+2=2
C=0+5
D=0+7
F=0+10.
Если она окажется
меньше веса вершины приемника, то изменим вес этой вершины.
Третьим шагом: вычеркнем
вершину-«источник».
Повторим шаги 1, 2, 3
до тех пор, пока не будут вычеркнуты все вершины.
Еще один способом
нахождения кратчайшего пути может служить «метод динамического
программирования».
Пусть дан некоторый
лабиринт, соединяющий комнаты в виде графа. При этом заходя в каждую комнату,
нужно заплатить пошлину. Необходимо пройти по нему от точки А до точки В,
потратив наименьшее количество денег.
Составим таблицу, в
которой каждая ячейка будет соответствовать определенной ячейке. Числа в
ячейках будут равны минимальному числу пошлины, которое можно получить, пройдя
от начала (A) до соответствующей клетки.
Комментариев нет:
Отправить комментарий