Управляющий граф: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 27: Строка 27:
[[Гамачное представление]], [[Достоверные отношения частоты выполнения]], [[Зона]],  
[[Гамачное представление]], [[Достоверные отношения частоты выполнения]], [[Зона]],  
[[Зонно-интервальное представление]], [[Иерархия вложенных альтов]], [[Иерархия вложенных зон]], [[Интервал]], [[Каркас уграфа]],  
[[Зонно-интервальное представление]], [[Иерархия вложенных альтов]], [[Иерархия вложенных зон]], [[Интервал]], [[Каркас уграфа]],  
[[Крупноблочная схема программы]],
[[Крупноблочная схема программ|Крупноблочная схема программы]],
[[Линейная компонента]], [[Линейный участок]],  [[Непосредственный обязательный преемник]], [[Одновходовый уграф]], [[Разборный граф]],
[[Линейная компонента]], [[Линейный участок]],  [[Непосредственный обязательный преемник]], [[Одновходовый уграф]], [[Разборный граф]],
[[Регуляризуемый уграф]], [[Сводимый управляющий граф]], [[Стандартные схемы]], [[Схемы программ]],
[[Регуляризуемый уграф]], [[Сводимый управляющий граф]], [[Стандартные схемы]], [[Схема программ|Схемы программ]],
[[Участок повторяемости]], [[Фактор-уграф]], [[Фрагмент]], [[Циклический участок]]
[[Участок повторяемости]], [[Фактор-уграф]], [[Фрагмент]], [[Циклический участок]]



Версия от 13:05, 17 февраля 2010

Управляющий граф (Control flow graph, Flow graph) --- основная модель программы, представляющая в виде орграфа поток управления (систему управляющих связей) в программе; в ней сохраняется только членение программы на операторы (команды, лучи), а также информация о тождественности операторов и возможных передачах управления между операторами.

В общем случае управляющий граф --- это помеченный упорядоченный мультиграф с выделенными начальной вершиной (входом) и непустым множеством конечных вершин (выходов).

Обычно считается, что управляющий граф является правильным и не содержит кратных дуг, вершин с совпадающими пометками и разных конечных вершин, т.е. управляющий граф --- это орграф с выделенными начальной [math]\displaystyle{ s }[/math] и конечной [math]\displaystyle{ t }[/math] вершинами, каждая вершина которого лежит хотя бы на одном [math]\displaystyle{ s-t }[/math]-пути.

Часто без ограничения общности можно считать, что из [math]\displaystyle{ t }[/math] не выходит и в [math]\displaystyle{ s }[/math] не заходит ни одна дуга управляющего графа, а из каждой вершины, отличной от [math]\displaystyle{ t }[/math], выходит одна или две дуги.

Другие названия --- Граф переходов, Уграф, Схема Мартынюка.


См. также

Альт, Аранжировка, Аранжируемый граф, Базисная нумерация, Гамак, Гамачное представление, Достоверные отношения частоты выполнения, Зона, Зонно-интервальное представление, Иерархия вложенных альтов, Иерархия вложенных зон, Интервал, Каркас уграфа, Крупноблочная схема программы, Линейная компонента, Линейный участок, Непосредственный обязательный преемник, Одновходовый уграф, Разборный граф, Регуляризуемый уграф, Сводимый управляющий граф, Стандартные схемы, Схемы программ, Участок повторяемости, Фактор-уграф, Фрагмент, Циклический участок


Литература

[Касьянов/88], [Ершов/77], [Евстигнеев/85], [Касьянов/86]