Abhängigkeitsgraphen

In Mathematik, Informatik und der digitalen Elektronik, ist ein Abhängigkeitsgraphen ein gerichteter Graph, der Abhängigkeiten von mehreren Objekten zueinander. Es ist möglich, eine Auswertung Ordnung oder die Abwesenheit eines Auswertungsreihenfolge, die den angegebenen Abhängigkeiten aus dem Abhängigkeitsgraphen respektiert abzuleiten.

Definition

Bei einer Menge von Objekten S und eine transitive Relation mit der Modellierung einer Abhängigkeit "eine Bedarfs b zuerst ausgewertet", ist die Abhängigkeitsdiagramm ein Diagramm, mit und R die transitive Hülle von T.

Beispielsweise gehen von einem einfachen Rechner. Dieser Rechner unterstützt die Zuordnung von Konstanten, Variablen und Zuweisen der Summe von genau 2 Variablen in eine dritte Variable. Angesichts mehrerer Gleichungen wie "A = B + C, B = 5 + D, C = 4; D = 2;" ist, dann und. Sie können dieses Verhältnis direkt ableiten: A hängt davon ab, B und C, weil Sie zwei Variablen hinzufügen, genau dann, wenn Sie die Werte der beiden Variablen kennen. Somit B und C berechnet werden, bevor A berechnet werden kann. Jedoch D's Wert unmittelbar bekannt, da es sich um eine Zahl Literal.

Erkennen unmöglich Auswertungen

In einem Abhängigkeitsgraph, die Zyklen von Abhängigkeiten führen zu einer Situation, in der keine gültige Bewertungsreihenfolge vorhanden ist, da keines der Objekte in dem Zyklus kann zuerst ausgewertet werden. Wenn eine Abhängigkeitsgraphen hat keine zirkuläre Abhängigkeiten nicht, einen gerichteten azyklischen Graphen bildet, und eine Auswertungsreihenfolge kann durch topologische Sortierung finden. Esten topologischen Sortieralgorithmen sind auch fähig Erfassungszyklen in ihren Eingängen, kann es jedoch wünschenswert, Zykluserfassung getrennt von topologische Sortierung um geeignete Handhabung für den erfassten Zyklen bereitzustellen auszuführen.

Gehen wir von der einfachen Taschenrechner aus der Zeit vor. Das Gleichungssystem "A = B; B = D + C, C = D + A; D = 12;" enthält eine zirkuläre Abhängigkeit von A, B und C gebildet, wie B muss vor der A bewertet werden, C muss vor dem B ausgewertet und A muss vor der C bewertet werden

Ableiten eines Auswertungsreihen

Eine korrekte Auswertung Ordnung eine Nummerierung der Objekte, die die Knoten des Abhängigkeitsgraphen zu bilden, so dass die folgende Gleichung gilt: mit. Das bedeutet, wenn die Nummerierung Bestellungen beiden Elemente a und b, so dass ein noch vor b ausgewertet werden, dann wird ein nicht auf b abhängen. Darüber hinaus kann es mehr als eine einzige korrekte Auswertung Ordnung sein. In der Tat ist eine korrekte Nummerierung ein topologischer Ordnung und jede topologische Ordnung ist eine korrekte Nummerierung. Somit kann jeder Algorithmus, der eine korrekte topologische Ordnung leitet leitet eine korrekte Auswertung bestellen.

Gehen wir von der einfachen Rechner von oben noch einmal. Angesichts der Gleichungssystem "A = B + C, B = 5 + D, C = 4; D = 2;", eine korrekte Bewertung Um sein würde. Allerdings ist eine korrekte Auswertung um als gut.

Beispiele

Abhängigkeitsgraphen werden eingesetzt in:

  • Automatisierte Software-Installer. Sie gehen die Grafik auf der Suche nach Software-Pakete, die erforderlich sind, aber noch nicht installiert. Die Abhängigkeit wird durch die Kopplung der Verpackungen verwendet wird.
  • Software Build-Skripte wie Unix Stellen, Knoten NPM installieren, Twitter Laube installieren oder Apache Ant. Sie müssen wissen, welche Dateien so nur verändert die richtigen Dateien neu kompiliert werden müssen.
  • In Compilertechnologie und Formensprache Umsetzung:
    • Instruction Scheduling. Abhängigkeitsgraphen für die Operanden der Montage oder Zwischenbefehle berechnet und verwendet, um eine optimale Reihenfolge für die Anweisungen bestimmen.
    • Beseitigung von totem Code. Wenn kein Seiten bewirkten Betätigung abhängig von einer variablen wird diese Variable als tot angesehen und kann entfernt werden.
  • Spreadsheet-Rechner. Sie müssen eine korrekte Berechnung, um ähnlich, dass man in der in diesem Artikel verwendeten Beispiel abzuleiten.
  • Web Forms-Standards wie XForms zu wissen, was visuelle Elemente auf, wenn Daten in den Modelländerungen zu aktualisieren.

Abhängigkeitsgraphen gibt ein Aspekt:

  • Manufacturing Plant Typen. Rohstoffe werden über mehrere Stufen abhängig zu Produkten verarbeitet.
  • Job Shop Scheduling. Eine Sammlung von verwandten theoretische Probleme in der Informatik.
  0   0

In Verbindung Stehende Artikel

Kommentare - 0

Keine Kommentare

Fügen Sie einen Kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Zeichen übrig: 3000
captcha