Управляющий граф: различия между версиями
Перейти к навигации
Перейти к поиску
KVN (обсуждение | вклад) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показаны 4 промежуточные версии 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. | |||
[[Категория: Потоковый анализ программ]] | [[Категория: Потоковый анализ программ]] | ||
[[Категория: Теория схем программ ]] | |||
Текущая версия от 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.