Иерархия вложенных альтов: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Иерархия вложенных альтов''' ([[Hierarchy of nested alts]]) | '''Иерархия вложенных альтов''' ([[Hierarchy of nested alts]]) — | ||
множество нетривиальных [[Альт| альтов]] <math>A = \{H_{i}\}</math> [[Управляющий граф |управляющего графа]] таких, что для любых двух альтов либо их | множество нетривиальных [[Альт| альтов]] <math>\,A = \{H_{i}\}</math> [[Управляющий граф |управляющего графа]] таких, что для любых двух альтов либо их | ||
пересечение пусто, либо один целиком содержится в другом. | пересечение пусто, либо один целиком содержится в другом. | ||
Альт <math>H_{i} \in A</math> ''непосредственно вложен'' в альт | Альт <math>H_{i} \in A</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_{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} \in A</math> называется [[Альт внутренний|''внутренним'']] альтом относительно <math>\,A</math>, если в <math>\,A</math> не | ||
существует альтов, непосредственно вложенных в <math>H_{i}</math> и | существует альтов, непосредственно вложенных в <math>\,H_{i}</math> и | ||
[[Альт внешний|''внешним'']] альтом относительно <math>A</math>, если в <math>A</math> не | [[Альт внешний|''внешним'']] альтом относительно <math>\,A</math>, если в <math>\,A</math> не | ||
существует альта, в который <math>H_{i}</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_{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_{0} = G</math>, | ||
* <math>G_{r}</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>\,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>. | ||
[[Файл:Hierarchy of nested alts.png| | [[Файл:Hierarchy of nested alts.png|600px]] | ||
==Литература== | ==Литература== | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
Текущая версия от 11:40, 21 февраля 2011
Иерархия вложенных альтов (Hierarchy of nested alts) — множество нетривиальных альтов [math]\displaystyle{ \,A = \{H_{i}\} }[/math] управляющего графа таких, что для любых двух альтов либо их пересечение пусто, либо один целиком содержится в другом.
Альт [math]\displaystyle{ H_{i} \in A }[/math] непосредственно вложен в альт [math]\displaystyle{ H_{j} \in A }[/math] относительно [math]\displaystyle{ \,A }[/math], если [math]\displaystyle{ H_{i} \subset H_{j} }[/math] и в [math]\displaystyle{ \,A }[/math] не существует такого альта [math]\displaystyle{ \,H_{k} }[/math], что [math]\displaystyle{ H_{i} \subset H_{k} \subset H_{j} }[/math].
Альт [math]\displaystyle{ H_{i} \in A }[/math] называется внутренним альтом относительно [math]\displaystyle{ \,A }[/math], если в [math]\displaystyle{ \,A }[/math] не существует альтов, непосредственно вложенных в [math]\displaystyle{ \,H_{i} }[/math] и внешним альтом относительно [math]\displaystyle{ \,A }[/math], если в [math]\displaystyle{ \,A }[/math] не существует альта, в который [math]\displaystyle{ \,H_{i} }[/math] непосредственно вложен.
Последовательность уграфов [math]\displaystyle{ G_{0}, \; G_{1}, \; \ldots, \; G_{r} }[/math] называется представлением уграфа [math]\displaystyle{ \,G }[/math] в виде иерархии вложенных альтов [math]\displaystyle{ \,A }[/math] (A-граф, A-представление уграфа [math]\displaystyle{ \,G }[/math]), если
- [math]\displaystyle{ \,G_{0} = G }[/math],
- [math]\displaystyle{ \,G_{r} }[/math] — тривиальный уграф и
- для любого [math]\displaystyle{ \,i }[/math] уграф [math]\displaystyle{ \,G_{i} }[/math] получается из [math]\displaystyle{ \,G_{i-1} }[/math] стягиванием в вершины всех внешних альтов относительно [math]\displaystyle{ \bigcup \{A_{j} : \; 1 \leq j \leq i \} }[/math], где [math]\displaystyle{ \,A_{j} }[/math] — множество всех внутренних альтов относительно [math]\displaystyle{ A\setminus \bigcup \{A_{s}: \; 1 \leq s \lt j\} }[/math].
Литература
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.