Интернет магазин китайских планшетных компьютеров



Компьютеры - Граф-схема алгоритма

23 января 2011





Ждущая вершина алгоритма

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

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

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



Просмотров: 1838


<<< Гистограмма (статистика)
График движения поездов >>>