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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Участок повторяемости''' (''Repeatedly executed region'') - конструкция, позволяющая на о...)
 
Нет описания правки
Строка 1: Строка 1:
'''Участок повторяемости''' (''Repeatedly executed region'') -  
'''Участок повторяемости''' (''[[Repeatedly executed region]]'') -  
конструкция, позволяющая на основе анализа ''уграфа''
конструкция, позволяющая на основе анализа ''[[уграф|уграфа]]''
эффективно выявлять циклическую структуру алгоритма и
эффективно выявлять циклическую структуру [[алгоритм|алгоритма]] и
находить отношения частот выполнения между всеми
находить отношения частот выполнения между всеми
подмножествами его элементов, которые не противоречат  
подмножествами его элементов, которые не противоречат  
''достоверным отношениям частот выполнения''.
''достоверным отношениям частот выполнения''.


Пусть <math>G</math> --- некоторый ''уграф'' с начальной вершиной
Пусть <math>G</math> - некоторый ''уграф'' с [[начальная вершина|начальной вершиной]]
<math>p_0</math> и конечной <math>q_0</math>, <math>V</math> --- множество всех ''простых путей'' по <math>G</math> от <math>p_0</math> до <math>q_0</math>, а <math>W</math> --- множество всех ее ''простых контуров''.
<math>p_0</math> и [[конечная вершина|конечной]] <math>q_0</math>, <math>V</math> - множество всех ''[[простой путь|простых путей]]'' по <math>G</math> от <math>p_0</math> до <math>q_0</math>, а <math>W</math> - множество всех ее ''[[простой контур|простых контуров]]''.


Элементы множества <math>E=V \cup W</math> называются ''цепочками''
Элементы множества <math>E=V \cup W</math> называются ''[[цепочка|цепочками]]''
уграфа <math>G</math>: ''простыми'', если они принадлежат <math>V</math>, и  
уграфа <math>G</math>: ''простыми'', если они принадлежат <math>V</math>, и  
''замкнутыми'', если они содержатся в <math>W</math>. Говорят, что
''замкнутыми'', если они содержатся в <math>W</math>. Говорят, что
замкнутая цепочка <math>P_1</math> ''вложена'' в замкнутую цепочку
замкнутая цепочка <math>P_1</math> ''вложена'' в замкнутую цепочку
<math>P_2</math>, если <math>P_2</math> содержит все вершины и все дуги цепочки
<math>P_2</math>, если <math>P_2</math> содержит все [[вершина|вершины]] и все [[дуга|дуги]] цепочки
<math>P_1</math>, за исключением одной дуги. <math>P_1</math> ''непосредственно вложена'' в замкнутую цепочку <math>P_2</math>, если <math>P_1</math> вложена в
<math>P_1</math>, за исключением одной дуги. <math>P_1</math> ''непосредственно вложена'' в замкнутую цепочку <math>P_2</math>, если <math>P_1</math> вложена в
<math>P_2</math> и не существует такой замкнутой цепочки <math>P_3</math>, что
<math>P_2</math> и не существует такой замкнутой цепочки <math>P_3</math>, что
Строка 20: Строка 20:
цепочки, в которую <math>P</math> вложена. Множество цепочек <math>C</math>
цепочки, в которую <math>P</math> вложена. Множество цепочек <math>C</math>
называется ''зацепленными'', если оно состоит из попарно
называется ''зацепленными'', если оно состоит из попарно
не вложенных замкнутых цепочек и граф, образованный всеми
не вложенных замкнутых цепочек и [[граф]], образованный всеми
теми вершинами и дугами, которые принадлежат цепочкам из
теми вершинами и дугами, которые принадлежат цепочкам из
<math>C</math>, является сильно связным. Пусть <math>C_1</math> и <math>C_2</math> --- два
<math>C</math>, является сильно связным. Пусть <math>C_1</math> и <math>C_2</math> - два
зацепленных множества замкнутых цепочек схемы <math>G; C_1</math> ''(непосредственно) вложено'' в <math>C_2</math>, если пересечение <math>C_1</math> и
зацепленных множества замкнутых цепочек схемы <math>G; C_1</math> ''(непосредственно) вложено'' в <math>C_2</math>, если пересечение <math>C_1</math> и
<math>C_2</math> пусто и для любой цепочки из <math>C_1</math> найдется цепочка в
<math>C_2</math> пусто и для любой цепочки из <math>C_1</math> найдется цепочка в
<math>C_2</math>, в которую она (непосредственно) вложена.
<math>C_2</math>, в которую она (непосредственно) вложена.


'''У.п.''' уграфа <math>G</math> определяются
'''Участок повторяемости''' уграфа <math>G</math> определяются
следующим образом:
следующим образом:


1) <math>G</math> содержит единственный ''участок повторяемости нулевого уровня'', состоящий из всех простых цепочек <math>V</math>;
1) <math>G</math> содержит единственный ''участок повторяемости нулевого уровня'', состоящий из всех простых цепочек <math>V</math>;


2) ''участки повторяемости первого уровня'' <math>G</math> --- это
2) ''участки повторяемости первого уровня'' <math>G</math> - это
максимальные зацепленные множества его внешних замкнутых
максимальные зацепленные множества его внешних замкнутых
цепочек;
цепочек;
Строка 41: Строка 41:
(<math>i-1</math>)-го уровня.
(<math>i-1</math>)-го уровня.


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

Версия от 12:30, 18 февраля 2010

Участок повторяемости (Repeatedly executed region) - конструкция, позволяющая на основе анализа уграфа эффективно выявлять циклическую структуру алгоритма и находить отношения частот выполнения между всеми подмножествами его элементов, которые не противоречат достоверным отношениям частот выполнения.

Пусть [math]\displaystyle{ G }[/math] - некоторый уграф с начальной вершиной [math]\displaystyle{ p_0 }[/math] и конечной [math]\displaystyle{ q_0 }[/math], [math]\displaystyle{ V }[/math] - множество всех простых путей по [math]\displaystyle{ G }[/math] от [math]\displaystyle{ p_0 }[/math] до [math]\displaystyle{ q_0 }[/math], а [math]\displaystyle{ W }[/math] - множество всех ее простых контуров.

Элементы множества [math]\displaystyle{ E=V \cup W }[/math] называются цепочками уграфа [math]\displaystyle{ G }[/math]: простыми, если они принадлежат [math]\displaystyle{ V }[/math], и замкнутыми, если они содержатся в [math]\displaystyle{ W }[/math]. Говорят, что замкнутая цепочка [math]\displaystyle{ P_1 }[/math] вложена в замкнутую цепочку [math]\displaystyle{ P_2 }[/math], если [math]\displaystyle{ P_2 }[/math] содержит все вершины и все дуги цепочки [math]\displaystyle{ P_1 }[/math], за исключением одной дуги. [math]\displaystyle{ P_1 }[/math] непосредственно вложена в замкнутую цепочку [math]\displaystyle{ P_2 }[/math], если [math]\displaystyle{ P_1 }[/math] вложена в [math]\displaystyle{ P_2 }[/math] и не существует такой замкнутой цепочки [math]\displaystyle{ P_3 }[/math], что [math]\displaystyle{ P_1 }[/math] вложена в [math]\displaystyle{ P_3 }[/math], а [math]\displaystyle{ P_3 }[/math] вложена в [math]\displaystyle{ P_2 }[/math]. Цепочка [math]\displaystyle{ P \in W }[/math] называется внешней, если в [math]\displaystyle{ W }[/math] не существует такой цепочки, в которую [math]\displaystyle{ P }[/math] вложена. Множество цепочек [math]\displaystyle{ C }[/math] называется зацепленными, если оно состоит из попарно не вложенных замкнутых цепочек и граф, образованный всеми теми вершинами и дугами, которые принадлежат цепочкам из [math]\displaystyle{ C }[/math], является сильно связным. Пусть [math]\displaystyle{ C_1 }[/math] и [math]\displaystyle{ C_2 }[/math] - два зацепленных множества замкнутых цепочек схемы [math]\displaystyle{ G; C_1 }[/math] (непосредственно) вложено в [math]\displaystyle{ C_2 }[/math], если пересечение [math]\displaystyle{ C_1 }[/math] и [math]\displaystyle{ C_2 }[/math] пусто и для любой цепочки из [math]\displaystyle{ C_1 }[/math] найдется цепочка в [math]\displaystyle{ C_2 }[/math], в которую она (непосредственно) вложена.

Участок повторяемости уграфа [math]\displaystyle{ G }[/math] определяются следующим образом:

1) [math]\displaystyle{ G }[/math] содержит единственный участок повторяемости нулевого уровня, состоящий из всех простых цепочек [math]\displaystyle{ V }[/math];

2) участки повторяемости первого уровня [math]\displaystyle{ G }[/math] - это максимальные зацепленные множества его внешних замкнутых цепочек;

3) участком повторяемости [math]\displaystyle{ i }[/math]-го уровня, [math]\displaystyle{ i\gt 1 }[/math], является каждое максимальное зацепленное множество замкнутых цепочек, непосредственно вложенных в некоторый участок повторяемости ([math]\displaystyle{ i-1 }[/math])-го уровня.

См. также

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

Литература

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