Binary decision diagram (original) (raw)
En les ciències de la computació, un diagrama de decisió binari (DDB) és una estructura de dades utilitzada per representar una funció booleana. Els DDBs poden ser considerats com una representació de conjunts o relacions. A diferència d'altres representacions comprimides, les operacions es realitzen directament en els DDB, sense necessitat de descomprimir-los.
| Property | Value |
|---|---|
| dbo:abstract | En les ciències de la computació, un diagrama de decisió binari (DDB) és una estructura de dades utilitzada per representar una funció booleana. Els DDBs poden ser considerats com una representació de conjunts o relacions. A diferència d'altres representacions comprimides, les operacions es realitzen directament en els DDB, sense necessitat de descomprimir-los. (ca) Ein binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und -verifikation eingesetzt. Ein BED kann als eine Art Flussdiagramm zur Auswertung einer Booleschen Funktion verstanden werden. Dabei wird nacheinander der Wert der Variablen , , ... abgefragt, mit den zwei Entscheidungsmöglichkeiten Wahr oder Falsch, welche jeweils in unterschiedliche Teilbereiche des Diagramms verzweigen. Als Ergebnis erhält man schließlich den Wert der Booleschen Funktion unter der gewählten Variablenbelegung. Die Darstellung des Diagramms ist dabei weitestgehend komprimiert, so dass für das Ergebnis irrelevante Fragen ausgelassen und doppelte Teildiagramme zusammengelegt werden. (de) In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression. Similar data structures include negation normal form (NNF), Zhegalkin polynomials, and propositional directed acyclic graphs (PDAG). (en) En ciencias de la computación, un diagrama de decisión binario (DDB), tal como una forma normal de negación (FNN) o un (GADP), es una estructura de datos utilizada para representar una función booleana. A un nivel más abstracto, los DDBs pueden ser considerados como una representación comprimida de conjuntos o relaciones. A diferencia de otras representaciones comprimidas, las operaciones se realizan directamente en los DDB, sin necesidad de descomprimirlos. (es) En informatique, un graphe de décision binaire ou diagramme de décision binaire (ou BDD pour Binary Decision Diagram en anglais) est une structure de données utilisée pour représenter des fonctions booléennes, ou des questionnaires binaires. On utilise les BDD pour représenter des ensembles ou des relations de manière compacte / compressée. Les diagrammes de décision binaires sont utilisés par les programmes de conception assistée par ordinateur (CAO / CAD) pour générer des circuits (synthèse logique), et dans la vérification formelle. C'est une structure de donnée considérée comme compacte, en comparaison par exemple aux arbres de décision. Les diagrammes de décision binaire sont utilisés dans le model checking symbolique de CTL. (fr) In de informatica is een binair beslissingsdiagram (Engels: binary decision diagram, BDD) een datastructuur waarmee een booleaanse functie gerepresenteerd kan worden. (nl) 二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。 (ja) 在计算机科学中，二元决策图（英語：binary decision diagram, BDD），或译为二元判定图，是被用来表达一个布尔函数的一种数据结构。 (zh) Бінарна діаграма рішень (англ. Binary decision diagram) або програма розгалуження — це структура даних в інформатиці, яка використовується для представлення булевої функції. На більш абстрактному рівні, БДР можна розглядати як стиснене представлення множин або відношень. На відміну від інших стиснених представлень, операції виконуються безпосередньо на стислому представлені, тобто без декомпресії. Інші структури даних, які використовуються для представлення булевої функції включають в себе заперечення нормальної форми, . (uk) Бинарная диаграмма решений (БДР) или программа с ветвлением является формой представления булевой функции от переменных в виде направленного ациклического графа, состоящего из внутренних узлов решений (помеченных ), каждый из которых имеет по два потомка, и двух терминальных узлов (помеченных 0 и 1), каждый из которых соответствует одному из двух значений булевой функции. В зарубежной литературе бинарные диаграммы решений и программы с ветвлением называются binary decision diagram (BDD) и branching programs (BP) соответственно. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/BDD.png?width=300 |
| dbo:wikiPageExternalLink | https://www.youtube.com/watch%3Fv=SQE21efsf7Y http://www.hpi.uni-potsdam.de/fileadmin/hpi/FG_ITS/books/OBDD-Book.pdf http://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz https://github.com/johnyf/tool_lists/blob/master/bdd.md |
| dbo:wikiPageID | 576855 (xsd:integer) |
| dbo:wikiPageLength | 22461 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124624694 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Carnegie_Mellon_University dbr:Bayesian_probability dbr:Negation_normal_form dbr:Relation_(mathematics) dbr:Decision_tree dbr:Integer_factorization dbr:L/poly dbr:♯P dbc:Articles_with_example_code dbc:Diagrams dbr:And-inverter_graph dbr:Negation dbr:Rooted_graph dbr:Model_checking dbr:NC_(complexity) dbr:NP-complete dbr:NP-hard dbr:Logical_conjunction dbr:Complexity_class dbr:Computational_problem dbr:Computer_science dbr:Hardware_acceleration dbr:Private_information_retrieval dbr:Propositional_directed_acyclic_graph dbr:P/poly dbr:Truth_table dbr:Data_compression dbr:Data_structure dbr:Logic_synthesis dbr:FPGA dbr:Formal_verification dbr:Graph_isomorphism dbr:Graph_theory dbr:Logical_disjunction dbr:Radix_tree dbc:Boolean_algebra dbr:Tautology_(logic) dbc:Graph_data_structures dbc:Model_checking dbr:Child_node dbr:Karnaugh_map dbr:Binary_moment_diagram dbr:Donald_Knuth dbr:Boolean_function dbr:Boolean_satisfiability_problem dbr:Randal_Bryant dbr:Set_(mathematics) dbr:Multiplexer dbr:The_Art_of_Computer_Programming dbr:Zhegalkin_polynomial dbr:Zero-suppressed_decision_diagram dbr:Ripple_carry_adder dbr:Fault_tree dbr:Switching_function dbr:Polynomial-time dbr:Computer_Aided_Design dbr:Shannon_expansion dbr:Adnan_Darwiche_(computer_scientist) dbr:Binary_decision_tree dbr:Decomposable_negation_normal_form dbr:File:BDD.png dbr:File:BDD_Variable_Ordering_Bad.svg dbr:File:BDD_Variable_Ordering_Good.svg dbr:File:BDD_diagram_with_complemented_edges.png dbr:File:BDD_simple.svg dbr:Free_binary_decision_diagram dbr:Parity_decision_diagram |
| dbp:cs1Dates | y (en) |
| dbp:date | May 2019 (en) |
| dbp:wikiPageUsesTemplate | dbt:Authority_control dbt:Citation_needed dbt:Cite_book dbt:Cite_journal dbt:Commons_category dbt:Redirect dbt:Reflist dbt:Rp dbt:Short_description dbt:Use_dmy_dates dbt:Data_structures |
| dct:subject | dbc:Articles_with_example_code dbc:Diagrams dbc:Boolean_algebra dbc:Graph_data_structures dbc:Model_checking |
| gold:hypernym | dbr:Structure |
| rdf:type | owl:Thing yago:Ability105616246 yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 yago:WikicatGraphDataStructures dbo:Building yago:Structure105726345 yago:WikicatDataStructures yago:WikicatFormalMethods |
| rdfs:comment | En les ciències de la computació, un diagrama de decisió binari (DDB) és una estructura de dades utilitzada per representar una funció booleana. Els DDBs poden ser considerats com una representació de conjunts o relacions. A diferència d'altres representacions comprimides, les operacions es realitzen directament en els DDB, sense necessitat de descomprimir-los. (ca) In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression. Similar data structures include negation normal form (NNF), Zhegalkin polynomials, and propositional directed acyclic graphs (PDAG). (en) En ciencias de la computación, un diagrama de decisión binario (DDB), tal como una forma normal de negación (FNN) o un (GADP), es una estructura de datos utilizada para representar una función booleana. A un nivel más abstracto, los DDBs pueden ser considerados como una representación comprimida de conjuntos o relaciones. A diferencia de otras representaciones comprimidas, las operaciones se realizan directamente en los DDB, sin necesidad de descomprimirlos. (es) In de informatica is een binair beslissingsdiagram (Engels: binary decision diagram, BDD) een datastructuur waarmee een booleaanse functie gerepresenteerd kan worden. (nl) 二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。 (ja) 在计算机科学中，二元决策图（英語：binary decision diagram, BDD），或译为二元判定图，是被用来表达一个布尔函数的一种数据结构。 (zh) Бінарна діаграма рішень (англ. Binary decision diagram) або програма розгалуження — це структура даних в інформатиці, яка використовується для представлення булевої функції. На більш абстрактному рівні, БДР можна розглядати як стиснене представлення множин або відношень. На відміну від інших стиснених представлень, операції виконуються безпосередньо на стислому представлені, тобто без декомпресії. Інші структури даних, які використовуються для представлення булевої функції включають в себе заперечення нормальної форми, . (uk) Бинарная диаграмма решений (БДР) или программа с ветвлением является формой представления булевой функции от переменных в виде направленного ациклического графа, состоящего из внутренних узлов решений (помеченных ), каждый из которых имеет по два потомка, и двух терминальных узлов (помеченных 0 и 1), каждый из которых соответствует одному из двух значений булевой функции. В зарубежной литературе бинарные диаграммы решений и программы с ветвлением называются binary decision diagram (BDD) и branching programs (BP) соответственно. (ru) Ein binäres Entscheidungsdiagramm (BED; engl. binary decision diagram, BDD) ist eine Datenstruktur zur Repräsentation Boolescher Funktionen. Binäre Entscheidungsdiagramme werden vor allem im Bereich der Hardwaresynthese und -verifikation eingesetzt. (de) En informatique, un graphe de décision binaire ou diagramme de décision binaire (ou BDD pour Binary Decision Diagram en anglais) est une structure de données utilisée pour représenter des fonctions booléennes, ou des questionnaires binaires. On utilise les BDD pour représenter des ensembles ou des relations de manière compacte / compressée. (fr) |
| rdfs:label | Diagrama de decisió binari (ca) Binäres Entscheidungsdiagramm (de) Binary decision diagram (en) Diagrama de decisión binario (es) Diagramme de décision binaire (fr) 二分決定図 (ja) Binair beslissingsdiagram (nl) Бинарная диаграмма решений (ru) Бінарна діаграма рішень (uk) 二元决策图 (zh) |
| owl:sameAs | freebase:Binary decision diagram yago-res:Binary decision diagram dbpedia-commons:Binary decision diagram http://d-nb.info/gnd/4530728-3 wikidata:Binary decision diagram dbpedia-ca:Binary decision diagram dbpedia-da:Binary decision diagram dbpedia-de:Binary decision diagram dbpedia-es:Binary decision diagram dbpedia-fr:Binary decision diagram http://hi.dbpedia.org/resource/बाइनरी_निर्णय_आरेख dbpedia-ja:Binary decision diagram dbpedia-nl:Binary decision diagram dbpedia-ru:Binary decision diagram dbpedia-sr:Binary decision diagram dbpedia-uk:Binary decision diagram dbpedia-zh:Binary decision diagram https://global.dbpedia.org/id/51yMD |
| prov:wasDerivedFrom | wikipedia-en:Binary_decision_diagram?oldid=1124624694&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/BDD.png wiki-commons:Special:FilePath/BDD_Variable_Ordering_Bad.svg wiki-commons:Special:FilePath/BDD_Variable_Ordering_Good.svg wiki-commons:Special:FilePath/BDD_diagram_with_complemented_edges.png wiki-commons:Special:FilePath/BDD_simple.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Binary_decision_diagram |
| is dbo:wikiPageDisambiguates of | dbr:BDD |
| is dbo:wikiPageRedirects of | dbr:Binary_Decision_Diagram dbr:Binary_decision_diagrams dbr:Ordered_binary_decision_diagram dbr:ROBDD dbr:Reduced_ordered_binary_decision_diagram dbr:OBDD dbr:Binary_Decision_Diagrams dbr:Branching_program dbr:Branching_programs |
| is dbo:wikiPageWikiLink of | dbr:BDD dbr:Enumeration_algorithm dbr:List_of_data_structures dbr:Bernoulli_distribution dbr:DPLL_algorithm dbr:Decision_tree_learning dbr:Ingo_Wegener dbr:Libdmc dbr:List_of_graphical_methods dbr:And-inverter_graph dbr:Reachability_problem dbr:Model_checking dbr:Logic_optimization dbr:Communicating_sequential_processes dbr:Computer_engineering_compendium dbr:Kevin_Karplus dbr:Propositional_directed_acyclic_graph dbr:Automated_theorem_proving dbr:Truth_table dbr:Logic_synthesis dbr:Datalog dbr:NuSMV dbr:Binary_Decision_Diagram dbr:Binary_decision_diagrams dbr:Digital_electronics dbr:Formal_equivalence_checking dbr:Formal_methods dbr:Knowledge_compilation dbr:List_of_PSPACE-complete_problems dbr:Karnaugh_map dbr:Binary_decision dbr:Binary_moment_diagram dbr:Schwartz–Zippel_lemma dbr:Directed_acyclic_graph dbr:Boole's_expansion_theorem dbr:Boolean_algebra dbr:Boolean_function dbr:Randal_Bryant dbr:Reed–Muller_expansion dbr:SAT_solver dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:The_Art_of_Computer_Programming dbr:Zero-suppressed_decision_diagram dbr:Ordered_binary_decision_diagram dbr:ROBDD dbr:Reduced_ordered_binary_decision_diagram dbr:OBDD dbr:Binary_Decision_Diagrams dbr:Branching_program dbr:Branching_programs |
| is rdfs:seeAlso of | dbr:Binary_decision |
| is owl:differentFrom of | dbr:Influence_diagram |
| is foaf:primaryTopic of | wikipedia-en:Binary_decision_diagram |
