Иерархия вложенных альтов: различия между версиями

'''Иерархия вложенных альтов''' ([[Hierarchy of nested alts]]) —

множество нетривиальных [[Альт| альтов]] <math>\,A = \{H_{i}\}</math> [[Управляющий граф |управляющего графа]] таких, что для любых двух альтов либо их

<math>H_{j} \in A</math> относительно <math>\,A</math>, если <math>H_{i} \subset H_{j}</math> и в <math>\,A</math> не существует такого альта <math>\,H_{k}</math>, что <math>H_{i} \subset H_{k} \subset H_{j}</math>.

Альт <math>H_{i} \in A</math> называется [[Альт внутренний|''внутренним'']] альтом относительно <math>\,A</math>, если в <math>\,A</math> не

существует альтов, непосредственно вложенных в <math>\,H_{i}</math> и

[[Альт внешний|''внешним'']] альтом относительно <math>\,A</math>, если в <math>\,A</math> не

существует альта, в который <math>\,H_{i}</math> непосредственно вложен.

Последовательность уграфов <math>G_{0}, \; G_{1}, \; \ldots, \; G_{r}</math> называется представлением [[Уграф |уграфа]] <math>\,G</math> в виде '''иерархии вложенных альтов''' <math>\,A</math> ([[A-граф|''A-граф'']], [[A-представление уграфа|''A-представление уграфа'']] <math>\,G</math>), если  

 

* <math>\,G_{0} = G</math>,  

 

* <math>\,G_{r}</math> — [[Тривиальный граф|тривиальный]] уграф и  

 

* для любого <math>\,i</math> уграф <math>\,G_{i}</math> получается из <math>\,G_{i-1}</math> стягиванием в вершины всех внешних альтов относительно <math>\bigcup \{A_{j} : \; 1 \leq j \leq i \}</math>, где <math>\,A_{j}</math> — множество всех внутренних альтов относительно <math>A\setminus \bigcup \{A_{s}: \; 1 \leq s < j\}</math>.

 

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