Кіріспе
Тәуелділікті көрсететін бағытталған график Математика, компьютерлік ғылым және цифрлық электроникада тәуелділік графигі - бірнеше нысандардың бір-біріне тәуелділігін көрсететін бағытталған график. Берілген тәуелділіктерді құрметтейтін бағалау тәртібін немесе бағалау тәртібінің жоқтығын тәуелділік графигінен алуға болады.
In mathematics, computer science and digital electronics, a dependency graph is a directed graph representing dependencies of several objects towards each other. It is possible to derive an evaluation order or the absence of an evaluation order that respects the given dependencies from the dependency graph.
Анықтама
Объектілер жиынтығы және "a b-ге байланысты" ("b алдымен бағаланады" дегенді білдіреді) тәуелділікті модельдеумен транзитивті қатынас берілген жағдайда, тәуелділік графигі R-дің транзитивті азайтылуы бар график болып табылады. Мысалы, қарапайым калькуляторды алыңыз. Бұл калькулятор тұрақты мәндерді айнымалыларға беруді және дәл екі айнымалының қосындысын үшінші айнымалыға беруді қолдайды. "A = B + C; B = 5 + D; C = 4; D = 2;" сияқты бірнеше теңдеулерді ескере отырып, сіз бұл байланысты тікелей шығара аласыз: A B және C-ға байланысты, өйткені сіз екі айнымалыны қоссаңыз болады, егер сіз екі айнымалының мәндерін білсеңіз. Осылайша, А-ны есептеуден бұрын В-ды есептеу керек. Алайда, C және D мәндері бірден белгілі, өйткені олар сандық литеральдар.
For example, assume a simple calculator. This calculator supports assignment of constant values to variables and assigning the sum of exactly two variables to a third variable. Given several equations like "A = B+C; B = 5+D; C=4; D=2;", then and You can derive this relation directly: A depends on B and C, because you can add two variables if and only if you know the values of both variables. Thus, B must be calculated before A can be calculated. However, the values of C and D are known immediately, because they are number literals.
Мүмкін емес бағалауларды тану
Тәуелдік графында тәуелділік циклдері (айналмалы тәуелділіктер деп те аталады) жарамды бағалау тәртібі жоқ жағдайға әкеледі, өйткені циклдегі объектілердің ешқайсысы бірінші бағаланбауы мүмкін. Егер тәуелділік графигінде шеңберлік тәуелділіктер болмаса, ол бағытталған ациклді графикті құрайды және бағалау тәртібі топологиялық сұрыптау арқылы табылуы мүмкін. Топологиялық сұрыптау алгоритмдерінің көпшілігі өздерінің кірісіндегі циклдерді анықтауға қабілетті; алайда, анықталған циклдерді дұрыс басқаруды қамтамасыз ету үшін циклдерді анықтауды топологиялық сұрыптаудан бөлек орындау қажет болуы мүмкін. Бұрынғы қарапайым калькуляторды қараңыз. "A=B; B=D+C; C=D+A; D=12;" теңдеу жүйесі A, B және C құрайтын дөңгелек тәуелділікті қамтиды, өйткені B-ді A-дан бұрын, C-ді B-ден бұрын және A-ды C-ден бұрын бағалау керек.
Бағалау тапсырысын шығару
Дұрыс бағалау тәртібі - бұл байланыстылық графигінің түйіндерін құрайтын нысандарды нөмірлеу, сондықтан келесі теңдеу орындалады: Бұл дегеніміз, егер нөмірлеу екі элементті реттеп, оларды бұрын бағалайтын болса, онда олар бірден көп дұрыс бағалау тәртібіне тәуелді болмауы керек. Шын мәнінде, дұрыс нөмірлеу - топологиялық тәртіп, ал кез келген топологиялық тәртіп - дұрыс нөмірлеу. Осылайша, дұрыс топологиялық ретті шығаратын кез келген алгоритм дұрыс бағалау реттілігін шығарады. Жоғарыдағы қарапайым калькуляторды тағы да қайталаңыз. "A = B + C; B = 5 + D; C = 4; D = 2;" теңдеу жүйесін ескере отырып, дұрыс бағалау тәртібі (D, C, B, A) болады. Алайда (С, D, В, А) дұрыс бағалау тәртібі болып табылады.
There can be more than one correct evaluation order. In fact, a correct numbering is a topological order, and any topological order is a correct numbering. Thus, any algorithm that derives a correct topological order derives a correct evaluation order. Assume the simple calculator from above once more. Given the equation system "A = B+C; B = 5+D; C=4; D=2;", a correct evaluation order would be (D, C, B, A). However, (C, D, B, A) is a correct evaluation order as well.