Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями.
Определение 1.Если в параллельном алгоритме существует связь между операторами α, β и α – исполнительный блок, то в графе G существует дуга di Î D1, исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать α → β. Определение 2.Если в параллельном алгоритме существует связь между операторами α, β и α – логический блок, то в графе G существует дуга di Î D2, исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать или соответственно и называть связь по управлению. Связь определяет связь между операторами, если оператор α принимает значение “ TRUE ”, связь - в противном случае. Связи α → β, , назовём задающими связями. Определение 3.Путями в графе G назовём последовательности вершин α1,…, αn , такие, что для любой пары вершин αi, αi+1 существует дуга uÎD1 U D2, исходящая из вершины αi и входящая в вершину αi+1. В графе G нет циклов, поэтому все пути имеют конечную длину. Кроме того, будем считать, что значения логических переменных не связаны друг с другом, поэтому в процессе реализации алгоритма возможен любой из допустимых путей. Определение 4.Характеристикой пути в графе G назовем количество вершин, входящих в этот путь. Определение 5. Длиной пути в графе G со скалярными весами вершин назовем сумму весов вершин, составляющих этот путь. Определение 6.Путь максимальной длины Ткр в графе G со скалярными весами вершин назовем критическим. В одном графе может быть несколько критических путей. В качестве примера алгоритмов в виде схемы последовательного и параллельного алгоритмов с некоторыми трехмерными весами вершин представлен рис. 3. Нумерация блоков в последовательном алгоритме дана в соответствии с ярусностью. В качестве формального средства обработки графов введем матрицу следования S. В матрице следования для удобства использования в столбцах помечены значением 1 все выходящие из данной вершины связи, а в строках – все входящие в заданную вершину связи. Более точное определение матрицы следования заключается в следующем: i –ой вершине графа G ставятся в соответствие i – ые столбец и строка матрицы, если существует связь по управлению , то элемент матрицы равен (i,j) = jT, порождает значение (i,j) = jF, при j → i образуется (i,j) = 1. Остальные элементы матрицы равны 0. Если мы хотим сказать, что между элементом i и j существует некоторая связь, то будем писать i → j. Для отражения весов вершин вводится понятие расширенной матрицы следования SR: прибавляется дополнительно k столбцов с номерами m+1,…,m+k, где k – размерность вектора весов вершин граф – схемы.
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (447)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |