Riippuvuuskaavio

Riippuvuusgraafi on suunnattu graafi , joka näyttää tietyn kokoelman elementtijoukon suhteen valitun transitiivisen suhteen mukaisesti .

Tätä kuvaajaa käytetään usein tietojenkäsittelytieteessä ja digitaalielektroniikassa , erityisesti riippuvuusgraafista määritetään laskelmien järjestys tai sen puutteet, jotka ovat yhdenmukaisia graafissa annettujen riippuvuuksien kanssa.

Määritelmä

Olkoon joukko objekteja ja transitiivinen relaatio, jossa mallinnettaessa riippuvuutta "laskeakseen sinun on ensin laskettava ", niin riippuvuusgraafi on graafi, jossa ja on transitiivinen sulkeminen . $S$ $R = S\ kertaa S$ $(a,b)\in R$ $a$ $b$ $G=(S,T)$ $T\subseteq R$ $R$ $T$

Esimerkiksi jokin laskin tukee vakion kirjoittamista johonkin muuttujaan ja kahden muuttujan lisäämistä ja tuloksen kirjoittamista johonkin kolmanteen muuttujaan. Annetaan useita lausekkeita, esimerkiksi . Sitten ja . On mahdollista johtaa eksplisiittisesti kaikki suhteet: riippuu ja , koska kaksi muuttujaa voidaan lisätä jos ja vain, jos molempien muuttujien arvot tunnetaan. Näin ollen ja on laskettava ennen . Arvo tiedetään kuitenkin välittömästi, koska se on numeerinen vakio. $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$

Mahdottomien laskutoimitusten havaitseminen

Riippuvuusgraafin sykliset riippuvuudet johtavat tilanteeseen, jossa ei ole käytettävissä arviointijärjestystä, koska mitään syklin objekteista ei voida ottaa huomioon ensimmäisenä. Jos syklisiä riippuvuuksia ei ole, meillä on suunnattu asyklinen graafi , ja arvioinnin järjestys voidaan määrittää topologisella lajittelulla . Useimmat topologiset lajittelualgoritmit pystyvät havaitsemaan syklejä syötteestä, mutta on toivottavaa havaita jaksot erillään topologisesta lajittelusta.

Laskinpohjaisessa esimerkissä laskentajärjestelmä sisältää ympyräriippuvuuden. täytyy arvioida , täytyy arvioida , täytyy arvioida . $A=B;B=D+C;C=D+A;D=12$ $B$ $A$ $C$ $B$ $A$ $C$

Arviointijärjestyksen määrittäminen

Oikea laskujärjestys on objektien numerointi, joka järjestää riippuvuusgraafin solmut siten, että yhtälö tapahtuu: , missä . Tämä tarkoittaa, että jos määritetään luettelo, joka on arvioitu ennen , se ei voi riippua . Lisäksi oikeaa arviointijärjestystä voi olla useampi kuin yksi. Pohjimmiltaan oikea numerointi on topologinen lajittelu ja mikä tahansa topologinen lajittelu on oikea numerointi. Itse asiassa mikä tahansa algoritmi, joka tuottaa oikean topologisen lajittelun, määrittää samalla myös oikean arviointijärjestyksen. $n:S\rightarrow N$ $n(a)<n(b)\Nuoli oikealle(a,b)\notin R$ $a,b\in S$ $a$ $b$ $a$ $b$

Järjestelmälle (laskimen esimerkissä) oikea järjestys on: , on kuitenkin myös oikea laskentajärjestys. $A=B+C;B=5+D;C=4;D=2$ $(D, C, B, A)$ $(C,D,B,A)$

Esimerkkejä

Riippuvuuskaaviota käytetään:

Automaattinen ohjelmiston asennus. [1] Se liikkuu kaaviota pitkin etsiessään ohjelmistopaketteja , joita tarvitaan, mutta joita ei ole vielä asennettu. Riippuvuudet määritellään pakettisuhteen mukaan .
Kääntäjillä ja virallisilla kielillä :

Suunnitteluohjeet . Riippuvuuskaavio lasketaan kokoajan operandeille tai välikäskyille, ja sitä käytetään ohjeiden optimaalisen järjestyksen määrittämiseen.
Kuolleen koodin poistaminen .

Riippuvuuskaaviot ovat yksi kysymyksistä:

Rajoitusteoriat . Alkutiedot käsitellään tuloksena oleviksi tiedoiksi useiden riippuvien vaiheiden aikana.
Suunnittelu. Joukko toisiinsa liittyviä teoreettisia ongelmia tietojenkäsittelytieteessä.

Katso myös

Muistiinpanot

↑ Esimerkiksi make - apuohjelmissa

Kirjallisuus

Balmas, Francoise (2001) Riippuvuuskaavioiden näyttäminen: hierarkkinen lähestymistapa , [1] wcre, s. 261, kahdeksas käänteistekniikan työkonferenssi (WCRE'01)

Linkit

kokoajan tutkimusprojekti. Dependency Graph Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa