4625
правок
Участок повторяемости: различия между версиями
Материал из WikiGrapp
нет описания правки
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] | ||
