Лабораторные работы по информатике

Практикум по механике и молекулярной физике
ОПРЕДЕЛЕНИЕ МОМЕНТА ИНЕРЦИИ
МАТЕМАТИЧЕСКИЙ МАЯТНИК
Физический маятник
ОПРЕДЕЛЕНИЕ МОДУЛЯ ЮНГА
ПОПЕРЕЧНЫЕ КОЛЕБАНИЯ СТРУНЫ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ВЯЗКОСТИ
ОПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПОВЕРХНОСТНОГО НАТЯЖЕНИЯ
ОПРЕДЕЛЕНИЕ ВЛАЖНОСТИ ВОЗДУХА
ОПРЕДЕЛЕНИЕ АДИАБАТИЧЕСКОЙ ПОСТОЯННОЙ ВОЗДУХА
Вынужденные колебания линейного осциллятора
Лабораторные работы по информатике
Определение параметров n-мерных коммутационных структур
Преобразование последовательного алгоритма в параллельный
Представление алгоритмов в виде граф–схем.

Построение матрицы логической несовместимости операторов

Построение множеств взаимно независимых операторов
Определение ранних и поздних сроков окончания выполнения операторов
Запуск параллельных программ на кластере
Microsoft Visio
Спецификация требований к информационной системе
Основы работы в редакторе деловой графики Microsoft Visio 2010.
Лабораторная работа №3
Лабораторная работа №4
Функциональное моделирование
Диаграмма классов
Алгоритмические основы машинной графики

Анимация и морфинг

Отсечение прямоугольным окном
Построение проекции трехмерного объекта
Создание простых объектов
Основные навыки работы с объектами
Привязка объектов
Редактирование формы произвольных кривых
Приемы работы с контурами объектов
Создание цветных изображений
Обмен изображениями с другими программами
Ввод и редактирование текста
СИСТЕМА АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ AutoCAD
Основы работы с использованием системы AutoCAD
Команды рисования
Нанесение надписей
Команды редактирования
Проставление размеров на чертеже
Работа с блоками чертежа
 

Лабораторная работа №3. Представление алгоритмов в виде граф–схем.

Цель работы – ознакомление с принципами организации параллельных вычислений с помощью информационного (ИГ) или информационно-логического графа (ИЛГ), представляющего алгоритм решения поставленной задачи как показано на рисунках 3.1, 3.2.


Рисунок 3.1. Информационная граф-схема алгоритма

. . 

Рисунок 3.2. Информационно-логическая граф-схема алгоритма


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

Теоретическая часть

Информационный или информационно-логический граф задается с помощью выражения:

G = (X, P, D),

где X = {i} = {1, …, m} – множество вершин графа, соответствующее множеству операторов параллельного алгоритма, P = {pi}, i = 1, …, m, pi – множество весов, определяющих время выполнения каждого i-го оператора. В общем случае pi – вектор. Размерность вектора равна количеству типов процессоров, используемых в неоднородной ВС. Для однородной ВС pi – скаляр. D – множество дуг графа.

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

В общем случае граф–схема алгоритма – это сеть. Как следует из определения 3.1., циклы исключены из граф-схем. Это сделано по нескольким причинам. Во-первых, распараллеливание осуществляется для сложных программ, где каждый блок схемы алгоритмов – это программный модуль, в который всегда можно включить небольшие по времени циклы и тем самым упростить составление граф-схем алгоритмов. Во-вторых, циклы по параметру [1] не поддаются распараллеливанию и их бессмысленно изображать в граф-схеме, а лучше включить в программный модуль. Циклы по счётчику циклов [1] распараллеливается, как будет показано ниже, введением дополнительных вершин в граф – схему. Для дальнейшего рассмотрения сеть можно представить в виде совокупности свёрток и развёрток графа.

Определение 3.2. Свёрткой k-й вершины граф-схемы называется наличие у k-й вершины граф-схемы n входящих дуг, где n  1 и является конечным числом.

Определение  3.3. Развёрткой k-й вершины графа называется наличие у k-й вершины графа n выходящих дуг, где n  1 и является конечным числом.

 Свёртка и развёртка граф-схемы показаны на рисунке 3.3.

  

Рисунок 3.3. Свёртка и развёртка граф - схемы

 

Определение 3.4. Изолированной k-й вершиной граф-схемы называется вершина, у которой отсутствуют  входящие и выходящие дуги.

Определение 3.5. Элементарной свёрткой или развёрткой k-й вершины граф-схемы называется наличие у k-й вершины граф-схемы одной входящей или выходящей дуги соответственно.

Вопрос о получении или передаче значений параметров для этих случаев представляет несомненный интерес при создании граф-схем алгоритмов, предназначенных для выполнения на вычислительных системах. Рассмотрим случай свёртки k-й вершины граф-схемы. Будем полагать, что каждый вход в k-ю вершину рассматривается, как логическая переменная [1], которая принимает значение «истина», если на рассматриваемый вход приходит информация, полученная на предшествующей вершине, в заданный интервал времени в соответствии с заданными логическими уравнениями пользователя. В противном случае логическая переменная принимает значение «ложь», если логические уравнения определяют значение «ложь». Интервал времени вычисляется соответствующим `способом. Учитывая, что возможны некоторые непредвиденные отклонения, не влияющие существенно на результаты вычислений, при обработке и передаче информации с предшествующей i-й вершины в k-ю, введём интервал времени [-t*ik, t*ik]. Таким образом, время прихода информации с i-й вершины определится как

 Tik = ti + tik + ik , ik[-t*ik, t*ik], (3.1)

где ti – время выполнения программного модуля, представленного i-й вершиной, tik – время передачи информации с i-й вершины в k-ю вершину,ik - отклонение времени выполнения модуля, представленного i-й вершиной, и передачи информации по k-й связи от его среднего значения. 

Перенумеруем все дуги, входящие в k-ю вершиной, получим множество дуг n. Тогда образуется множество времён { Tik}, in и свёртку в вершине k можно трактовать как логическую функцию n переменных. В качестве примера использования данной концепции рассмотрим две логические функции, реализованные на свёртках или развёртках k-х вершин, которые, как будет показано далее, полностью перекрывают возможности, предоставляемые соответствующими ЕСПД по изображению последовательных алгоритмов. Функция «ИСКЛЮЧАЮЩЕЕ ИЛИ» вызывает срабатывание к-й вершины при появлении информации на k-й дуге свёртки или развёртки и реализует наиболее быстрый проход k-ой вершины, так как отсутствует ожидание прихода информации на другие дуги рассматриваемой свёртки или развёртки. Кроме того, эта функция обеспечивает наиболее надёжный узел для срабатывания, так как вероятность не прихода информации на рассматриваемую вершину, в общем случае, минимальна. И наоборот, функция «И» реализует наиболее медленный проход k-й вершины и наименее надёжный узел для срабатывания, так как в общем случае, должна прийти информация на все n дуг свёртки или развёртки. Все другие логические функции занимают промежуточное положение по надёжности и времени срабатывания.

Рассмотрим времена срабатывания для развёртки с k-й вершиной для функции «ИСКЛЮЧАЮЩЕЕ ИЛИ» и функции «И». Функция «ИСКЛЮЧАЮЩЕЕ ИЛИ» реализуется за время для случая срабатывания i-ого выхода

  Tki=tki+ tki* +ki, ki[-t*ki, t*ki], (3.2)

где tki – время выполнения k-ого модуля при формировании i-ого выхода, tki* - время передачи информации, сформированной k-й вершины, к i - й вершине при формировании i-ого выхода, ki – отклонение времени выполнения модуля, представленного k-й вершиной, и передаче информации по i-му каналу от его среднего значения.

Время срабатывания для функции «И» также определяются по формуле (3.2), так как одновременность срабатывания всех выходов не требуется.

Время срабатывания для свёртки с k-й вершиной для функции «ИСКЛЮЧАЮЩЕЕ ИЛИ» также определяется по формуле (3.2), а для функции «И» для обеспечения одновременного прихода сигнала в k-ю вершину время составит

 Tik* = max { Tik}, in,

где Tik – времена, вычисленные по формуле (3.2), n – число входов в k–ю развёртку. 

Очевидно, что любая граф-схема алгоритма представляет собой некоторую последовательность свёрток – развёрток, образующих композицию из логических функций, зависящих от n переменных, где n {1,…,}, где  – максимальное количество дуг в свёртках и развёртках. Следует отметить особую роль времени tki*, при формировании граф-схем алгоритмов. При рассмотрении ВС с общей памятью это время, как правило, не учитывается и методы анализа и решения таких алгоритмов значительно проще. Учёт времени tki* порождает класс ВС с разделяемой памятью, что приводит к усложнению  методов анализа и решения таких алгоритмов. Предлагаемая читателю работа, также построена по принципу – «от простого к сложному». В начале представлен материал, связанный с с методами обработки информации на ВС с общей памятью, имея дело с информационными (ИГ) и информационно-логическими (ИЛГ) граф-схемами. Затем исследуем ВС с разделяемой памятью и изучим информационные граф-схемами с разделяемой памятью (ИГР) и информационно-логические граф-схемами с разделяемой памятью (ИЛГП).

Рассмотрим примеры часто используемых конструкций в граф–схемах алгоритмов, которые могут быть реализованы с помощью предлагаемых логических функций. На развёртках могут быть реализованы все типы основных конструкций языков программирования, используемых для создания последовательных программ. 

На функции «И» k-й развёртки может быть реализован цикл по счётчику циклов. Так, если количество дуг, исходящей из k-й вершины, ограничено по некоторым причинам есть n, а количество повторений в цикле – F, то количество обращений k-ого блока к нижестоящим, связанным с ним блокам определится соотношением ]F/n[, где ][ – функция выделения целой части положительного числа, большей или равной этому числу. Время прохождения информации по этому каналу определится по формуле

   (3.3)

Время выполнения цикла может быть уменьшено до Tki , если увеличить число каналов (число процессоров) до F. Реализация функции «Исключающее ИЛИ» на два или несколько выходов может представлять логическую функцию на два выхода (true, false), три выхода ( > 0, < 0, = 0), а также функцию переключения на один из n возможных каналов. Кроме того, задавая ту или иную логическую функцию, можно получить любую комбинацию передающих каналов, ориентированных на использование операторов – переключателей, используемых в различных языках программирования или для каких либо других целей.

Определение 3.6. Дуги, исходящие из вершин, содержащих логические блоки, переключатели каналов, подлежащие распараллеливанию, называются логически зависимыми. 

На рисунке 3.4 приведена схема алгоритма, ориентированного на представление его в виде графа-схемы. Для простоты изложения будем полагать, что развёртка содержит две логически зависимые дуги и осуществлена развёртка цикла с помощью введения двух дополнительных вершин под номерами 5,9,10. В общем случае требуется, ввод дополнительных вершин, согласно соотношению (3.3) – ]F/n[-1 или F, если используется число процессоров, равное числу итераций в цикле.

Начало алгоритма.

Вычисляется значение переменной А.

Проверяется условие А>10.

Объявляется цикл по переменной i=1, …, 10.

Вычисляется массив значений: B[i]= B[i]+20,

  Вычисляется значение переменной F:=F+1.

Конец алгоритма.

Конец алгоритма.

 

На рисунке 3.4, б приведён фрагмент граф-схемы, соответствующий схеме алгоритма, изображённого в соответствии с выше указанными ЕСПД. Условный блок 3 заменён вершиной 3 с исходящими связями, образующими логическую функцию «Исключающее ИЛИ» на два выхода. Связи, выходящие из вершины 3 в граф-схемах будем обозначать в виде стрелок с точками в начале. Для обозначения связей при построении матриц, описывающих граф-схемы, будет использована комбинация символов в виде n.m, где n – номер вершины, из которой выходит дуга, m – порядковый номер связи. Блок цикла по счётчику циклов 4 заменён логической функцией «И» на три входа, образуя функцию (4,5) & (4,9) & (4,10). Цикл 4 на рисунке 3.4, б заканчивается свёрткой по схеме «И». Два выхода из программы 7,8 позволяют использовать результаты вычислений на процессорах, не дожидаясь окончательного завершения одной из ветвей программы, так как они определяют конец параллельной ветви алгоритма. Элементарные свёртки или развёртки вершин 1,2,3,6.7 не имеют идентификатора логических функций, хотя в соответствии с определением алгоритма при его запуске, они должны всегда срабатывать, будем считать, что они реализуют схему «И». Дуги, образующие схему «И» в блок-схеме изображаются в виде стрелок, используемых как для обозначения дуг свёрток и развёрток.

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

Для более полного представления о возможностях использования граф-схем приведём изображения основных операторов наиболее часто используемых языков программирования.

На рисунке 3.5, а представлена вершина граф-схемы, с помощью которой реализуется процесс в соответствии с терминологией, используемой в ЕСПД. Рисунок 3.5, б отображает реализацию с помощью функции «Исключающее ИЛИ» логического оператора с двумя выходами. Аналогично, рисунок 3.5, в – реализацию с помощью функции «Исключающее ИЛИ» логического оператора с тремя выходами. На рисунке 3.5, г показана реализация оператора-переключателя  с n выходами типа «CASE» языка «Паскаль» [1]. Рисунок 3.5, д отображает реализацию фрагмента программы, в которой начало передачи информации по всем m каналам начинает передаваться одновременно. Используется логическая функция «И»: (13,14) & (13,15) & (13,16). На этой же схеме реализуется цикл по счётчику циклов. Время выполнения зависит от количества итераций в цикле и количества выделенных вычислителей для вычислений цикла ВМ. Время выполнения цикла, определяется согласно формуле  (3.3). Идентификаторы процессов в виде чисел записываются внутри окружностей, которыми изображаются вершины графа.

Затем составляется описание процессов:

 


 

 а) б) в) 

 

 

 • • • • • •

 

 n m 

  г) д) 

Рисунок 3.5. На рисунке изображены фрагменты граф-схемы алгоритма

Представим в виде граф-схем рассмотренные ранее алгоритмы (cм. рисунки 2.1 и 2.2).

 


 a) б)

Рисунок 3.6. Граф-схемы алгоритмов, представленных на рисунках 2.1 и 2.2.

Рисунок 3.6, б наглядно показывает, что после обработки схемы алгоритма, представленного на рисунке 3.1, алгоритмом 2.1, модули 1,2, 4 или 5 и 6 или 7 могут выполняться параллельно. Анализируя нумерацию блоков на рисунке 3.6. можно заметить, что она не совпадает. Это связано с двумя причинами. Во-первых, блоки начала и конца алгоритма исключены, во-вторых, при нумерации вершин граф-схемы (б) соблюдалось правило нумерации по ярусам. Это правило, и преимущество, которое даёт его соблюдение, будет рассмотрено ниже. 

 

Использование граф-схем для представления параллельных алгоритмов

 Граф- схемы алгоритмов представляются с помощью выражения G = (X, P, D), X – множество вершин граф- схемы, X{1, ..., m}. Множество вершин графа X соответствует множеству операторов параллельного алгоритма. P = {1,...,Pm} – множество весов вершин графа. Pi может быть скалярной величиной или вектором, i{1, ..., m}. Если Pi - скаляр, то рассматривается решение этой задачи на однородной ВС (вычислительная система имеет одинаковые процессоры). Тогда, как правило, Pi – время решения i-ого программного модуля. Если – вектор, то предполагается решение этой задачи на неоднородной ВС (вычислительная система имеет разные типы процессоров). И, тогда, если система содержит S разнотипных процессоров, то вектор = { Pi1 ,… , Pis}, где Pi1 ,… , Pis – набор времен решения i-ой процедуры на различных типах процессоров из множества S. D – множество дуг графов. Дуги бывают трёх типов: di  D0, dj  D2 , dk  D3. D = D0D2D3. D0- множество одиночных дуг графа, соответствующих элементарным свёрткам или развёрткам k-х вершин граф-схемы. D2 – множество логических дуг графа, реализующих функции «Исключающее ИЛИ» граф-схемы, D3 – множество дуг графа, реализующих функции «И» граф-схемы,. Обозначим D1= D0D3.

На рисунке 3.7 показаны типы дуг, используемых граф-схемах алгоритмов. Тип а) формирует множество D0, тип б) формирует множество D3, тип в) и г) формирует множество D2. Коплексная стрелка г) используется в тех случаях, когда один выход функции «Исключающее ИЛИ» соединяется с несколькими вершинами граф-схемы одновременно. Граф-схемы бывают двух типов согласно определениям 3.7 и 3.8.

Определение 3.7. Граф-схема, содержащая только дуги diD1,называется информационной граф-схемой (ИГ).

Определение  3.8. Граф-схема, содержащая дуги djD2, реализующие функции «Исключающее ИЛИ» или «Исключающее ИЛИ», «И», называется информационно- логической граф-схемой (ИЛГ).

Например, информационная граф-схема, представленная на рисунке 3.7а, предназначена для изображения алгоритма, который будет выполняться на неоднородных вычислительных системах, имеющих три типа ВМ. Последовательность чисел, заключённых в круглые скобки, расположенных возле вершин граф-схемы, представляет собой составляющие трёхмерного вектора.

 

 а) б) 

Рисунок 3.7. Типы граф-схем, используемых для изображения алгоритмов

а) информационная граф-схема, используемая для решения задач на неоднородных системах; б) информационно-логическая  граф-схема, используемая для решения задач на однородных системах

Принято, что первая составляющая вектора определяет время решения соответствующего программного модуля на первом типе ВМ, вторая – на втором типе ВМ, третья – на третьем и т. д. Символ «» обозначает, что данный программный модуль не может выполняться на рассматриваемом типе вычислительного модуля. Информационно-логическая граф-схема, представленная на рисунке 3.7б, предназначена для изображения алгоритма, который будет выполняться на однородных вычислительных системах. Вместо векторных весов используются скалярные величины, так как будет использован одинаковый тип ВМ.

Дуги бывают двух типов:   и . Дуги  назовем информационными. Эти дуги соответствуют связям, исходящим из исполнительных блоков параллельного алгоритма. Информационно-логические дуги  соответствуют связям, исходящим из логических блоков. Дуги  нагружены меткой «j.n» для связей, j – это номер оператора в граф-схеме, n – номер дуги, выходящей из j-ого оператора. Нумерация дуг будем осуществлять слева – направо.

Граф, содержащий только дуги из множества D1, называется информационной граф-схемой алгоритма. Граф, содержащий некоторые дуги  (в частном случае – все), называется информационно-логической  граф-схемой алгоритма. Примеры различных графов приведены на рисунке 3.7 , а и б.

На этом рисунке номера вершин соответствуют номерам блоков в параллельном алгоритме, веса в виде составляющих вектора записываются рядом с соответствующей вершиной. На рис 3.7, б дуги, соответствующие логическим связям или связям по управлению, помечены составными номерами «2.1» и «2.2».

В качестве весов используются трёхмерные векторы. Это означает, что для решения этой задачи будет использована неоднородная ВС с тремя типами процессоров. Например, значение (1, 3, ∞) у первого оператора означает, что время выполнения на первом типе процессора есть 1 условный эквивалент времени выполнения, на втором – 3, на третьем этот оператор не может быть выполнен.

Введем несколько определений, уточняющих построение граф-схемы алгоритма на основе схемы параллельного алгоритма.

Определение 3.9. Если в параллельном алгоритме существует связь между операторами α, β и α – исполнительный блок, то в граф-схеме G существует дуга , исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать .

Определение 3.10. Если в параллельном алгоритме существует связь между операторами α, β и α – логический блок, то в графе G существует дуга , исходящая из вершины α и входящая в вершину β. Эту связь будем обозначать и называть связью по управлению. Здесь n – номер логической дуги. Нумерацию удобно осуществлять против движения часовой стрелки, беря за основу начала отсчёта положение стрелки, указывающей на девять часов.

Связи ,  назовём задающими связями.

Определение 3.11. Множество выходных вершин граф-схемы G называется мажорантой граф-схемы G.

Определение 3.12. Путями в граф-схеме G назовём последовательности вершин α1, …, αn , такие, что для любой пары вершин αi, αi+1 существует дуга d Î D, исходящая из вершины αi и входящая в вершину αi+1.

Определение 3.13. Множество путей в информационно-логической граф-схеме, начинающихся в i-й вершине, соответствующей логическому оператору, и содержащие дугу с меткой  , и заканчивающихся вершиной, принадлежащей мажоранте, назовём n-ветвью α логического оператора.

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

Определение 3.14. Длиной пути в граф-схеме G назовём количество вершин, входящих в этот путь.

Определение 3.15. Характеристикой пути в граф-схеме G со скалярными весами вершин назовём сумму весов вершин, составляющих этот путь.

Определение 3.16. Путь с максимальной характеристикой Ткр в граф-схеме G со скалярными весами вершин назовем критическим.

В одной граф-схеме может быть несколько критических путей.

Рисунок 3.8. Граф-схема последовательного (а) и последовательного (б) алгоритмов

В качестве примера на рисунка 3.8. представлены схемы последовательного и параллельного алгоритмов с некоторыми трехмерными весами вершин.

Нумерация блоков в последовательном алгоритме дана в соответствии с ярусностью. В качестве формального средства обработки графов введем матрицу следования S. В матрице следования для удобства использования в столбцах помечены не нулевым значением все выходящие из данной вершины связи, а в строках – все входящие в данную вершину связи.

Более точное определение матрицы следования заключается в следующем: i-ой вершине графа G ставятся в соответствие i-ые столбец и строка матрицы S; если существует связь по управлению , то элемент матрицы (i, j) равен α.n; при  образуется значение (i, j) = 1. Остальные элементы матрицы равны 0.

Для отражения весов вершин вводится понятие расширенной матрицы следования SR: к матрице S прибавляется дополнительно k столбцов с номерами m+1, …, m+k, где k – размерность вектора весов вершин граф-схемы.

Построим расширенные матрицы следования для граф-схем, изображенных на рисунке 3.8.

Рисунок 3.9. Расширенные матрицы следования Sдля последовательного алгоритма (а) и параллельного алгоритма (б)

Как видим из рисунка 3.9 матрицы следования получаются треугольными. Рассмотрим условие получения матриц следования в треугольном виде. По условию граф-схемы не должны содержать циклов (контуров). Это означает, что главная диагональ всегда должна содержать нулевые элементы.

Найдем условие построения треугольной матрицы следования для граф-схемы без цикла. Введем в граф-схемы понятие яруса. Возьмем произвольную вершину α в графе G. Найдем все длины путей, ведущих в α. Среди этих длин найдем максимальную. Пусть это будет число hα. Аналогичные вычисления выполним для некоторой вершины β, получим hβ.

Определение 3.17. Если hα = hβ = h, то вершины α и β принадлежат одному ярусу (ярусу h).

Для обеспечения получения треугольной матрицы следования для графа G необходимо при нумерации вершин придерживаться следующего правила: вершины, принадлежащие d+1 ярусу, должны иметь номера большие, чем номера вершин d-ого яруса. Внутри одного яруса вершины могут нумероваться произвольно. Такую нумерацию назовем нумерацией по ярусам.

При решении задачи распараллеливания важную роль играют не только задающие связи, но и так называемые транзитивные.

Определение 3.18. Если , а  связаны задающими связями, то существует транзитивная связь .

Определение 3.19. Множество связей, которые введены направленно внутри всех пар элементов, принадлежащих одному пути в графе G и не связанных задающими связями, назовем множеством транзитивных связей для заданного пути.

Определение 3.20. Множество транзитивных связей графа G есть объединение множеств транзитивных связей по всем путям графа G.

Множество транзитивных связей, очевидно, полностью определяется множеством задающих связей. При формировании множества транзитивных связей следует учитывать, что, если   и , где  – множество всех операторов, связанных с оператором α, то все операторы  связаны транзитивно с оператором β.

Рассмотрим построение матрицы следования с транзитивными связями ST. Возьмем 3 произвольные вершины i, j, k такие, что между ними определены следующие связи: связь вершины i с вершиной j, вершины j с вершиной k, вершины i с вершиной k, как показано на рисунке 3.10.

Рисунок 3.10. Рассматриваемая часть информационно-логического графа

Рисунок 3.11. Матрица следования для фрагмента графа, представленного на рис. 3.10. Многоточием обозначены связи, которые в данном случае не представляют интереса

В матрице следования, изображённой на рисунке 3.11, многоточием обозначены другие связи, которые для данного случая не представляют интереса. При построении матрицы S элементы матрицы, соответствующие логическим связям, выписываются по формуле (3.1), а информационным – по формуле (3. 2):

 (3. 1)

 (3. 2)

Рассмотрим пример построения матрицы S для графа, приведенного на рисунке 3.7, б. Для логических связей в этом графе произведем преобразование по формуле (3.1):  и .

Остальные связи в графе не являются логическими, поэтому соответствующие элементы матрицы S будут равны единице согласно формуле (3. 2). В результате этого преобразования получим матрицу S, изображенную на рисунке 3.12.

1

0

0

0

0

0

2

1

0

0

0

0

3

1

0

0

0

0

4

0

2.1

0

0

0

5

0

2.2

0

0

0

1

2

3

4

5

 

Рисунок 3.12. Матрица следования S для графа, изображенного на рисунке 3.7, б

Теперь необходимо произвести анализ значений типов связей между этими вершинами и определить, какую связь между вершинами i и k выбрать: непосредственную или через вершину j.

Первое, что влияет на этот выбор, – наличие транзитивной связи из вершины i в вершину k через вершину j. Обозначим эту связь ST. Для существования такой связи, как было замечено выше, необходимо, чтобы обе связи Sij и Sjk были отличны от нуля. Для проверки существования этой связи введем операцию «Ä», которая аналогична операции конъюнкции в булевой алгебре и в дальнейшем будет называться транзитивной конъюнкцией. В таблице 3.1 приведены истинные значения операции «Ä» применительно к информационно-логическим графам.

 Таблица 3.1

Таблица истинности операции «»

Sij

Sjk

0

0

0

1

1

L1

0

1

L

1

L

L2

0

0

0

1

L

L1_L2

Здесь L1, L2, L обозначают некоторые кортежи [4] из логических связей , где  – либо некоторая логическая связь из вершины a в вершину b, либо ранее вычисленная транзитивная связь. Символ «_» – оператор конкатенации [4].

Как нетрудно убедиться операция «Ä» коммутативна, поэтому в таблице приведены значения без учета перестановки операндов.

Рассмотрим построение этой таблицы более подробно. Очевидно, что транзитивная связь есть, если обе связи Sij и Sjk отличны от нуля. Соответственно, результат операции на наборах, где хотя бы одна из связей Sij или Sjk равна нулю, будет нулевым, т.е. транзитивная связь отсутствует. Далее, в связи с тем, что ход решения алгоритма отражается последовательностью выполненных логических операторов, то в ситуации, когда один операнд равен единице, а второй содержит логический тип связи, необходимо, чтобы результат операции отражал логическую связь. Поэтому на наборе (1, L) результатом выполнения операции «Ä» будет L. Исходя из тех же рассуждений, можно сказать, что в случае, когда обе связи содержат логический тип связи, необходимо их объединить и результатом операции на наборе (L1, L2) будет выражение L1_L2. Таким образом, данная операция дает нам транзитивную связь .

Следующим шагом будет определение, какая связь нам более важна: непосредственная из вершины i в k (Sik­) или новая, вычисленная ST.

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

Второе, что определяет результат операции, – непосредственно наличие хотя бы одной из связей между вершинами i и k транзитивной или задающей [1], т.е. необходимо выбрать ненулевую связь, если она есть, при нулевом значении другой связи. Обозначим операцию, осуществляющую такой выбор, «Å». Из изложенного выше можно сказать, что ее характер подобен операции дизъюнкции булевой алгебры. В дальнейшем эта операция будет называться транзитивной дизъюнкцией. Приведём таблицу истинности для операции «Å» (таблица 3.2) применительно к информационно-логическим графам, обозначив ранее вычисленную связь  как ST.

 Таблица 3.2

Таблица истинности операции «»

Sik

ST

0

0

0

1

1

L1

0

1

L

L

1

L2

0

1

L

L

1

L1_L2

Таким образом, для трех рассматриваемых вершин можно определить новую связь, используя две введённые операции, т.е. связь Sik можно вычислить по следующей формуле:

 (3. 3)

или применительно к матрице следования:

. (3. 4)

После последовательного преобразования всей матрицы S мы получим матрицу ST.

Теперь необходимо привести алгоритм, осуществляющий такой перебор элементов матрицы S для ее преобразования в ST. Отправной точкой для разработки такого алгоритма является принцип, иллюстрируемый рисунком 3.8. Если при просмотре некоторой k-ой строки матрицы следования, определяющей все входящие в данную вершину связи, обнаруживается в некотором j-ом столбце ненулевой элемент, то, как показано на рисунке 3.10, определяется некоторая вершина j, из которой исходит связь в вершину k. Далее необходимо проверить все входящие в вершину j связи, т.е. проверить все вершины i, а затем к каждой такой тройке применить формулу (3. 4).

Используя соотношения (3.3) и (3.4), построим алгоритм, осуществляющий преобразование матрицы S в матрицу ST. При описании алгоритма были использованы следующие обозначения:

RS – порядок матрицы следования;

(i, j) – операция по чтению или записи значения в ST. Первый индекс определяет строку, второй – столбец матрицы ST.

То, какая операция будет выполнена (считывание или запись), определяется положением выражения (i, j) относительно символа «=». Если она находится слева, то производится запись, если справа – чтение.

Матрица следования является квадратной, поэтому оба цикла определены для множества значений [1, …, RS].

Алгоритм 3.1. Построение матрицы следования с транзитивными связями.

Вычислим ST := S.

В матрице следования ST размера RS просматриваются строки, начиная с первой.

Если в очередной i-й строке матрицы ST отыскивается элемент (i, j) <> 0, то вычисляются значения элементов (i, 1), …, (i, j-1) матрицы ST, используя соотношение (4 – 4):

 

для k = 1, …, j-1.

Вычислим j := j+1. Если j  RS, то переход на шаг 3, иначе – работа алгоритма заканчивается (просмотрены все строки).

Конец алгоритма.

Рассмотрим пример построения матрицы следования с транзитивными связями, используя данные операции, для графа, изображённого на рисунке 3.13а и соответствующей ему матрицы следования, показанной на рисунке 3.13б.

Рисунок 3.13. Пример графа (а) и соответствующей ему матрицы следования (б)

Выполним алгоритм построения матрицы следования с транзитивными связями, используя соотношение (3.4). Первая, вторая и третья строки не удовлетворяют условию применения формулы (3.3) согласно шагу 3 алгоритма 3.1.

Для четвертой вершины:

Для пятой вершины:

Для шестой вершины:

Для седьмой вершины:

Для восьмой вершины:

В результате получим матрицу следования с транзитивными связями (рис. 3.14).

Рисунок 3.14. Матрица следования с транзитивными связями для графа, изображенного на рисунке 3.13 а

Введение операций «Ä» и «Å» позволяет построить матрицу следования с транзитивными связями, в которой сохраняется информация о проходимых в процессе выполнения алгоритма логических операторах, что позволяет исключить из программы большое число промежуточных поисковых операций. Так при определении внешних и внутренних замыканий эффективно используется информация из ST. Кроме того, полученные в этой матрице кортежи из логических связей могу быть использованы для получения вероятностей прохождения по тем или иным путям в граф-схеме алгоритма, что может быть использовано для построения эффективных планов параллельных вычислений.

Определение контуров в граф-схеме алгоритма

Алгоритм использует свойство появления ненулевого элемента в главной диагонали матрицы ST. В качестве исходной берется не треугольная матрица S. Поэтому при получении транзитивных связей предыдущий алгоритм вызывается несколько раз до получения неизменяемой матрицы ST.

Алгоритм 3.2. Определение контуров в граф-схеме алгоритма.

Вычисление матрицы := S, i := 0.

С помощью алгоритма 3.1, используя матрицу  вычислить матрицу .

На главной диагонали матрицы   определяется, есть ли ненулевые элементы? Если есть, то исследуемый граф имеет цикл – работа алгоритма завершена. В противном случае проверяем, изменилась ли матрица . Если , то исследуемый граф не имеет контуров. Алгоритм заканчивает работу. Иначе определяется , i := i+1 и осуществляется переход на шаг 2.

Конец алгоритма.

Пример работы данного алгоритма проиллюстрирован на рисунке 3.15 и рисунке 3.16.

Рисунок 3.15. Иллюстрация работы алгоритма 3.2: граф (а) и матрица следования S (б)

Рисунок 3.16. Матрица ST для графа, изображенного на рисунке 3.15 а

Вопросы для самопроверки

В чем отличие матрицы следования от расширенной матрицы следования и матрицы следования с транзитивными связями?

В каких случаях используется треугольная матрица следования?

Что является признаком наличия цикла (контура) в информационно-логическом графе в матрице следования?

С какой целью вычисляется матрица следования с транзитивными связями?

В чём смысл операций «Ä» и «Å»?

Задание на лабораторную работу

Используя программу, разработанную в предыдущей лабораторной работе, необходимо дополнить ее следующими функциями:

Построение матрицы следования S по заданному графу.

Построение матрицы следования SR (с указанием весов).

Построение матрицы следования ST с транзитивными связями.

Определение наличия или отсутствия контура в исходном графе.

Продемонстрировать работающую программу преподавателю и получить отметку о её выполнении.

Сохранить копию программы для выполнения последующих лабораторных работ на дискете.

Оформить отчет о проделанной работе.

Содержание отчета

Цель работы.

Ответы на вопросы для самопроверки.

Схемы алгоритмов и их описание.

Распечатки экранных форм, полученных в результате работы программы.

Анализ полученных результатов.

Лабораторные работы