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

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

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

Пусть G_0=G, G_1, \ldots, 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.


Loop region.gif


См. также

Литература

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