- •1. Определение элемента системы, его функции и связей. Определение системы и ее свойств. Параметризация системы.
- •2.*Структура системы. Агрегирование и декомпозиция. Виды декомпозиции систем. Пример декомпозиции любого вида1.
- •3) Типы соединений систем. Иерархические, матричные и сетевые структуры
- •4) Принципы системного подхода. Процедуры системного подхода. Задача синтеза систем
- •5.*Алгоритм итерационного проектирования систем. Характеристика методов модификации проектов систем.
- •6.*Базисные множества и концептуальная модель системы в терминах теории множеств.
- •7. Типовые математические схемы моделирования систем
- •8.*Постановка одно- и многокритериальной задачи поиска и принятия решений
- •12.Топологические модели систем. Оптимизация структур связей методом построения минимальных связывающих деревьев. Алгоритм Прима или Краскала. Пример реализации выбранного алгоритма.
- •13.Алгоритм формальной декомпозиции систем по методу разбиения графа на максимально сильно связные подграфы.
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. Построение завершается, когда дерево включает все вершины графа, т. е. все вершины имеют общий цвет.