- Граф зависимостей
-
В математике, информатике и цифровой электронике, граф зависимостей представляет собой ориентированный граф, отражающий зависимости нескольких объектов друг к другу. По графу зависимостей можно определить порядок вычислений или его недостатки, согласованные с данными зависимостями в графе.
Содержание
Определение
Пусть дано множество объектов S и отношение транзитивности где , моделирующее зависимость "для вычисления a нужно сначала вычислить b", тогда граф зависимостей - это граф где и R является транзитивным замыканием T.
Например, рассмотрим простую вычислительную машину (калькулятор). Пусть калькулятор поддерживает запись константы в некоторую переменную и сложение двух переменных с записью результата в некоторую третью переменную. Пусть дано несколько выражений, например, "A = B+C; B = 5+D; C=4; D=2;". Тогда и . Можно явно вывести все отношения: A зависит B и C, потому что две переменные можно складывать тогда и только тогда, когда известны значения обеих переменных. Таким образом, B и C должны быть вычислены перед A. Однако, значение D известно сразу, потому что это числовая константа.
Обнаружение невозможных вычислений
Циклические зависимости в графе зависимостей приводят к ситуации, в которой нет доступного порядка вычислений, потому что ни один из объектов цикла не может считаться первым. Если циклических зависимостей нет, то мы имеем направленный ациклический граф, и порядок вычислений может быть определен с помощью топологической сортировки. Большинство алгоритмов топологической сортировки способны обнаруживать циклы на входе, однако, желательно обнаруживать циклы отдельно от топологической сортировки.
Рассмотрим на простом примере калькулятора. Вычислительная система "A=B; B=D+C; C=D+A; D=12;" содержит циклическую зависимость. B должно быть вычислено до А, С должно быть вычислено до В, А должно быть вычислено до С.
Определение порядка вычислений
Корректный порядок вычислений - это нумерация объектов, которая упорядочивает узлы графа зависимостей так, что имеет место равенство: , где . Это означает, что если нумераций определяется, что а вычисляется перед b, то а не может зависеть от b. Более того, может существовать более одного корректного порядка вычислений. По сути, корректная нумерация является топологической сортировкой, и любая топологическая сортировка является корректной нумерацией. На самом деле, любой алгоритм, производящий корректную топологическую сортировку, одновременно определяет корректный порядок вычисления.
Снова вернемся к примеру с калькулятором. Пусть дана система: "A = B+C; B = 5+D; C=4; D=2". Корректный порядок: (D, C, B, A). Однако, (C, D, B, A) также является корректным порядком вычислений.
Примеры
Граф зависимостей используется в:
- Автоматизированной установке программного обеспечения. Происходит движение по графу в поисках пакетов программ, которые нужны, но еще не установлены. Зависимости определяются связанностью пакетов.
- В компиляторах и формальных языках:
-
- Планирование инструкций. Граф зависимостей вычисляется для операндов ассемблера или промежуточных инструкций и используется для определения оптимального порядка инструкций.
- Удаление мёртвого кода.
Графы зависимости это один из вопросов:
- Теории ограничений. Исходные данные перерабатываются в результирующие в ходе нескольких зависимых этапов.
- Планирования. Набор взаимосвязанных теоретических проблем в области компьютерных наук.
Смотрите также
Литература
- Balmas, Francoise (2001) Displaying dependence graphs: a hierarchical approach, [1] wcre, p. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)
Категории:- Проектирование программного обеспечения
- Граф (математика)
- Приложения теории графов
Wikimedia Foundation. 2010.