Участок повторяемости: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Участок повторяемости''' (''Repeatedly executed region'') - конструкция, позволяющая на о...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>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> определяются | ||
следующим образом: | следующим образом: | ||
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]