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

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

Пусть <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> — множество всех ее ''[[простой контур|простых контуров]]''.

[[Файл:Repeatedly executed region.gif|650px]]

Элементы множества <math>E=V \cup W</math> называются ''[[цепочка|цепочками]]'' уграфа <math>\,G</math>: ''простыми'', если они принадлежат <math>\,V</math>, и ''замкнутыми'', если они содержатся в <math>\,W</math>. Говорят, что замкнутая цепочка <math>\,P_1</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_2</math> и не существует такой замкнутой цепочки <math>\,P_3</math>, что

<math>\,P_1</math> вложена в <math>\,P_3</math>, а <math>\,P_3</math> вложена в <math>\,P_2</math>. Цепочка <math>\,P \in W</math> называется внешней, если в <math>\,W</math> не существует такой цепочки, в которую <math>\,P</math> вложена. Множество цепочек <math>\,C</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>\,C_2</math> пусто и для любой цепочки из <math>\,C_1</math> найдется цепочка в <math>\,C_2</math>, в которую она (непосредственно) вложена.

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

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

2) ''участки повторяемости первого уровня'' <math>\,G</math> — это максимальные зацепленные множества его внешних замкнутых цепочек;

3) ''участком повторяемости <math>\,i</math>-го уровня'', <math>\,i>1</math>, является

каждое максимальное зацепленное множество замкнутых цепочек, непосредственно вложенных в некоторый участок повторяемости (<math>\,i-1</math>)-го уровня.

* ''[[Циклический участок]].''

* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.