Wykres zależności

W matematyce , informatyce i elektronice cyfrowej wykres zależności jest skierowanym wykresem przedstawiającym wzajemne zależności kilku obiektów. Możliwe jest wyprowadzenie kolejności oceny lub braku kolejności oceny, która respektuje dane zależności z grafu zależności.

Definicja

$R \ subseteq S \ razy S}$ uwagę zbiór obiektów i relację przechodnią $Displaystyle$ z ${\ Displaystyle (a, b) \ w R }$ modelując zależność „ a zależy od b ” („ a wymaga najpierw oceny b ”), wykres zależności jest wykresem ${\ Displaystyle G = (S, T)}$ z $T\subseteq R}$ ${\$ displaystyle przechodnia redukcja R .

Załóżmy na przykład prosty kalkulator. Ten kalkulator obsługuje przypisywanie stałych wartości do zmiennych i przypisywanie sumy dokładnie dwóch zmiennych do trzeciej zmiennej. Biorąc pod uwagę kilka równań, takich jak „ ZA = b + do ; b = 5+ re ; do = 4; re = 2;”, to ${\ Displaystyle S = \ {A, B, do, re \}}$ i ${\ Displaystyle R = \ {(A, b), (A, C), (B$ . Możesz wyprowadzić tę relację bezpośrednio: A zależy od B i C , ponieważ możesz dodać dwie zmienne wtedy i tylko wtedy, gdy znasz wartości obu zmiennych. Zatem B musi zostać obliczone przed obliczeniem A. Jednak wartości C i D są znane od razu, ponieważ są literałami liczbowymi.

Rozpoznawanie ocen niemożliwych

W grafie zależności cykle zależności (zwane również zależnościami cyklicznymi ) prowadzą do sytuacji, w której nie istnieje żadna ważna kolejność oceny, ponieważ żaden z obiektów w cyklu nie może być oceniony jako pierwszy. Jeśli graf zależności nie ma żadnych zależności kołowych, tworzy skierowany graf acykliczny , a kolejność oceny można znaleźć za pomocą sortowania topologicznego . Większość algorytmów sortowania topologicznego jest również w stanie wykrywać cykle na swoich danych wejściowych; jednakże może być pożądane przeprowadzenie wykrywania cykli oddzielnie od sortowania topologicznego w celu zapewnienia odpowiedniej obsługi wykrytych cykli.

Załóżmy prosty kalkulator z wcześniej. Układ równań „ A = B ; B = D + C ; C = D + A ; D =12;” zawiera cykliczną zależność utworzoną przez A , B i C , ponieważ B musi być obliczone przed A , C musi zostać obliczone przed B i A musi zostać obliczone przed C .

Wyprowadzenie zlecenia oceny

Prawidłowa ${\ Displaystyle n (a) <n (b) \ Strzałka w prawo (a, b) \ notin R}$ oceny to numeracja obiektów, które tworzą węzły wykresu zależności, tak aby zachodziło następujące równanie: $: S \ rightarrow \ mathbb {N}$ z za $\ Displaystyle a, b \ w S}$ . Oznacza to, że jeśli numeracja porządkuje dwa elementy $displaystyle$ b $b}$ tak, że $displaystyle$ ocenione przed $b}$ , to nie może za $\ displaystyle a}$ zależy od ${\ displaystyle b}$ .

Poprawnej kolejności oceny może być więcej niż jedna. W rzeczywistości poprawna numeracja jest porządkiem topologicznym , a każdy porządek topologiczny jest poprawną numeracją. Zatem każdy algorytm, który wyprowadza poprawną kolejność topologiczną, wyprowadza poprawną kolejność oceny.

Załóżmy jeszcze raz prosty kalkulator z góry. Biorąc pod uwagę układ równań „ A = B + C ; B = 5+ D ; C = 4; D = 2;”, poprawna kolejność oceny byłaby następująca ( D , C , B , A ). Jednak ( C , D , B , A ) jest również poprawną kolejnością oceny.

Struktura monoidu

Wykres zależności acyklicznej odpowiada śladowi monoidu śladowego w następujący sposób:

Funkcja ${\ Displaystyle \ phi: S \ do \ Sigma}$ oznacza każdy wierzchołek symbolem z alfabetu ${\ Displaystyle \ Sigma}$
Za ${\ Displaystyle a \ do b}$ lub ${\ Displaystyle b \ do a}$ wtedy i tylko wtedy, gdy $\ Displaystyle (\ phi (a ), \ phi (b)}}$ jest w relacji zależności ${\ displaystyle D}$ .
Dwa grafy uważa się za równe, jeśli ich etykiety i krawędzie są zgodne.

Wtedy ciąg składający się z etykiet wierzchołków uporządkowanych według poprawnej kolejności oceny odpowiada ciągowi śladu.

Operacja monooidalna $= (S_ {1}, R_ {1} })\bullet (S_ {2}, R_ {2})}$ ) {\ Displaystyle (S_ {12}, R_ {12} przyjmuje rozłączny związek dwóch wykresów ${\ Displaystyle S_ {12} = S_ {1} \ sqcup S_ {2}}$ ' ustawia wierzchołki, zachowuje istniejące krawędzie w każdym grafie i rysuje nowe krawędzie od pierwszej do drugiej, o ile pozwala na to relacja zależności,

{\ Displaystyle R_ {12} = R_ { 1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b)) \w D\}}

Tożsamość jest pustym grafem.

Przykłady

Wykresy zależności są używane w:

Zautomatyzowane instalatory oprogramowania : przeglądają wykres w poszukiwaniu pakietów oprogramowania , które są wymagane, ale jeszcze nie zostały zainstalowane. Zależność wynika ze sprzężenia pakietów.
Skrypty do tworzenia oprogramowania, takie jak Unix Make , Node npm install, php Composer, Twitter bower install lub Apache Ant . Muszą wiedzieć, jakie pliki zostały zmienione, więc tylko poprawne pliki muszą być ponownie skompilowane.
W technologii kompilatora i implementacji języka formalnego :
- Szeregowanie instrukcji : Wykresy zależności są obliczane dla operandów instrukcji asemblera lub instrukcji pośrednich i wykorzystywane do określenia optymalnej kolejności instrukcji.
- Eliminacja martwego kodu : Jeśli żadna operacja z efektem ubocznym nie zależy od zmiennej, ta zmienna jest uważana za martwą i można ją usunąć.
Dynamiczna analiza wykresów: GraphBolt i KickStarter wychwytują zależności wartości dla obliczeń przyrostowych , gdy zmienia się struktura wykresu.
arkuszy kalkulacyjnych. Muszą wyprowadzić poprawną kolejność obliczeń, podobną do tej w przykładzie użytym w tym artykule.
Standardy Web Forms, takie jak XForms, aby wiedzieć, które elementy wizualne należy zaktualizować, jeśli dane w modelu ulegną zmianie.
Gry wideo, zwłaszcza gry logiczne i przygodowe , które często są projektowane jako wykresy zależnych relacji między działaniami w grze.

Wykresy zależności są jednym z aspektów:

Typy zakładów produkcyjnych : Surowce są przetwarzane na produkty w kilku zależnych od siebie etapach.
Harmonogram pracy : zbiór powiązanych problemów teoretycznych w informatyce.

Zobacz też

Balmas, Francoise (2001) Wyświetlanie wykresów zależności: podejście hierarchiczne , [1] wcre, s. 261, ósma konferencja robocza na temat inżynierii wstecznej (WCRE'01)