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

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

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

Элементы множества $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$)-го уровня.

См. также

Циклический участок.

Литература

[Касьянов/88]