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

Текущая версия от 11:20, 23 сентября 2011

Управляющий граф (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], выходит одна или две дуги.

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

См. также

Литература

Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.

Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.

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

@@ Строка 1: / Строка 1: @@
-'''Управляющий граф''' ([[Control flow graph]], [[Flow graph]]) ---
+'''Управляющий граф''' ([[Control flow graph]], [[Flow graph]]) — основная модель программы, представляющая в виде [[орграф|орграфа]] поток управления (систему управляющих связей) в программе; в ней сохраняется только членение программы на операторы (команды, лучи), а также информация о тождественности операторов и возможных передачах управления между операторами.
-основная модель программы, представляющая в виде орграфа
-поток управления (систему управляющих связей) в программе;
-в ней сохраняется только членение программы на операторы
-(команды, лучи), а также информация о тождественности операторов
-и возможных передачах управления между операторами.
-В общем случае '''Управляющий граф''' --- это помеченный упорядоченный
+В общем случае '''управляющий граф''' — это помеченный упорядоченный [[мультиграф]] с выделенными ''[[начальная вершина|начальной вершиной]]'' (''[[вход|входом]]'') и непустым множеством ''[[конечная вершина|конечных вершин]]'' (''[[выход|выходов]]'').
-мультиграф с выделенными ''начальной вершиной'' (''входом'') и непустым множеством ''конечных вершин'' (''выходов'').
-Обычно считается, что '''Управляющий граф'''  является [[Правильный уграф|''правильным'']]
+Обычно считается, что '''управляющий граф'''  является [[Правильный уграф|''правильным'']]
-и не содержит кратных дуг, вершин с совпадающими пометками и разных конечных вершин, т.е.
+и не содержит [[кратные дуги|кратных дуг]], [[вершина|вершин]] с совпадающими пометками и разных конечных вершин, т.е. '''управляющий граф''' — это орграф с выделенными ''начальной'' <math>s</math> и ''конечной'' <math>t</math> вершинами, каждая вершина которого лежит хотя
-'''управляющий граф''' --- это орграф с
-выделенными ''начальной'' <math>s</math> и ''конечной'' <math>t</math> вершинами,
-каждая вершина которого лежит хотя
 бы на одном <math>s-t</math>-пути.
-Часто без ограничения общности можно считать, что
+Часто без ограничения общности можно считать, что из <math>t</math> не выходит и в <math>s</math> не заходит ни одна [[дуга]] '''управляющего графа''', а из каждой вершины, отличной от <math>t</math>, выходит одна или две дуги.
-из <math>t</math> не выходит и в <math>s</math> не заходит ни одна дуга '''управляющего графа''', а
-из каждой вершины, отличной от <math>t</math>, выходит одна или две дуги.
-Другие названия --- [[Граф переходов|''Граф переходов'']], [[Уграф|''Уграф'']], [[Схема Мартынюка|''Схема Мартынюка.'']]
+Другие названия — ''[[Граф переходов]]'', ''[[Уграф]]'', ''[[Схема Мартынюка]].''
 == См. также ==
-[[Альт]], [[Аранжировка]], [[Аранжируемый граф]], [[Базисная нумерация]], [[Гамак]],
+* ''[[Альт]],''
-[[Гамачное представление]], [[Достоверные отношения частоты выполнения]], [[Зона]],
+* ''[[Аранжировка]],''
-[[Зонно-интервальное представление]], [[Иерархия вложенных альтов]], [[Иерархия вложенных зон]], [[Интервал]], [[Каркас уграфа]],
+* ''[[Аранжируемый граф]],''
-[[Крупноблочная схема программы]],
+* ''[[Базисная нумерация]],''
-[[Линейная компонента]], [[Линейный участок]],  [[Непосредственный обязательный преемник]], [[Одновходовый уграф]], [[Разборный граф]],
+* ''[[Гамак]],''
-[[Регуляризуемый уграф]], [[Сводимый управляющий граф]], [[Стандартные схемы]], [[Схемы программ]],
+* ''[[Гамачное представление]],''
-[[Участок повторяемости]], [[Фактор-уграф]], [[Фрагмент]], [[Циклический участок]]
+* ''[[Достоверные отношения частоты выполнения]],''
+* ''[[Зона]],''
+* ''[[Зонно-интервальное представление]],''
+* ''[[Иерархия вложенных альтов]],''
+* ''[[Иерархия вложенных зон]],''
+* ''[[Интервал]],''
+* ''[[Каркас уграфа]],''
+* ''[[Крупноблочная схема программ]],''
+* ''[[Линейная компонента]],''
+* ''[[Линейный участок]],''
+* ''[[Непосредственный обязательный преемник]],''
+* ''[[Одновходовый граф|Одновходовый уграф]],''
+* ''[[Разборный граф]],''
+* ''[[Регуляризуемый уграф]],''
+* ''[[Сводимый управляющий граф]],''
+* ''[[Стандартные схемы]],''
+* ''[[Схема программ]],''
+* ''[[Участок повторяемости]],''
+* ''[[Фактор-уграф]],''
+* ''[[Фрагмент]],''
+* ''[[Циклический участок]].''
+== Литература ==
+* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
+* Ершов А.П. Введение в теоретическое программирование. Беседы о методе. — М.: Наука, 1977.
+* Касьянов В.Н. Теоретико-графовые задачи анализа управляющих графов транслируемых программ // Исследования по прикладной теории графов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
+* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
-== Литература ==
-[Касьянов/88],
+[[Категория: Потоковый анализ программ]]
-[Ершов/77],
+[[Категория: Теория схем программ ]]
-[Евстигнеев/85],
-[Касьянов/86]

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

Текущая версия от 11:20, 23 сентября 2011

См. также

Литература

Навигация

Поиск