- •Содержание шпоры
- •1. Определение элемента системы, его функции и связей. Определение системы и ее свойств. Параметризация системы.
- •2.*Структура системы. Агрегирование и декомпозиция. Виды декомпозиции систем. Пример декомпозиции любого вида1.
- •3) Типы соединений систем. Иерархические, матричные и сетевые структуры
- •4) Принципы системного подхода. Процедуры системного подхода. Задача синтеза систем
- •5.*Алгоритм итерационного проектирования систем. Характеристика методов модификации проектов систем.
- •6.*Базисные множества и концептуальная модель системы в терминах теории множеств.
- •7. Типовые математические схемы моделирования систем
- •8.*Постановка одно- и многокритериальной задачи поиска и принятия решений
- •12.Топологические модели систем. Оптимизация структур связей методом построения минимальных связывающих деревьев. Алгоритм Прима или Краскала. Пример реализации выбранного алгоритма.
- •13.Алгоритм формальной декомпозиции систем по методу разбиения графа на максимально сильно связные подграфы.
- •14.Определение модели, моделирования, свойств интерполяции и экстраполяции. Классификация моделей по критерию подобия и соотношению точности/абстрактности.
- •15.*Иерархические уровни моделирования скт и кс. Структурные примитивы уровней моделирования.
- •16.*Математический аппарат моделирования скт и кс на различных уровнях декомпозиции.
- •17.Подходы к описанию функциональных структур. Типы элементов функциональных структур смо, используемых для моделирования скт и кс.
- •18.Вероятностное моделирование. *Использование метода Монте-Карло для реализации неравномерных распределений.
- •19.Абстрактные конечные автоматы 1-го и 2-го рода. Матрицы переходов и выходов. Представление графом.
- •20.*Простые временные сети Петри. Способы задания. Моделирование элементарного цикла обслуживания простой временной сетью Петри.
- •21.*Ингибиторные сети Петри. Моделирование элементарного цикла обслуживания ингибиторной сетью Петри. Пример моделирования системы или процесса ингибиторной сетью Петри.
- •22.*Типы сетей Петри, используемые для моделирования вс. Пример моделирования процесса параллельного обслуживания заявок с пакетированием сетью Петри.
- •23.*Моделирование вс с использованием теории массового обслуживания. Классификация смо. Типы элементов функциональных структур смо, используемых для моделирования вс.
- •24.Аналитические модели массового обслуживания.
- •25.*Обслуживание с ожиданием. Постановка задачи. Свойства экспоненциального распределения времени обслуживания. Обслуживание как Марковский процесс.
- •26.Обслуживание с потерями. Обслуживание с ограниченным временем ожидания. Постановка задачи. Обслуживание как Марковский процесс.
- •27.Обслуживание с потерями. Обслуживание с ограниченным временем пребывания. Постановка задачи. Обслуживание как Марковский процесс.
- •28.Обслуживание с потерями. Моделирование приоритетного обслуживания с использованием теории массового обслуживания.
- •Моделирование приоритетного обслуживания с использованием теории мо.
- •29.*Имитационные модели массового обслуживания. Элементы имитационных моделей.
- •30 Алгоритмы имитационного моделирования для пошагового управления модельным временем
- •31.Алгоритмы имитационного моделирования для событийного управления модельным временем.
- •32.Алгоритмы имитационного моделирования для пошагового управления модельным временем.
12.Топологические модели систем. Оптимизация структур связей методом построения минимальных связывающих деревьев. Алгоритм Прима или Краскала. Пример реализации выбранного алгоритма.
Модели систем в виде графов называются топологическими. Топологические модели первого типа являются описаниями структуры связей внешних, внутренних и выходных параметров системы. Они создаются на уровне концептуального моделирования и далее последовательно детализируются путем определения операторов связей в математическом моделировании.
Примером топологической модели первого типа может служить модель схемы электрической принципиальной, используемая для решения задач анализа динамических и статических характеристик в ПО САПР функционального анализа электронной и вычислительной аппаратуры.
Топологические модели второго типа являются описаниями функциональной структуры систем. Они используются для решения задач декомпозиции (выделения подсистем в системе) и определения структурных свойств системы.
Примерами топологических моделей второго типа служат:
-
неориентированный граф компьютерной сети, в котором вершины соответствуют активному оборудованию, а ребрам присвоены весовые коэффициенты, характеризующие функциональные характеристики линий связи (длина, скорость передачи, пропускная способность и т. п.);
-
ориентированный граф информационной системы предприятия, в которой источники информации (персонал, измерительные устройства), приемники (персонал, исполнительное оборудование) и устройства обработки информации (активное оборудование компьютерной сети) представлены узлами, а дуги интерпретируют каналы связи с заданным направлением передачи информации.
Минимальным связывающим деревом графа называется дерево, связывающее между собой все вершины графа и имеющее минимальный суммарный вес ребер. Для построения таких деревьев используют алгоритмы Прима и Краскала.
В алгоритме Прима на первом шаге выбирается произвольная вершина графа (так называемый корень дерева) и из множества связанных с ней ребер выбирается ребро с минимальным весом. В дерево включается корень дерева, выбранное ребро и смежная вершина. На всех последующих шагах алгоритма рассматриваются множества вершин, имеющие ребра, инцидентные уже построенному дереву, из которых выбирается ребро с минимальным весом для включения в дерево очередной вершины. Построение завершается, когда дерево включает все вершины графа.
На рис. 33 приведен граф рассматриваемой подсети и результат выполнения первого шага алгоритма Прима, для которого в качестве корня дерева была выбрана вершина 6, и из множества весов инцидентных ребер {3, 4, 6} – ребро с минимальным весом, равным 3. Построенный фрагмент дерева выделен цветом, а множество ребер, инцидентных построенному фрагменту дерева – пунктиром.
На втором шаге алгоритма из множества весов инцидентных ребер {4, 6, 5, 5, 1} выбирается ребро с весом 1, в дерево добавляется вершина 1, а множество рассматриваемых весов ребер расширяется до {4, 6, 5, 5, 4, 3, 3}. На третьем шаге из этого множества выбирается ребро с весом 3, в дерево добавляется вершина 4, а в множество, рассматриваемое на следующих шагах включаются веса всех оставшихся ребер графа (рис. 34).
На четвертом шаге алгоритма в дерево добавляется ребро с весом 2 и вершина 3; на пятом – ребро с весом 3 и вершина 7. Результат построения минимального связывающего дерева для выделенного графа подсети первого сервера приведен на рис. 35. Суммарный вес этого дерева равен 12.
Алгоритм Краскала, в отличие от алгоритма Прима, не требует прохода по всем вершинам графа. Если m – количество вершин графа, то для построения минимального дерева необходимо m-1 ребер. Изначально все вершины графа окрашивают в различные цвета. Далее, на каждом шаге алгоритма выбирают ребро минимального веса между смежными вершинами разного цвета. Выбор очередного ребра r=(vi, vj), где vi и vj имеют разные цвета, возможен, если он не образует циклов в уже сформированном дереве. При выборе ребра r=(vi, vj) вершина vj и все, окрашенные в ее цвет (т. е. ранее уже включенные в построенные фрагменты дерева) перекрашиваются в цвет вершины vi. Построение завершается, когда дерево включает все вершины графа, т. е. все вершины имеют общий цвет.