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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Циклический участок''' (''Loop region'') - конструкция, позволяющая на основе анал...)
 
Нет описания правки
Строка 1: Строка 1:
'''Циклический участок''' (''Loop region'') -  
'''Циклический участок''' (''[[Loop region]]'') -  
конструкция, позволяющая на основе анализа ''уграфа'' с
конструкция, позволяющая на основе анализа ''[[уграф|уграфа]]'' с
<math>n</math> вершинами и <math>m</math> дугами за время <math>O(nm)</math> выявлять
<math>n</math> [[вершина|вершинами]] и <math>m</math> [[дуга|дугами]] за время <math>O(nm)</math> выявлять циклическую структуру [[алгоритм|алгоритма]] и находить отношения частот
циклическую структуру алгоритма и находить отношения частот
выполнения между всеми подмножествами его элементов, которые
выполнения между всеми подмножествами его элементов, которые
не противоречат ''достоверным отношениям частот выполнения'', если уграф <math>G</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>G_r</math> не содержит нетривиальных
''бикомпонент'', и для любого <math>i</math> уграф <math>G_i</math> получается
''[[бикомпонента|бикомпонент]]'', и для любого <math>i</math> уграф <math>G_i</math> получается
из <math>G_{i-1}</math> удалением в каждой нетривиальной бикомпоненте
из <math>G_{i-1}</math> удалением в каждой нетривиальной бикомпоненте
<math>C</math> уграфа <math>G_{i-1}</math> всех дуг, заходящих в один из ее  
<math>C</math> уграфа <math>G_{i-1}</math> всех дуг, заходящих в один из ее  
''входов''. Эту ''входную вершину'' бикомпоненты <math>C</math> называют
''[[вход|входов]]''. Эту ''[[входная вершина подграфа|входную вершину]]'' бикомпоненты <math>C</math> называют ее ''[[голова|головой]]'', а удаленные дуги - ''[[дуга повторения уровня i|дугами повторения уровня <math>i</math>]]''.
ее ''головой'', а удаленные дуги --- ''дугами повторения уровня <math>i</math>''.
Пусть <math>I_i</math> обозначает множество
Пусть <math>I_i</math> обозначает множество
всех дуг повторения уровня <math>i</math>.
всех дуг повторения уровня <math>i</math>.
Части схемы <math>G</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</math>, <math>i>0</math>, <math>C</math> - бикомпонента схемы
<math>G_{i-1}</math> с головой <math>p</math>, тогда в <math>G</math> имеется циклический
<math>G_{i-1}</math> с головой <math>p</math>, тогда в <math>G</math> имеется циклический
участок уровня <math>i</math> с головой <math>p</math>; он состоит из всех тех
участок уровня <math>i</math> с головой <math>p</math>; он состоит из всех тех
Строка 29: Строка 27:
из <math>C</math> удалением всех дуг повторения уровня <math>j>i</math>.
из <math>C</math> удалением всех дуг повторения уровня <math>j>i</math>.


См. также ''Участок повторяемости.''
==См. также ==
''[[Участок повторяемости]].''
==Литература==
==Литература==
[Касьянов/88]
[Касьянов/88]

Версия от 13:59, 7 мая 2010

Циклический участок (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 }[/math], [math]\displaystyle{ i\gt 0 }[/math], [math]\displaystyle{ 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].

См. также

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

Литература

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