График зависимости

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июнь 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математике , информатике и цифровой электроники , А граф зависимостей представляет собой ориентированный граф , представляющий зависимости от нескольких объектов по отношению друг к другу. Из графа зависимостей можно вывести порядок оценки или отсутствие порядка оценки, учитывающего заданные зависимости.

Определение [ править ]

Принимая во внимание множество объектов и транзитивное отношение с моделирования зависимости « зависит от Ь » ( « а потребности б оценивали первый»), граф зависимостей представляет собой график с и Т является транзитивным сокращение от R . ${\ displaystyle S}$ ${\ Displaystyle R \ substeq S \ times S}$ ${\ displaystyle (a, b) \ in R}$ ${\ Displaystyle G = (S, T)}$ ${\ displaystyle T \ substeq R}$

Например, предположим, что это простой калькулятор. Этот калькулятор поддерживает присвоение постоянных значений переменным и присвоение суммы ровно двух переменных третьей переменной. Учитывая несколько уравнений, например « A = B + C ; B = 5+ D ; C = 4; D = 2;», тогда и . Вы можете вывести это отношение напрямую: A зависит от B и C , потому что вы можете добавить две переменные тогда и только тогда, когда вам известны значения обеих переменных. Таким образом, B необходимо рассчитать до того, как можно будет рассчитать A. Однако значения ${\ Displaystyle S = \ {А, В, С, D \}}$ ${\ Displaystyle R = \ {(А, В), (А, С), (В, D) \}}$ C и D известны сразу, потому что они числовые литералы.

Признание невозможных оценок [ править ]

В графе зависимостей циклы зависимостей (также называемые циклическими зависимостями ) приводят к ситуации, в которой не существует допустимого порядка оценки, потому что ни один из объектов в цикле не может быть оценен первым. Если граф зависимостей не имеет циклических зависимостей, он образует ориентированный ациклический граф , и порядок оценки может быть найден с помощью топологической сортировки . Большинство алгоритмов топологической сортировки также способны обнаруживать циклы на своих входах; однако может быть желательно выполнять обнаружение цикла отдельно от топологической сортировки, чтобы обеспечить соответствующую обработку обнаруженных циклов.

Предположим, простой калькулятор из предыдущего. Система уравнений « A = B ; B = D + C ; C = D + A ; D = 12;» содержит циклическую зависимость , образованный A , B и C , а B должна быть оценена , прежде чем A , C должно быть оценено , прежде чем Б , и должны быть оценены перед C .

Получение порядка оценки [ править ]

Правильный порядок оценки является нумерация объектов, образующих узлы графа зависимостей , так что имеет место равенство: с . Это означает, что если нумерация упорядочивает два элемента, и поэтому они будут оцениваться раньше , то не должны зависеть от . ${\ displaystyle n: S \ rightarrow \ mathbb {N}}$ ${\ Displaystyle п (а) <N (б) \ Rightarrow (а, б) \ notin R}$ ${\ displaystyle a, b \ in S}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$

Может быть более одного правильного порядка оценки. Фактически, правильная нумерация - это топологический порядок , а любой топологический порядок - это правильная нумерация. Таким образом, любой алгоритм, который выводит правильный топологический порядок, получает правильный порядок оценки.

Предположим еще раз простой калькулятор сверху. Учитывая систему уравнений « A = B + C ; B = 5+ D ; C = 4; D = 2;», правильный порядок оценки будет ( D , C , B , A ). Однако ( C , D , B , A ) также является правильным порядком оценки.

Примеры [ править ]

Графы зависимостей используются в:

Автоматизированные установщики программного обеспечения : они просматривают график в поисках необходимых, но еще не установленных программных пакетов . Зависимость задается связыванием пакетов.
Скрипты сборки программного обеспечения, такие как Unix Make , Node npm install, php composer, Twitter bower install или Apache Ant . Им необходимо знать, какие файлы были изменены, поэтому необходимо перекомпилировать только правильные файлы.
В технологии компилятора и реализации на формальном языке :
- Планирование инструкций : графы зависимостей вычисляются для операндов сборки или промежуточных инструкций и используются для определения оптимального порядка инструкций.
- Устранение мертвого кода : если от переменной не зависит никакая побочная операция, эта переменная считается мертвой и может быть удалена.
Аналитика динамического графа: GraphBolt ^[1] и KickStarter ^[2] фиксируют зависимости значений для инкрементных вычислений при изменении структуры графа.
Калькуляторы электронных таблиц . Им необходимо получить правильный порядок вычислений, аналогичный тому, который приведен в примере, использованном в этой статье.
Стандарты веб-форм, такие как XForms, чтобы знать, какие визуальные элементы обновлять при изменении данных в модели.
Видеоигры, особенно головоломки и приключенческие видеоигры , которые часто представляют собой граф зависимых отношений между внутриигровыми действиями. ^[3]

Графики зависимостей - это один из аспектов:

Типы производственных предприятий : сырье перерабатывается в продукты через несколько зависимых стадий.
Планирование работы магазина : собрание связанных теоретических проблем в области информатики.

См. Также [ править ]

График звонков
Топологическая сортировка
Зависимость от данных

Ссылки [ править ]

^ Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: управляемая зависимостями синхронная обработка потоковых графов». На Европейской конференции по компьютерным системам (EuroSys'19) . С. 25: 1–25: 16. DOI : 10.1145 / 3302424.3303974 .
^ Кеваль Вора; Раджив Гупта; Гуоцин Сюй (2017). «KickStarter: быстрые и точные вычисления потоковых графиков с помощью усеченных приближений». В Международной конференции по архитектурной поддержке языков программирования и операционных систем (ASPLOS'17) . С. 237–251. DOI : 10.1145 / 3093337.3037748 .
^ Гилберт, Рон. «Диаграммы зависимости головоломки» . Сварливый геймер . Проверено 11 января 2020 года .

Balmas, Francoise (2001) Отображение графиков зависимостей: иерархический подход , [1] wcre, p. 261, Восьмая рабочая конференция по обратному инжинирингу (WCRE'01)

[1] Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: управляемая зависимостями синхронная обработка потоковых графов». На Европейской конференции по компьютерным системам (EuroSys'19) . С. 25: 1–25: 16. DOI : 10.1145 / 3302424.3303974 .

[2] Кеваль Вора; Раджив Гупта; Гуоцин Сюй (2017). «KickStarter: быстрые и точные вычисления потоковых графиков с помощью усеченных приближений». В Международной конференции по архитектурной поддержке языков программирования и операционных систем (ASPLOS'17) . С. 237–251. DOI : 10.1145 / 3093337.3037748 .

[3] Гилберт, Рон. «Диаграммы зависимости головоломки» . Сварливый геймер . Проверено 11 января 2020 года .

[1]