Участок повторяемости

Материал из WikiGrapp
Перейти к:навигация, поиск

Участок повторяемости (Repeatedly executed region) — конструкция, позволяющая на основе анализа уграфа эффективно выявлять циклическую структуру алгоритма и находить отношения частот выполнения между всеми подмножествами его элементов, которые не противоречат достоверным отношениям частот выполнения.

Пусть \,G — некоторый уграф с начальной вершиной \,p_0 и конечной \,q_0, \,V — множество всех простых путей по \,G от \,p_0 до \,q_0, а \,W — множество всех ее простых контуров.

Repeatedly executed region.gif


Элементы множества E=V \cup W называются цепочками уграфа \,G: простыми, если они принадлежат \,V, и замкнутыми, если они содержатся в \,W. Говорят, что замкнутая цепочка \,P_1 вложена в замкнутую цепочку \,P_2, если \,P_2 содержит все вершины и все дуги цепочки \,P_1, за исключением одной дуги. \,P_1 непосредственно вложена в замкнутую цепочку \,P_2, если \,P_1 вложена в \,P_2 и не существует такой замкнутой цепочки \,P_3, что \,P_1 вложена в \,P_3, а \,P_3 вложена в \,P_2. Цепочка \,P \in W называется внешней, если в \,W не существует такой цепочки, в которую \,P вложена. Множество цепочек \,C называется зацепленными, если оно состоит из попарно не вложенных замкнутых цепочек и граф, образованный всеми теми вершинами и дугами, которые принадлежат цепочкам из \,C, является сильно связным. Пусть \,C_1 и \,C_2 — два зацепленных множества замкнутых цепочек схемы G;\, C_1 (непосредственно) вложено в \,C_2, если пересечение \,C_1 и \,C_2 пусто и для любой цепочки из \,C_1 найдется цепочка в \,C_2, в которую она (непосредственно) вложена.

Участок повторяемости уграфа \,G определяются следующим образом:

1) \,G содержит единственный участок повторяемости нулевого уровня, состоящий из всех простых цепочек \,V;

2) участки повторяемости первого уровня \,G — это максимальные зацепленные множества его внешних замкнутых цепочек;

3) участком повторяемости \,i-го уровня, \,i>1, является каждое максимальное зацепленное множество замкнутых цепочек, непосредственно вложенных в некоторый участок повторяемости (\,i-1)-го уровня.

См. также

Литература

  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.