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

Слайд #1

Модели и моделирование. Цели моделирования. Адекватность модели моделируемому объекту или процессу. Формализация прикладных задач. Представление результатов моделирования в виде, удобном для восприятия человеком.
Графическое представление данных (схемы, таблицы, графики).
Графы. Основные понятия. Виды графов. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа).
Комиссарова О.В.

Слайд #2

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

Задачи делятся на две категории:
вычислительные;
функциональные.

Слайд #3

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

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

Слайд #4

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

Слайд #5

Схема процедуры решения задачи посредством моделирования

Слайд #6

Объект моделирования
Моделировать можно не только материальные объекты, но и реальные процессы.
В дальнейшем термин «объект моделирования» будем понимать в широком смысле.

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

Слайд #7

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

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

Слайд #8

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

Слайд #9

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

Слайд #10

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

Слайд #11

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

Слайд #12

Рассмотрим каждый класс в отдельности

Слайд #13

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

Слайд #14

Классификация по отрасли представленных в модели знаний
По отрасли представленных в модели знаний, все модели можно разделить на:
физические;
биологические;
социальные;
экономические;
и т. д.

Слайд #15

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

Слайд #16

Слайд #17

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

Слайд #18

Зарисуйте схему

Слайд #19

Табличная модель
– это информация о моделируемом объекте, структурированная в виде таблицы. Различают следующие типы табличных моделей:
таблица типа «объект-свойство»
в одной строке содержит информацию
об одном объекте в виде заданного
набора его свойств
таблица типа «объект-объект» отражает взаимосвязи между разными объектами по какому-либо свойству
связь между объектами
Студент и Экзамен
через свойство Оценка за экзамен

Слайд #20

Табличная модель
таблица типа «двоичная матрица» является частным случаем таблицы «объект-объект» и отражает наличие или отсутствие связи между объектами (1 – связь присутствует, 0 – отсутствует).

Слайд #21

Геометрическая модель
модель, представленная с помощью графических форм (граф, блок-схема алгоритма решения задачи, диаграмма и др.)
Геометрическая модель счастья

Слайд #22

Графы

Слайд #23

Граф
- это множество вершин и множество ребер, соединяющих между
собой все или часть этих вершин.

На рисунке представлена геометрическая модель графа, представляющая схему дорог, соединяющих населенные пункты. Вершины графа – это населенные пункты, ребра – дороги. 1-ая модель дает представление - через какие населенные пункты нужно проехать, чтобы добраться из пункта А в пункт В.
2-ая - сколько составит расстояние от одного населенного пункта до другого.

Слайд #24

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

Сколько вершин и ребер у данного графа?

Слайд #25

Решение задач с помощью алгоритмов теории графов
Для этого достаточно лишь принять объекты за вершины, а связь между ними - за рёбра, после чего весь арсенал алгоритмов теории графов к вашим услугам:

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

Слайд #26

Термины и определения теории графов
Вершина - точка в графе, отдельный объект, для топологической модели графа не имеет значения координата вершины, её расположение, цвет, вкус, размер; однако при решении некоторых задачах вершины могут раскрашиваться в разные цвета или сохранять числовые значения.
Ребро - неупорядоченная пара двух вершин, которые связаны друг с другом. Эти вершины называются концевыми точками или концами ребра. При этом важен сам факт наличия связи, каким именно образом осуществляется эта связь и по какой дороге - не имеет значения; однако рёбра может быть присвоен “вес”, что позволит говорить о “нагруженном графе” и решать задачи оптимизации.
Инцидентность - вершина и ребро называются инцидентными, если вершина является для этого ребра концевой. Обратите внимание, что термин “инцидентность” применим только к вершине и ребру. 
Смежность вершин - две вершины называются смежными, если они инцидентны одному ребру.
Смежность рёбер - два ребра называются смежными, если они инцидентны одной вершине.

Слайд #27

Слайд #28

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

Слайд #29

Термины и определения теории графов (продолжение)
Кратные рёбра - рёбра, имеющие одинаковые концевые вершины, по другому их называют ещё параллельными.
Мультиграф - граф с кратными рёбрами.
Псевдомультиграф - граф с петлями и кратными рёбрами.

Слайд #30

Слайд #31

Термины и определения теории графов (продолжение)
Степень вершины - это количество рёбер, инцидентных указанной вершине. По-другому - количество рёбер, исходящих из вершины. Петля увеличивает степень вершины на 2.
Изолированная вершина - вершина с нулевой степенью.
Висячая вершина - вершина со степенью 1.

Слайд #32

Слайд #33

Термины и определения теории графов (продолжение)
Подграф. Если в исходном графе выделить несколько вершин и несколько рёбер (между выбранными вершинами), то мы получим подграф исходного графа. 

Слайд #34

Термины и определения теории графов (продолжение)
Полный граф - это граф, в котором каждые две вершины соединены одним ребром. 
Сколько рёбер в полном графе? Это известная задача о рукопожатиях: собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? Вычисляется как сумма чисел от 1 до N - каждый новый участник должен пожать руку всем присутствующим, вычисляется по формуле: N * (N - 1) / 2.

Слайд #35

Термины и определения теории графов (продолжение)
Регулярный граф - граф, в котором степени всех вершин одинаковые.

Слайд #36

Термины и определения теории графов (продолжение)
Путь или Маршрут - это последовательность смежных рёбер. Обычно путь задаётся перечислением вершин, по которым он пролегает.
Длина пути - количество рёбер в пути.
Цепь - маршрут без повторяющихся рёбер.
Простая цепь - цепь без повторяющихся вершин.

Слайд #37

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

Слайд #38

Слайд #39

Слайд #40

Слайд #41

https://ppt-online.org/1063070

Слайд #42

Ориентированный граф
Ориентированный граф или Орграф - граф, в котором рёбра имеют направления.
Дуга - направленные рёбра в ориентированном графе.

Слайд #43

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

Слайд #44

Слайд #45

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

Слайд #46

Вопросы и упражнения для самоконтроля
Объясните смысл понятия модели и моделирования.
Каким требованиям должны удовлетворять модели?
На какие классы разделяются модели по области использования?
Опишите классификацию моделей по способу их представления.
Поясните термины «материальная (натурная) модель», «информационная модель». Приведите примеры моделей такого рода.
Объясните понятие «вербальная модель». Приведите примеры.
Назовите и охарактеризуйте типы табличных моделей.

Слайд #47

Используемые ресурсы:
https://moodle.kstu.ru/pluginfile.php/247904/mod_resource/content/1/%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D1%8F%20%E2%84%961.pdf
https://intuit.ru/studies/courses/108/108/lecture/3161
https://multiurok.ru/files/tsieli-modielirovaniia.html

Слайд #48

Телеграм-Канал ChatGPT&DALL-e
Решить уравнение
Вопрос по использованию Графа

Создать презентацию (5-6 слайдов)

Слайд #49

Спасибо за внимание