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

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

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

Граф-схема алгоритма — конечный связный ориентированный граф , вершины которого соответствуют операторам, а дуги задают порядок следования вершин алгоритма, где — число вершин графа, — число дуг. В более широком смысле вершинам графа соответствуют не только операторные вершины, но и условные, начальная и конечная вершины и т.д. При рассмотрении параллельных алгоритмов вводится понятие параллельной граф-схемы алгоритма, в состав которой входят вершины распараллеливания/синхронизации, функциональность которых обычно совмещается. Иногда в состав ГСА вводятся вершины дополнительных типов: объединения альтернативных дуг, фиктивные операторные вершины, вершины маркировки, ждущие вершины.

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

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