File:BDD Variable Ordering VisuBDD Bad.png
Aus Wikimedia Commons, dem freien Medienarchiv
Zur Navigation springen
Zur Suche springen
BDD_Variable_Ordering_VisuBDD_Bad.png (518 × 32 Pixel, Dateigröße: 288 Bytes, MIME-Typ: image/png)
Dateiinformationen
Strukturierte Daten
Bildtexte
Beschreibung[Bearbeiten]
BeschreibungBDD Variable Ordering VisuBDD Bad.png | Visualization of the BDD for the Boolean formula x1 * x2 + x3 * x4 + ... + x19 * x20 using a bad variable ordering (x1,x3,x5,x7,x9,x11,x13,x15,x17,x19,x2,x4,x6,x8,x10,x12,x14,x16,x18,x20). One pixel in the picture corresponds to one BDD node, all nodes of one variable are represented by one line (level), and the number of nodes for that variable by the width of the line. The variables with the most nodes are x19 and x2 with 512 nodes each, i.e., the width of the picture is 512 pixels (x1:1, x3:2, x5:4, x7:8, x9:16, x11:32, x13:64, x15:128, x17:256, x19:512, x2:512, x4:256, x6:128, x8:64, x10:32, x12:16, x14:8, x16:4, x18:2, x20:1). |
Datum | |
Quelle | self-made using CrocoPat, a tool for relational programming, and VisuBDD, a small Java program |
Urheber | Dirk Beyer |
Genehmigung (Weiternutzung dieser Datei) |
GFDL and cc-by-sa-2.5 |
The PNG picture is 518 x 32 pixel.
Other BDD pictures for similar formulas:
-
BDD graph for the Boolean formula x1 * x2 + x3 * x4 + x5 * x6 + x7 * x8 using a good variable ordering
-
BDD graph for the Boolean formula x1 * x2 + x3 * x4 + x5 * x6 + x7 * x8 using a bad variable ordering
The following is the RML (Relational Manipulation Language) code that I fed to CrocoPat to produce the dat files for VisuBDD:
// RML program to generate BDD visualizations for the formula // x1 & x2 | x3 & x4 | ... | x19 & x20, // using two different variable orderings. // "crocopat -e BDD_Variable_Ordering_VisuBDD.rml" // generates two files in dat format. // "java -classpath <your_CrocoPat_dir> // VisuBDD.VisualizeSize BDD_Variable_Ordering_VisuBDD_Bad.dat" // displays a visualization of the BDD graph on screen. // There are two ('Boolean') values for the variables x1, ..., x20. DOM("0"); DOM("1"); // F is the name of the Boolean formula. F(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20) := (x1="1" & x2="1") | (x3="1" & x4="1") | (x5="1" & x6="1") | (x7="1" & x8="1") | (x9="1" & x10="1") | (x11="1" & x12="1") | (x13="1" & x14="1") | (x15="1" & x16="1") | (x17="1" & x18="1") | (x19="1" & x20="1"); // Prints the number of nodes per variable in dat format for VisuBDD, // using a good variable ordering resulting in linear size of the graph. PRINT NODESPERVAR( F(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20) ) TO "BDD_Variable_Ordering_VisuBDD_Good.dat"; // Prints the number of nodes per variable in dat format for VisuBDD, // using a bad variable ordering resulting in exponential size of the graph. // The first term of the conjunction sets the variable ordering. PRINT NODESPERVAR( TRUE(x1,x3,x5,x7,x9,x11,x13,x15,x17,x19,x2,x4,x6,x8,x10,x12,x14,x16,x18,x20) & F(x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16,x17,x18,x19,x20) ) TO "BDD_Variable_Ordering_VisuBDD_Bad.dat";;
Lizenz[Bearbeiten]
Ich, der Urheberrechtsinhaber dieses Werkes, veröffentliche es hiermit unter der folgenden Lizenz:
Es ist erlaubt, die Datei unter den Bedingungen der GNU-Lizenz für freie Dokumentation, Version 1.2 oder einer späteren Version, veröffentlicht von der Free Software Foundation, zu kopieren, zu verbreiten und/oder zu modifizieren; es gibt keine unveränderlichen Abschnitte, keinen vorderen und keinen hinteren Umschlagtext.
Der vollständige Text der Lizenz ist im Kapitel GNU-Lizenz für freie Dokumentation verfügbar.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue |
Diese Datei ist unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 3.0 nicht portiert“ lizenziert. | ||
| ||
Diese Lizenzmarkierung wurde auf Grund der GFDL-Lizenzaktualisierung hinzugefügt.http://creativecommons.org/licenses/by-sa/3.0/CC BY-SA 3.0Creative Commons Attribution-Share Alike 3.0truetrue |
Diese Datei ist unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 2.5 generisch“ (US-amerikanisch) lizenziert.
- Dieses Werk darf von dir
- verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
- neu zusammengestellt werden – abgewandelt und bearbeitet werden
- Zu den folgenden Bedingungen:
- Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
- Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.
Du darfst es unter einer der obigen Lizenzen deiner Wahl verwenden.
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
---|---|---|---|---|---|
aktuell | 09:50, 1. Sep. 2005 | 518 × 32 (288 Bytes) | Dirk Beyer (Diskussion | Beiträge) | {{Information| |Description = Visualization of the BDD for the Boolean formula x1 * x2 + x3 * x4 + ... + x19 * x20 using a bad variable ordering |Source = self-made |Date = 2005-09-01 |Author = Dirk Beyer |Permission = GFDL and cc-by-s |
Du kannst diese Datei nicht überschreiben.
Dateiverwendung
Die folgenden 9 Seiten verwenden diese Datei:
Globale Dateiverwendung
Die nachfolgenden anderen Wikis verwenden diese Datei:
- Verwendung auf de.wikipedia.org
- Verwendung auf en.wikipedia.org