Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

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

---

67 
соответствует операция реализующей этот алгоритм программы. Для 
недетерминированного алгоритма такое соответствие построить нельзя.
Введенный в рассмотрение граф алгоритма есть ориентированный 
ациклический мультиграф, что для любых программ означает выполнение 
только явных вычислений и невозможность определения величины через 
саму себя. В общем случае граф алгоритма есть мультиграф, т. е. две 
вершины могут быть связаны несколькими дугами. Это будет тогда, когда в 
качестве разных аргументов одной и той же операции используется одна и та 
же величина. Обозначим граф, как 
С= (V, Е),
где 
V
- 
множество вершин, 
Е
- 
множество дуг графа 
С
. 
На основе графа алгоритма можно построит по определенным 
правилам строгую параллельную форму графа. Совокупность вершин с 
одинаковыми индексами определяется, как ярус параллельной формы. 
Ширина яруса 
- 
число вершин в группе. Высота параллельной формы 
определяется числом ярусов параллельной формы, а ширину составляет 
максимальная ширина ярусов. Максимальной называется параллельная 
форма минимальной высоты. 
Между различными реализациями одного и того же алгоритма на 
различных компьютерах и различными параллельными формами графа 
алгоритма существует взаимное соответствие. По результатам исследования 
графа алгоритма и его параллельных форм, можно оценить запас 
параллелизма в алгоритме и выбрать его лучшую реализацию на конкретном 
компьютере параллельной архитектуры.