Циклический участок
Циклический участок (Loop region) — конструкция, позволяющая на основе анализа уграфа с [math]\displaystyle{ \,n }[/math] вершинами и [math]\displaystyle{ \,m }[/math] дугами за время [math]\displaystyle{ \,O(nm) }[/math] выявлять циклическую структуру алгоритма и находить отношения частот выполнения между всеми подмножествами его элементов, которые не противоречат достоверным отношениям частот выполнения, если уграф [math]\displaystyle{ \,G }[/math] алгоритма является регуляризуемым.
Пусть [math]\displaystyle{ G_0=G, G_1, \ldots, G_r }[/math] — такая последовательность уграфов, в которой только [math]\displaystyle{ \,G_r }[/math] не содержит нетривиальных бикомпонент, и для любого [math]\displaystyle{ \,i }[/math] уграф [math]\displaystyle{ \,G_i }[/math] получается из [math]\displaystyle{ \,G_{i-1} }[/math] удалением в каждой нетривиальной бикомпоненте [math]\displaystyle{ \,C }[/math] уграфа [math]\displaystyle{ \,G_{i-1} }[/math] всех дуг, заходящих в один из ее входов. Эту входную вершину бикомпоненты [math]\displaystyle{ \,C }[/math] называют ее головой, а удаленные дуги — дугами повторения уровня [math]\displaystyle{ \,i }[/math]. Пусть [math]\displaystyle{ \,I_i }[/math] обозначает множество всех дуг повторения уровня [math]\displaystyle{ \,i. }[/math] Части схемы [math]\displaystyle{ \,G, }[/math] называемые ее циклическими участками, определяются по следующим двум правилам:
1) Циклический участок нулевого уровня в уграфе [math]\displaystyle{ \,G }[/math] один; он состоит из всех тех вершин и дуг, которые принадлежат путям по [math]\displaystyle{ \,G_r }[/math] от [math]\displaystyle{ \,p_0 }[/math] к [math]\displaystyle{ \,q_0 }[/math], и имеет головой вершину [math]\displaystyle{ \,p_0 }[/math];
2) пусть для некоторого [math]\displaystyle{ i,\,i\gt 0,\,C }[/math] — бикомпонента схемы [math]\displaystyle{ \,G_{i-1} }[/math] с головой [math]\displaystyle{ \,p, }[/math] тогда в [math]\displaystyle{ \,G }[/math] имеется циклический участок уровня [math]\displaystyle{ \,i }[/math] с головой [math]\displaystyle{ \,p; }[/math] он состоит из всех тех вершин и дуг, из которых достижима [math]\displaystyle{ \,p }[/math] в графе, полученном из [math]\displaystyle{ \,C }[/math] удалением всех дуг повторения уровня [math]\displaystyle{ \,j\gt i. }[/math]
См. также
Литература
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
