Graf závislosti

Graf závislosti je orientovaný graf , který zobrazuje poměr množiny prvků určité kolekce v souladu s vybraným tranzitivním vztahem nad ním.

Tento graf se často používá v informatice a digitální elektronice , zejména se z grafu závislostí určuje pořadí výpočtů nebo jeho nedostatky v souladu s danými závislostmi v grafu.

Definice

Nechť existuje množina objektů a vztah tranzitivity kde , modelování závislosti „pro výpočet, musíte nejprve vypočítat “, pak graf závislosti je grafem kde a je tranzitivní uzávěr . $S$ $R=S\krát S$ $(a,b)\v R$ $A$ $b$ $G=(S,T)$ $T\subseteq R$ $R$ $T$

Některá kalkulačka například podporuje zápis konstanty do nějaké proměnné a přidání dvou proměnných a zápis výsledku do nějaké třetí proměnné. Nechť je uvedeno několik výrazů, například . Potom a . Je možné explicitně odvodit všechny vztahy: závisí na a , protože dvě proměnné lze přidat tehdy a pouze tehdy , pokud jsou známy hodnoty obou proměnných. Tak, a musí být spočítán před . Hodnota je však známa okamžitě, protože se jedná o číselnou konstantu. $A=B+C;B=5+D;C=4;D=2$ $S={A,B,C,D}$ $R={(A,B),(A,C),(B,D)}$ $A$ $B$ $C$ $B$ $C$ $A$ $D$

Detekce nemožných výpočtů

Cyklické závislosti v grafu závislostí vedou k situaci, kdy není k dispozici žádné pořadí vyhodnocení, protože žádný z objektů v cyklu nelze uvažovat jako první. Pokud neexistují žádné cyklické závislosti, pak máme orientovaný acyklický graf a pořadí vyhodnocení lze určit pomocí topologického řazení . Většina topologických třídicích algoritmů je schopna detekovat cykly na vstupu, nicméně je žádoucí detekovat cykly odděleně od topologického třídění.

V příkladu založeném na kalkulačce obsahuje výpočetní systém kruhovou závislost. musí hodnotit do , musí hodnotit do , musí hodnotit do . $A=B;B=D+C;C=D+A;D=12$ $B$ $A$ $C$ $B$ $A$ $C$

Určení pořadí hodnocení

Správné pořadí výpočtů je číslování objektů, které seřadí uzly grafu závislosti tak, aby nastala rovnost: , kde . To znamená, že pokud je definován výčet, který je vyhodnocen dříve , nemůže záviset na . Navíc může existovat více než jedno správné pořadí hodnocení. Správné číslování je v podstatě topologické řazení a jakékoli topologické řazení je správné číslování. Ve skutečnosti každý algoritmus, který vytváří správné topologické řazení, zároveň určuje správné pořadí vyhodnocení. $n:S\šipka doprava N$ $n(a)<n(b)\Šipka doprava (a,b)\notin R$ $a,b\in S$ $A$ $b$ $A$ $b$

Pro systém (v příkladu s kalkulačkou) je správné pořadí: , je však také správné pořadí výpočtu. $A=B+C;B=5+D;C=4;D=2$ $(D,C,B,A)$ $(C,D,B,A)$

Příklady

Graf závislosti se používá v:

Automatická instalace softwaru. [1] Pohybuje se po grafu při hledání softwarových balíčků , které jsou potřeba, ale ještě nejsou nainstalovány. Závislosti jsou definovány příbuzností balíčku .
V kompilátorech a formálních jazycích :

Pokyny pro plánování . Graf závislosti se vypočítává pro operandy assembleru nebo pomocné instrukce a používá se k určení optimálního pořadí instrukcí.
Odstranění mrtvého kódu .

Grafy závislostí jsou jednou z otázek:

Teorie omezení . Počáteční data jsou zpracována do výsledných dat v průběhu několika závislých fází.
Plánování. Soubor vzájemně souvisejících teoretických problémů v informatice.

Viz také

Poznámky

↑ Například v nástrojích make

Literatura

Balmas, Francoise (2001) Zobrazení grafů závislostí: hierarchický přístup , [1] wcre, str. 261, Osmá pracovní konference o zpětném inženýrství (WCRE'01)

Odkazy

výzkumný projekt kompilátoru. Graf závislostí archivován 4. března 2016 na Wayback Machine