Управляющий граф: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Управляющий граф''' ([[Control flow graph]], [[Flow graph]]) --- | '''Управляющий граф''' ([[Control flow graph]], [[Flow graph]]) --- | ||
основная модель программы, представляющая в виде орграфа | основная модель программы, представляющая в виде [[орграф|орграфа]] | ||
поток управления (систему управляющих связей) в программе; | поток управления (систему управляющих связей) в программе; | ||
в ней сохраняется только членение программы на операторы | в ней сохраняется только членение программы на операторы | ||
| Строка 7: | Строка 7: | ||
В общем случае '''управляющий граф''' --- это помеченный упорядоченный | В общем случае '''управляющий граф''' --- это помеченный упорядоченный | ||
мультиграф с выделенными ''начальной вершиной'' (''входом'') и непустым множеством ''конечных вершин'' (''выходов''). | [[мультиграф]] с выделенными ''[[начальная вершина|начальной вершиной]]'' (''[[вход|входом]]'') и непустым множеством ''[[конечная вершина|конечных вершин]]'' (''[[выход|выходов]]''). | ||
Обычно считается, что '''управляющий граф''' является [[Правильный уграф|''правильным'']] | Обычно считается, что '''управляющий граф''' является [[Правильный уграф|''правильным'']] | ||
и не содержит кратных дуг, вершин с совпадающими пометками и разных конечных вершин, т.е. | и не содержит [[кратные дуги|кратных дуг]], [[вершина|вершин]] с совпадающими пометками и разных конечных вершин, т.е. | ||
'''управляющий граф''' --- это орграф с | '''управляющий граф''' --- это орграф с | ||
выделенными ''начальной'' <math>s</math> и ''конечной'' <math>t</math> вершинами, | выделенными ''начальной'' <math>s</math> и ''конечной'' <math>t</math> вершинами, | ||
| Строка 17: | Строка 17: | ||
Часто без ограничения общности можно считать, что | Часто без ограничения общности можно считать, что | ||
из <math>t</math> не выходит и в <math>s</math> не заходит ни одна дуга '''управляющего графа''', а | из <math>t</math> не выходит и в <math>s</math> не заходит ни одна [[дуга]] '''управляющего графа''', а | ||
из каждой вершины, отличной от <math>t</math>, выходит одна или две дуги. | из каждой вершины, отличной от <math>t</math>, выходит одна или две дуги. | ||
Версия от 17:25, 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]