Аноним

Циклический участок: различия между версиями

Материал из WikiGrapp
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Циклический участок''' (''[[Loop region]]'') -
'''Циклический участок''' (''[[Loop region]]'') конструкция, позволяющая на основе анализа ''[[уграф|уграфа]]'' с <math>\,n</math> [[вершина|вершинами]] и <math>\,m</math> [[дуга|дугами]] за время <math>\,O(nm)</math> выявлять циклическую структуру [[алгоритм|алгоритма]] и находить отношения частот выполнения между всеми подмножествами его элементов, которые
конструкция, позволяющая на основе анализа ''[[уграф|уграфа]]'' с
не противоречат ''достоверным отношениям частот выполнения'', если уграф <math>\,G</math> алгоритма является ''[[регуляризуемый граф|регуляризуемым]]''.
<math>n</math> [[вершина|вершинами]] и <math>m</math> [[дуга|дугами]] за время <math>O(nm)</math> выявлять циклическую структуру [[алгоритм|алгоритма]] и находить отношения частот
выполнения между всеми подмножествами его элементов, которые
не противоречат ''достоверным отношениям частот выполнения'', если уграф <math>G</math> алгоритма является ''[[регуляризуемый граф|регуляризуемым]]''.


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


1) '''Циклический участок''' нулевого уровня в уграфе <math>G</math> один; он состоит
1) '''Циклический участок''' нулевого уровня в уграфе <math>\,G</math> один; он состоит
из всех тех вершин и дуг, которые принадлежат [[путь|путям]] по <math>G_r</math>
из всех тех вершин и дуг, которые принадлежат [[путь|путям]] по <math>\,G_r</math>
от <math>p_0</math> к <math>q_0</math>, и имеет ''головой'' вершину <math>p_0</math>;
от <math>\,p_0</math> к <math>\,q_0</math>, и имеет ''головой'' вершину <math>\,p_0</math>;


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




Строка 32: Строка 16:


==См. также ==
==См. также ==
''[[Участок повторяемости]].''
* ''[[Участок повторяемости]].''
==Литература==
==Литература==
[Касьянов/88]
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.