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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Управляющий граф''' (Control flow graph, Flow graph) --- основная модель программы, пр...)
 
Нет описания правки
 
(не показано 5 промежуточных версий 2 участников)
Строка 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>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

Управляющий граф (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.