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

Циклический участок (Loop region) — конструкция, позволяющая на основе анализа уграфа с $n$ вершинами и $m$ дугами за время $O(nm)$ выявлять циклическую структуру алгоритма и находить отношения частот выполнения между всеми подмножествами его элементов, которые не противоречат достоверным отношениям частот выполнения, если уграф $G$ алгоритма является регуляризуемым.

Пусть $G_0=G,G_1,\dots ,G_r$ — такая последовательность уграфов, в которой только $G_r$ не содержит нетривиальных бикомпонент, и для любого $i$ уграф $G_i$ получается из $G_{i-1}$ удалением в каждой нетривиальной бикомпоненте $C$ уграфа $G_{i-1}$ всех дуг, заходящих в один из ее входов. Эту входную вершину бикомпоненты $C$ называют ее головой, а удаленные дуги — дугами повторения уровня $i$. Пусть $I_i$ обозначает множество всех дуг повторения уровня $i.$ Части схемы $G,$ называемые ее циклическими участками, определяются по следующим двум правилам:

1) Циклический участок нулевого уровня в уграфе $G$ один; он состоит из всех тех вершин и дуг, которые принадлежат путям по $G_r$ от $p_0$ к $q_0$, и имеет головой вершину $p_0$;

2) пусть для некоторого $i,i>0,C$ — бикомпонента схемы $G_{i-1}$ с головой $p,$ тогда в $G$ имеется циклический участок уровня $i$ с головой $p;$ он состоит из всех тех вершин и дуг, из которых достижима $p$ в графе, полученном из $C$ удалением всех дуг повторения уровня $j>i.$

См. также

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

Литература

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