Datei:BDD Variable Ordering VisuBDD Bad.png
BDD_Variable_Ordering_VisuBDD_Bad.png (518 × 32 Pixel, Dateigröße: 288 Bytes, MIME-Typ: image/png)
Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.
Beschreibung
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
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 |
- 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.
In dieser Datei abgebildete Objekte
Motiv
Einige Werte ohne einen Wikidata-Eintrag
1. September 2005
image/png
b2f6e8dcf178cd2eefb0419fced0d6f1d9cc350c
288 Byte
32 Pixel
518 Pixel
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
---|---|---|---|---|---|
aktuell | 11:50, 1. Sep. 2005 | 518 × 32 (288 Bytes) | Dirk Beyer | {{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 |
Dateiverwendung
Die folgende Seite verwendet diese Datei:
Globale Dateiverwendung
Die nachfolgenden anderen Wikis verwenden diese Datei:
- Verwendung auf en.wiki.x.io