Граф-схема алгоритма

Граф-схема алгоритма (ГСА) — конечный связный ориентированный граф $G=\left\langle A,V\right\rangle$ , вершины которого $a_{i}\in A,i={\overline {1,N}}$ соответствуют операторам, а дуги $v_{k}=\left(a_{i},a_{j}\right)\in V,k={\overline {1,M}},i,j={\overline {1,N}}$ задают порядок следования вершин (операторов) алгоритма, где $N=\left|A\right|$ — число вершин графа, $M=\left|V\right|$ — число дуг. В более широком смысле вершинам графа соответствуют не только операторные вершины, но и условные, начальная и конечная вершины и т. д. При рассмотрении параллельных алгоритмов вводится понятие параллельной граф-схемы алгоритма (ПарГСА), в состав которой входят вершины распараллеливания/синхронизации, функциональность которых обычно совмещается. Иногда

сетью Петри

), ждущие вершины.

Однако не любой ориентированный граф, составленный из вершин указанных выше типов, может быть отождествлен с корректным алгоритмом. Например, из операторной вершины не может выходить более одной дуги. Поэтому на практике обычно ограничиваются рассмотрением подкласса граф-схем алгоритмов, удовлетворяющих свойствам безопасности, живости и устойчивости.^[4] Алгоритмы преобразования ГСА, являющиеся подмножеством алгоритмов обработки графов общего вида, зачастую имеют существенные отличия ввиду использования особых свойств ГСА, что позволяет их упрощение, снижение временной или ёмкостной сложности.^[1]^[3]^[5]

В составе граф-схемы алгоритма могут быть выделены более крупные элементы, представленные подмножествами её вершин и дуг: ветви (линейные цепочки или участки вершин) и фрагменты (начальный, параллельный, альтернативный, циклические с пред-, постусловием и прерыванием). Эквивалентным представлением граф-схемы корректного алгоритма является дерево фрагментов, отражающее порядок вложенности фрагментов.

См. также

Граф потока управления

Примечания

↑ ¹ ² Ватутин Э. И., Зотов И. В. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов (неопр.). Известия курского государственного технического университета. Курск. № 2. С. 85–89. (2004). Архивировано 28 апреля 2012 года.
↑ Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4
↑ ¹ ² Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5
↑ Закревский А. Д. О корректности параллельных алгоритмов логического управления // Известия АН СССР. Техническая кибернетика. — 1987. — № 4. — С. 106—112.
↑ Ватутин Э. И., Зотов И. В., Титов В. С. Выявление изоморфных вхождений R-выражений при построении множества сечений параллельных алгоритмов логического управления (неопр.). Информационно-измерительные и управляющие системы. № 11, Т. 7. М.: «Радиотехника». С. 49–56. (2009). Архивировано 28 апреля 2012 года.

Ссылки

Баранов С. И. Синтез микропрограммных автоматов (граф-схемы и автоматы). Л.: Энергия, 1979. 232 с.
Лазарев В. Г., Пийль Е. И. Синтез управляющих автоматов. М.: Энергоатомиздат, 1989. 328 с.
Автоматное управление асинхронными процессами в ЭВМ и дискретных системах. Под ред. В. И. Варшавского. М.: Наука, 1986. 400 с.
Гост

[rm-1] ¹ ² Ватутин Э. И., Зотов И. В. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов (неопр.). Известия курского государственного технического университета. Курск. № 2. С. 85–89. (2004). Архивировано 28 апреля 2012 года.

[2] Зотов И. В., Титов В. С., Колосков В. А. [и др.] Организация и синтез микропрограммных мультимикроконтроллеров. Курск: изд-во «Курск», 1999. 368 с. ISBN 5-7277-0253-4

[mono-3] ¹ ² Ватутин Э. И., Зотов И. В., Титов В. С. [и др.] Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров. Курск, изд-во КурскГТУ, 2010. 200 с. ISBN 978-5-7681-0523-5

[4] Закревский А. Д. О корректности параллельных алгоритмов логического управления // Известия АН СССР. Техническая кибернетика. — 1987. — № 4. — С. 106—112.

[5] Ватутин Э. И., Зотов И. В., Титов В. С. Выявление изоморфных вхождений R-выражений при построении множества сечений параллельных алгоритмов логического управления (неопр.). Информационно-измерительные и управляющие системы. № 11, Т. 7. М.: «Радиотехника». С. 49–56. (2009). Архивировано 28 апреля 2012 года.

[4]

[1]

[3]

[5]