बाइनरी निर्णय आरेख: Difference between revisions

Latest revision as of 10:51, 4 September 2023

कंप्यूटर विज्ञान में, बाइनरी निर्णय आरेख(बीडीडी) या ब्रांचिंग प्रोग्राम एक डेटा संरचना है जिसका उपयोग बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है। अधिक सार स्तर पर, बीडीडी को समुच्चय या संबंधों के एक सघन प्रतिनिधित्व के रूप में माना जा सकता है। अन्य संपीड़ित अभ्यावेदन के विपरीत, संचालन सीधे संपीड़ित प्रतिनिधित्व पर किया जाता है, अर्थात बिना विघटन के।

इसी तरह की डेटा संरचनाओं में ऋणात्मक सामान्य रूप (एनएनएफ), ज़ेगल्किन बहुपद, और प्रस्तावक निर्देशित विश्वकोश रेखांकन (पीडीएजी) शामिल हैं।

परिभाषा

एक बूलियन फ़ंक्शन को एक रूटेड, निर्देशित, एसाइक्लिक ग्राफ के रूप में दर्शाया जा सकता है, जिसमें कई (निर्णय) नोड्स और दो टर्मिनल नोड होते हैं। दो टर्मिनल नोड्स को 0 (FALSE) और 1 (TRUE) के रूप में लेबल किया गया है। प्रत्येक (निर्णय) नोड $u$ को एक बूलियन चर $x_{i}$ द्वारा लेबल किया गया है और इसमें दो चाइल्ड नोड्स हैं जिन्हें लो चाइल्ड और हाई चाइल्ड कहा जाता है। नोड $u$ से निम्न (या उच्च) चाइल्ड तक का किनारा चर $x_{i}$ के मान FALSE (या TRUE, क्रमशः) के एक असाइनमेंट को दर्शाता है। ऐसे पीडीएजी को 'आदेशित' कहा जाता है यदि मूल से सभी पथों पर विभिन्न चर एक ही क्रम में प्रकट होते हैं। एक बीडीडी को 'कम' कहा जाता है यदि निम्नलिखित दो नियमों को इसके ग्राफ पर लागू किया गया है:

किसी भी समरूपी उप-अनुच्छेदों को मिलाइए।
ऐसे किसी भी नोड को हटा दें जिसके दो चाइल्ड समरूपी हों।

लोकप्रिय उपयोग में, बीडीडी शब्द लगभग हमेशा एक कम आदेशित द्विआधारी निर्णय आरेख होता है (साहित्य में आरओबीबीडी का उपयोग तब किया जाता है जब आदेश और कमी के पहलुओं पर जोर दिया जाना चाहिए)। आरओबीडीडी (ROBDD) 0 का लाभ यह है कि यह किसी विशेष कार्य और परिवर्तनशील क्रम के लिए विहित (अद्वितीय) है।^[1] यह गुण इसे कार्यात्मक तुल्यता जाँच और कार्यात्मक प्रौद्योगिकी मानचित्रण जैसे अन्य कार्यों में उपयोगी बनाता है।

रूट नोड से 1-टर्मिनल तक का पथ एक (संभवतः आंशिक) वैरिएबल असाइनमेंट का प्रतिनिधित्व करता है जिसके लिए प्रतिनिधित्व एक बूलियन फ़ंक्शन सत्य है। चूंकि पथ एक नोड से निचले (या उच्चतर) चाइल्ड तक जाता है, उस नोड का चर 0 (क्रमशः) नियत किया जाता है।

उदाहरण

नीचे दिया गया आंकड़ा एक द्विआधारी डिसिशन ट्री दिखाता है (कमी नियम लागू नहीं होते हैं), और एक सत्य तालिका, प्रत्येक फ़ंक्शन $f(x1,x2,x3)$ का प्रतिनिधित्व करता है। बाईं ओर के ट्री में, किसी दिए गए चर असाइनमेंट के लिए फ़ंक्शन का मान निर्धारित किया जा सकता हैl एक टर्मिनल के लिए ग्राफ़ के नीचे पथ का अनुसरण करना और नीचे दिए गए आंकड़ों में, बिंदीदार रेखाएं कम चाइल्ड के किनारों का प्रतिनिधित्व करती हैं, जबकि ठोस रेखाएं किनारों को उच्च चाइल्ड को दर्शाती हैं। इसलिए, f(0,1,1) को खोजने के लिए, x1 से शुरू करें, बिंदीदार रेखा को x2 तक ले जाएं (चूंकि x1 में 0 को असाइनमेंट है), और फिर दो ठोस रेखाएं नीचे आती हैं (चूंकि x2 और x3 प्रत्येक में एक को असाइनमेंट होता है)। यह टर्मिनल 1 की ओर जाता है, जो $f(0,1,1)$ का मान है। बायीं आकृति में बाइनरी निर्णय ट्री को दो कमी नियमों के अनुसार अधिकतम को कम करके बाइनरी निर्णय आरेख में बदला जा सकता है। परिणामी बीडीडी को सही आकृति में दिखाया गया है।

फ़ंक्शन के लिए बाइनरी डिसीजन ट्री और ट्रुथ टेबल

f(x_{1},x_{2},x_{3})=(\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})

, बूलियन ऑपरेटरों के लिए संकेतन में वर्णित है।

फ़ंक्शन f के लिए बीडीडी

इस बूलियन फ़ंक्शन को लिखने के लिए एक और संकेतन ${\overline {x}}_{1}{\overline {x}}_{2}{\overline {x}}_{3}+x_{1}x_{2}+x_{2}x_{3}$ है।

पूरक किनारे

Diagram of a binary decision diagram represented using complemented edges। एक द्विआधारी निर्णय आरेख का आरेख पूरक किनारों का उपयोग करके दर्शाया गया है।

पूरक किनारों का उपयोग करके दर्शाए गए द्विआधारी निर्णय आरेख का आरेख।

एक आरओबीडीडी (ROBDD) को पूरक किनारों का उपयोग करके और भी अधिक सघन रूप से दर्शाया जा सकता है।^[2]^[3] पूरक किनारों का निर्माण निम्नलिखित किनारों को पूरक के रूप में व्याख्या करके किया गया है या नहीं। यदि एक किनारे को पूरक किया जाता है, तो यह एक बूलियन फ़ंक्शन की अस्वीकृति को संदर्भित करता है जो एक नोड से मेल खाता है जो एक किनारे की ओर इशारा करता है (बूलियन फ़ंक्शन उस नोड की जड़ के साथ बीडीडी द्वारा दर्शाया गया है)। यह सुनिश्चित करने के लिए कि परिणामी बीडीडी प्रतिनिधित्व एक विहित रूप है, उच्च किनारों को पूरक नहीं किया गया है। इस निरूपण में, बीडीडी में एक एकल पत्ती नोड होता है, नीचे बताए गए कारणों के लिए।

बीडीडी का प्रतिनिधित्व करते समय पूरक किनारों का उपयोग करने के दो लाभ हैं:

बीडीडी के निषेध की गणना करने में निरंतर समय लगता है
स्पेस उपयोग (यानी, आवश्यक मेमोरी) कम हो जाता है

इस प्रतिनिधित्व में, बीडीडी का संदर्भ एक (संभवतः पूरक) "किनारे" है जो बीडीडी की जड़ को इंगित करता है। यह पूरक किनारों के उपयोग के बिना प्रतिनिधित्व में बीडीडी के संदर्भ के विपरीत है, जो बीडीडी के मूल नोड हैं। इस प्रतिनिधित्व में एक संदर्भ बढ़त होने का कारण यह है कि प्रत्येक बूलियन फ़ंक्शन के लिए, फ़ंक्शन और इसके निषेध को एक किनारे से दर्शाया जाता है जो एक बीडीडी की मूल तक जाता है, और एक ही बीडीडी की जड़ के पूरक किनारे का प्रतिनिधित्व करता है। यही कारण है कि नकारने में निरंतर समय लगता है। यह यह भी बताता है कि एक एकल निष्पर्ण पर्याप्त क्यों है: FALSE को एक पूरक किनारे द्वारा दर्शाया जाता है जो एक पत्ती नोड को इंगित करता है, और TRUE को एक साधारण किनारे (अर्थात, पूरक नहीं) द्वारा दर्शाया जाता है जो कि निष्पर्ण को इंगित करता है।

उदाहरण के लिए, मान लीजिए कि एक बूलियन फ़ंक्शन को पूरक किनारों का उपयोग करके दर्शाए गए बीडीडी के साथ दर्शाया गया है। एक चर के लिए दिए गए असाइनमेंट (बूलियन) के लिए एक बूलियन फ़ंक्शन का मान खोजने के लिए, हम संदर्भ किनारे से शुरू करते हैं, जो बीडीडी की जड़ को इंगित करता है और दिए गए चर मानों द्वारा परिभाषित पथ का अनुसरण करता है (बाद में) यदि नोड को लेबल करने वाला चर FALSE के बराबर है और उच्च किनारे का अनुसरण करता है यदि नोड को लेबल करने वाला चर TRUE के बराबर है), जब तक हम निष्पर्ण तक नहीं पहुंच जाते। इस पथ का अनुसरण करते हुए, हम गिनते हैं कि हमने कितने पूरक किनारों को पार किया है। यदि हम निष्पर्ण तक पहुँचते हैं तो हमने विषम संख्या में पूरक किनारों को पार कर लिया है, तो दिए गए चर असाइनमेंट के लिए बूलियन फ़ंक्शन का मान FALSE है, अन्यथा (यदि हमने पूरक किनारों की एक सम संख्या को पार कर लिया है), तो का मान दिए गए चर असाइनमेंट के लिए बूलियन फ़ंक्शन TRUE है।

इस प्रतिनिधित्व में एक बीडीडी का एक उदाहरण आरेख दाईं ओर दिखाया गया है, और उसी बूलियन अभिव्यक्ति का प्रतिनिधित्व करता है जैसा कि ऊपर के चित्र में दिखाया गया है, अर्थात $(\neg x_{1}\wedge \neg x_{2}\wedge \neg x_{3})\vee (x_{1}\wedge x_{2})\vee (x_{2}\wedge x_{3})$ । कम किनारों को धराशायी कर दिया जाता है, उच्च किनारों को ठोस, और पूरक किनारों को "-1" लेबल द्वारा दर्शाया जाता है। नोड जिसका लेबल @ प्रतीक से शुरू होता है, वह बीडीडी के संदर्भ का प्रतिनिधित्व करता है, अर्थात संदर्भ किनारा वह किनारा है जो इस नोड से शुरू होता है।

इतिहास

मूल विचार जिससे डेटा संरचना बनाई गई थी वह शैनन विस्तार है। एक स्विचिंग फ़ंक्शन को एक चर (सीएफ अगर-तब-अन्य सामान्य रूप) निर्दिष्ट करके दो उप-फ़ंक्शन (सहकारकों) में विभाजित किया जाता है। यदि ऐसे उप-कार्य को उप-वृक्ष के रूप में माना जाता है, तो इसे एक द्विआधारी निर्णय ट्री द्वारा दर्शाया जा सकता है। बाइनरी निर्णय आरेख (बीडीडी) को सी. वाई. ली द्वारा पेश किया गया था,^[4] और शेल्डन बी. एकर्स ^[5] और रेमंड टी. आगे के अध्ययन के बारे में बाउट द्वारा जाना जाता था।^[6] इन लेखकों से स्वतंत्र रूप से, यूके में "कैननिकल ब्रैकेट फॉर्म" नाम से एक बीडीडी पेश किया गया था। सीएडी में वी मोशन-इंडिपेंडेंट सर्किट ममरुकोव के विश्लेषण के लिए। ^[7] डेटा संरचना के आधार पर कुशल कलन विधि के लिए पूरी क्षमता की जांच कार्नेगी मेलन विश्वविद्यालय में रैंडल ब्रायंट द्वारा की गई थी: उनके प्रमुख विस्तार एक निश्चित चर क्रम (कैनोनिकल प्रतिनिधित्व के लिए) और साझा उप-ग्राफ (संपीड़न के लिए) का उपयोग करने के लिए थे। इन दो अवधारणाओं को लागू करने से समुच्चय और संबंधों के प्रतिनिधित्व के लिए एक कुशल डेटा संरचना और कलन विधि का परिणाम होता है।^[8]^[9] साझाकरण को कई बीडीडी तक विस्तारित करके, अर्थात कई बीडीडी द्वारा एक उप-ग्राफ का उपयोग किया जाता है, डेटा संरचना साझा कम किए गए आदेशित बाइनरी निर्णय आरेख को परिभाषित किया गया है।^[2] बीडीडी की धारणा अब आमतौर पर उस विशेष डेटा संरचना को संदर्भित करने के लिए उपयोग की जाती है।

अपने वीडियो लेक्चर फन विद बाइनरी निर्णय आरेखों (Fun with Binary Decision Diagrams) में,डोनाल्ड नुथ ने बीडीडी को "पिछले पच्चीस वर्षों में सामने आए एकमात्र वास्तव में मौलिक डेटा संरचनाओं में से एक" कहा और उल्लेख किया कि ब्रायंट का 1986 का पेपर कुछ समय के लिए था। कंप्यूटर विज्ञान में सबसे ज्यादा उद्धृत पत्रों में से एक था।^[10]

अदनान डारविच और उनके सहयोगियों ने दिखाया है कि बीडीडी बूलियन कार्यों के लिए कई सामान्य रूपों में से एक है, प्रत्येक आवश्यकताओं के एक अलग संयोजन द्वारा संचालित है। डारविच द्वारा पहचाना जाने वाला एक अन्य महत्वपूर्ण सामान्य रूप है डीकंपोजेबल नेगेटिव नॉर्मल फॉर्म, या डीएनएफ (DNNF) है।

अनुप्रयोग

सर्किट (तर्क संश्लेषण) को संश्लेषित करने और औपचारिक सत्यापन में बीडीडी का व्यापक रूप से सीएडी सॉफ्टवेयर में उपयोग किया जाता है। बीडीडी में कई कम-ज्ञात अनुप्रयोग हैं, जिनमें फॉल्ट ट्री विश्लेषण, बायेसियन लॉजिक, उत्पाद विन्यास और निजी सूचना पुनर्प्राप्ति शामिल हैं।^[11]^[12]^{[citation needed]}

कोई भी मनमाना बीडीडी (भले ही इसे कम किया गया हो या ऑर्डर न किया गया हो) प्रत्येक नोड को 2 से 1 मल्टीप्लेक्सर से बदलकर सीधे हार्डवेयर में लागू किया जा सकता है; प्रत्येक बहुसंकेतक एक FPGA में 4-LUT द्वारा सीधे लागू किया जा सकता है। लॉजिक गेट्स के एक मनमाने नेटवर्क से बीडीडी [उद्धरण वांछित] (AND-इन्वर्टर ग्राफ़ के विपरीत) में परिवर्तित करना इतना आसान नहीं है।

चर आदेश

बीडीडी का आकार प्रतिनिधित्व किए जा रहे फ़ंक्शन और चर के चुने हुए अनुक्रम द्वारा निर्धारित किया जाता है। बूलियन फ़ंक्शन मौजूद हैं $f(x_{1},\ldots ,x_{n})$ जिसके लिए चर के आदेश के आधार पर हम एक ग्राफ प्राप्त कर रहे हैं, जिसकी संख्या नोड्स की संख्या रैखिक होगी (सबसे अच्छा और सबसे अच्छा और घातीय रूप से सबसे खराब (जैसे, एक तरंग कैरी एडडर)। बूलियन फ़ंक्शन पर विचार करें $f(x_{1},\ldots ,x_{2n})=x_{1}x_{2}+x_{3}x_{4}+\cdots +x_{2n-1}x_{2n}.$ चर आदेश का उपयोग करना $x_{1}<x_{3}<\cdots <x_{2n-1}<x_{2}<x_{4}<\cdots <x_{2n}$ , बीडीडी की जरूरत है $2^{n+1}$ फ़ंक्शन का प्रतिनिधित्व करने के लिए नोड्स। आदेश का उपयोग करना $x_{1}<x_{2}<x_{3}<x_{4}<\cdots <x_{2n-1}<x_{2n}$ , बीडीडी में शामिल हैं $2n+2$ नोड्स।

फ़ंक्शन के लिए बीडीडी ƒ(x₁, ..., x₈) = x₁x₂ + x₃x₄ + x₅x₆ + x₇x₈ खराब चर क्रम का उपयोग करना

अच्छा परिवर्तन क्रम

इस डेटा संरचना को व्यवहार में लागू करते समय चर क्रम का ध्यान रखना महत्वपूर्ण है। सबसे अच्छा परिवर्तनीय अनुक्रम खोजने की समस्या एनपी-हार्ड है। ^[13]किसी भी स्थिरांक c> 1 के लिए एक चर क्रम की गणना करना और भी अधिक एनपी-कठिन है, जिसके परिणामस्वरूप एक Oबीडीडी एक आकार के साथ होता है जो एक इष्टतम से अधिक से अधिक c गुना बड़ा होता है।^[14]हालांकि, समस्या से निपटने के लिए प्रभावी अनुमान मौजूद हैं।^[15]

ऐसे फ़ंक्शन हैं जिनके लिए ग्राफ़ का आकार हमेशा घातीय होता है-चर क्रम से स्वतंत्र। यह धारण उदा. गुणन फ़ंक्शन के लिए।^[1]वास्तव में, फ़ंक्शन दो के उत्पाद के मध्य बिट की गणना करता है $n$ -बिट संख्याओं में एक Oबीडीडी की तुलना में छोटा नहीं है $2^{\lfloor n/2\rfloor }/61-4$ कोने।^[16] (यदि गुणन फ़ंक्शन में बहुपद-आकार के ओबीडीडी थे, तो यह दिखाएगा कि पूर्णांक कारक पी/पाली (p/poly)) में है, जो सच नहीं है।^[17]

शोधकर्ता बीडीडी डेटा संरचना पर एक शोधन का सुझाव देते हैं, जो बीएमडी (बाइनरी मोमेंट डायग्राम), जेडडीडी (जीरो-सप्रेस्ड डिसीजन डायग्राम), एफडीडी (फ्री बाइनरी डिसीजन डायग्राम), पीडीडी (पैरिटी डिसीजन डायग्राम) जैसे कई संबंधित ग्राफों को रास्ता देता है। ), और एमटीबीडीडी (MTBDDs) 0 (एकाधिक टर्मिनल बीडीडी)।

बीडीडी पर तार्किक संचालन

बीडीडी पर कई तार्किक संचालन बहुपद-समय ग्राफ हेरफेर एल्गोरिदम द्वारा कार्यान्वित किए जा सकते हैं ^[18]^: 20

संयोजक
असंतुष्ट
उपेक्षा

हालांकि, इन संचालनों को कई बार दोहराते हुए, उदाहरण के लिए, बीडीडी या संयोजनों का एक समुच्चय बनाना, सबसे खराब स्थिति में तेजी से बड़ा बीडीडी हो सकता है। इसका कारण यह है कि दो बीडीडी के लिए किसी भी पिछले संचालन के परिणामस्वरूप बीडीडी के आकार के उत्पाद के आनुपातिक आकार के साथ बीडीडी हो सकता है, और इसके परिणामस्वरूप कई बीडीडी के लिए आकार संचालन की संख्या में घातीय हो सकता है। परिवर्तनीय क्रम को एक नए रूप की जरूरत है; बीडीडी के समुच्चय (इनमें से कुछ) के लिए एक अच्छा क्रम क्या हो सकता है, संचालन के परिणाम के लिए एक अच्छा क्रम नहीं हो सकता है। इसके अलावा, चूंकि बूलियन फ़ंक्शन के बीडीडी के निर्माण से एनपी-पूर्ण (NP-complete) बूलियन संतुष्टि समस्या और सह-एनपी-पूर्ण (co-NP-complete) पुनरुक्ति समस्या हल हो जाती है, बीडीडी के निर्माण में बूलियन फॉर्मूला के आकार के लिए घातीय समय लग सकता है, भले ही जिसके परिणामस्वरूप बीडीडी छोटा है। .

कम बीडीडी के कई चर पर अस्तित्व संबंधी अमूर्तता की गणना एनपी-पूर्ण है (NP-complete)।^[19]

मॉडल-गिनती, एक बूलियन सूत्र को संतुष्ट करने वाले असाइनमेंट की संख्या की गणना, बीडीडी के लिए बहुपद समय में की जा सकती है। सामान्य प्रस्ताव संबंधी सूत्रों के लिए, समस्या पी-पूर्ण है और सबसे अच्छी तरह से ज्ञात कलन विधि को सबसे खराब स्थिति में घातीय समय की आवश्यकता होती है।

यह भी देखें

बूलियन संतुष्टि समस्या, विहित एनपी-पूर्ण कम्प्यूटेशनल समस्या
एल/पॉली, एक जटिलता वर्ग जिसमें बहुपद आकार के बीडीडी के साथ समस्याओं का समुच्चय सख्ती से शामिल है^{[citation needed]}
मॉडल जाँच
रेडिक्स ट्री
बैरिंगटन की प्रमेय
हार्डवेयर एक्सिलरेशन
कर्णघ मानचित्र, बूलियन बीजगणित के भावों को सरल बनाने की एक विधि
शून्य दबाया निर्णय आरेख

संदर्भ

↑ ^1.0 ^1.1 Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986
↑ ^2.0 ^2.1 Karl S. Brace, Richard L. Rudell and Randal E. Bryant. "Efficient Implementation of a BDD Package". In Proceedings of the 27th ACM/IEEE Design Automation Conference (DAC 1990), pages 40–45. IEEE Computer Society Press, 1990.
↑ Fabio Somenzi, "Binary decision diagrams", Calculational system design, Vol.173, NATO Science Series F: Computer and systems sciences, pp. 303--366, IOS Press, 1999
↑ C. Y. Lee. "Representation of Switching Circuits by Binary-Decision Programs". Bell System Technical Journal, 38:985–999, 1959.
↑ Sheldon B. Akers, Jr. Binary Decision Diagrams, IEEE Transactions on Computers, C-27(6):509–516, June 1978.
↑ Raymond T. Boute, "The Binary Decision Machine as a programmable controller". EUROMICRO Newsletter, Vol. 1(2):16–22, January 1976.
↑ Yu. V. Mamrukov, Analysis of aperiodic circuits and asynchronous processes. Ph.D. dissertation. Leningrad Electrotechnical Institute, 1984, 219 p.
↑ Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation". IEEE Transactions on Computers, C-35(8):677–691, 1986.
↑ Randal E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293–318.
↑ "Stanford Center for Professional Development". scpd.stanford.edu. Archived from the original on 4 June 2014. Retrieved 23 April 2018.
↑ R. M. Jensen. "CLab: A C+ + library for fast backtrack-free interactive product configuration". Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming, 2004.
↑ H. L. Lipmaa. "First CPIR Protocol with Data-Dependent Computation". ICISC 2009.
↑ Beate Bollig, Ingo Wegener. Improving the Variable Ordering of OBDDs Is NP-Complete, IEEE Transactions on Computers, 45(9):993–1002, September 1996.
↑ Detlef Sieling. "The nonapproximability of OBDD minimization." Information and Computation 172, 103–138. 2002.
↑ Rice, Michael. "A Survey of Static Variable Ordering Heuristics for Efficient BDD/MDD Construction" (PDF).
↑ Philipp Woelfel. "Bounds on the OBDD-size of integer multiplication via universal hashing." Journal of Computer and System Sciences 71, pp. 520-534, 2005.
↑ Richard J. Lipton. "BDD's and Factoring". Gödel's Lost Letter and P=NP, 2009.
↑ Andersen, H. R. (1999). "An Introduction to Binary Decision Diagrams" (PDF). Lecture Notes. IT University of Copenhagen.
↑ Huth, Michael; Ryan, Mark (2004). Logic in computer science: modelling and reasoning about systems (2 ed.). Cambridge [U.K.]: Cambridge University Press. pp. 380–. ISBN 978-0-52154310-1. OCLC 54960031.

अग्रिम पठन

R. Ubar, "Test Generation for Digital Circuits Using Alternative Graphs (in Russian)", in Proc. Tallinn Technical University, 1976, No. 409, Tallinn Technical University, Tallinn, Estonia, pp. 75–81.
D. E. Knuth, "The Art of Computer Programming Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams" (Addison–Wesley Professional, March 27, 2009) viii+260pp, ISBN 0-321-58050-8. Draft of Fascicle 1b available for download.
Ch. Meinel, T. Theobald, "Algorithms and Data Structures in VLSI-Design: Oबीडीडी – Foundations and Applications", Springer-Verlag, Berlin, Heidelberg, New York, 1998. Complete textbook available for download.
Ebendt, Rüdiger; Fey, Görschwin; Drechsler, Rolf (2005). Advanced BDD optimization. Springer. ISBN 978-0-387-25453-1.
Becker, Bernd; Drechsler, Rolf (1998). Binary Decision Diagrams: Theory and Implementation. Springer. ISBN 978-1-4419-5047-5.

बाहरी संबंध

Fun With Binary Decision Diagrams (BDDs), lecture by Donald Knuth
List of बीडीडी software libraries for several programming languages.

[Bryant1986-1] 1.0 ^1.1 Graph-Based Algorithms for Boolean Function Manipulation, Randal E. Bryant, 1986

[Brace-2] 2.0 ^2.1 Karl S. Brace, Richard L. Rudell and Randal E. Bryant. "Efficient Implementation of a BDD Package". In Proceedings of the 27th ACM/IEEE Design Automation Conference (DAC 1990), pages 40–45. IEEE Computer Society Press, 1990.

[Somenzi1999-3] Fabio Somenzi, "Binary decision diagrams", Calculational system design, Vol.173, NATO Science Series F: Computer and systems sciences, pp. 303--366, IOS Press, 1999

[Lee-4] C. Y. Lee. "Representation of Switching Circuits by Binary-Decision Programs". Bell System Technical Journal, 38:985–999, 1959.

[Akers-5] Sheldon B. Akers, Jr. Binary Decision Diagrams, IEEE Transactions on Computers, C-27(6):509–516, June 1978.

[Boute_1976-6] Raymond T. Boute, "The Binary Decision Machine as a programmable controller". EUROMICRO Newsletter, Vol. 1(2):16–22, January 1976.

[7] Yu. V. Mamrukov, Analysis of aperiodic circuits and asynchronous processes. Ph.D. dissertation. Leningrad Electrotechnical Institute, 1984, 219 p.

[Bryant-1986-8] Randal E. Bryant. "Graph-Based Algorithms for Boolean Function Manipulation". IEEE Transactions on Computers, C-35(8):677–691, 1986.

[Bryant-1992-9] Randal E. Bryant, "Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams", ACM Computing Surveys, Vol. 24, No. 3 (September, 1992), pp. 293–318.

[Stanford-10] "Stanford Center for Professional Development". scpd.stanford.edu. Archived from the original on 4 June 2014. Retrieved 23 April 2018.

[Jensen-11] R. M. Jensen. "CLab: A C+ + library for fast backtrack-free interactive product configuration". Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming, 2004.

[Lipmaa-12] H. L. Lipmaa. "First CPIR Protocol with Data-Dependent Computation". ICISC 2009.

[Bollig-13] Beate Bollig, Ingo Wegener. Improving the Variable Ordering of OBDDs Is NP-Complete, IEEE Transactions on Computers, 45(9):993–1002, September 1996.

[Sieling-14] Detlef Sieling. "The nonapproximability of OBDD minimization." Information and Computation 172, 103–138. 2002.

[Rice-15] Rice, Michael. "A Survey of Static Variable Ordering Heuristics for Efficient BDD/MDD Construction" (PDF).

[Woelfel_2005-16] Philipp Woelfel. "Bounds on the OBDD-size of integer multiplication via universal hashing." Journal of Computer and System Sciences 71, pp. 520-534, 2005.

[Lipton_2009-17] Richard J. Lipton. "BDD's and Factoring". Gödel's Lost Letter and P=NP, 2009.

[Andersen_1999-18] Andersen, H. R. (1999). "An Introduction to Binary Decision Diagrams" (PDF). Lecture Notes. IT University of Copenhagen.

[Huth-19] Huth, Michael; Ryan, Mark (2004). Logic in computer science: modelling and reasoning about systems (2 ed.). Cambridge [U.K.]: Cambridge University Press. pp. 380–. ISBN 978-0-52154310-1. OCLC 54960031.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

@@ Line 1: / Line 1: @@
-कंप्यूटर विज्ञान में, बाइनरी निर्णय आरेख (BDD) या ब्रांचिंग प्रोग्राम एक डेटा संरचना है जिसका उपयोग बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है। अधिक सार स्तर पर, BDD को समुच्चय या संबंधों के एक सघन प्रतिनिधित्व के रूप में माना जा सकता है। अन्य संपीड़ित अभ्यावेदन के विपरीत, संचालन सीधे संपीड़ित प्रतिनिधित्व पर किया जाता है, अर्थात बिना विघटन के।
+कंप्यूटर विज्ञान में, '''बाइनरी निर्णय आरेख'''(बीडीडी) या ब्रांचिंग प्रोग्राम एक डेटा संरचना है जिसका उपयोग बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है। अधिक सार स्तर पर, बीडीडी को समुच्चय या संबंधों के एक सघन प्रतिनिधित्व के रूप में माना जा सकता है। अन्य संपीड़ित अभ्यावेदन के विपरीत, संचालन सीधे संपीड़ित प्रतिनिधित्व पर किया जाता है, अर्थात बिना विघटन के।
-इसी तरह की डेटा संरचनाओं में नकारात्मक सामान्य रूप (NNF), ज़ेगल्किन बहुपद, और प्रस्तावक निर्देशित विश्वकोश रेखांकन (PDAG) शामिल हैं।
+इसी तरह की डेटा संरचनाओं में ऋणात्मक सामान्य रूप (एनएनएफ), ज़ेगल्किन बहुपद, और प्रस्तावक निर्देशित विश्वकोश रेखांकन (पीडीएजी) शामिल हैं।
 == परिभाषा ==
-एक बूलियन फ़ंक्शन को एक रूटेड, निर्देशित, एसाइक्लिक ग्राफ के रूप में दर्शाया जा सकता है, जिसमें कई (निर्णय) नोड्स और दो टर्मिनल नोड होते हैं। दो टर्मिनल नोड्स को 0 (FALSE) और 1 (TRUE) के रूप में लेबल किया गया है। प्रत्येक (निर्णय) नोड <math>u</math> को एक बूलियन चर <math>x_i</math> द्वारा लेबल किया गया है और इसमें दो चाइल्ड नोड्स हैं जिन्हें लो चाइल्ड और हाई चाइल्ड कहा जाता है। नोड <math>u</math> से निम्न (या उच्च) बच्चे तक का किनारा चर <math>x_i</math>के मान FALSE (या TRUE, क्रमशः) के एक असाइनमेंट को दर्शाता है। ऐसे BDD को 'आदेशित' कहा जाता है यदि मूल से सभी पथों पर विभिन्न चर एक ही क्रम में प्रकट होते हैं। एक बीडीडी को 'कम' कहा जाता है यदि निम्नलिखित दो नियमों को इसके ग्राफ पर लागू किया गया है:
+एक बूलियन फ़ंक्शन को एक रूटेड, निर्देशित, एसाइक्लिक ग्राफ के रूप में दर्शाया जा सकता है, जिसमें कई (निर्णय) नोड्स और दो टर्मिनल नोड होते हैं। दो टर्मिनल नोड्स को 0 (FALSE) और 1 (TRUE) के रूप में लेबल किया गया है। प्रत्येक (निर्णय) नोड <math>u</math> को एक बूलियन चर <math>x_i</math> द्वारा लेबल किया गया है और इसमें दो चाइल्ड नोड्स हैं जिन्हें लो चाइल्ड और हाई चाइल्ड कहा जाता है। नोड <math>u</math> से निम्न (या उच्च) चाइल्ड तक का किनारा चर <math>x_i</math>के मान FALSE (या TRUE, क्रमशः) के एक असाइनमेंट को दर्शाता है। ऐसे पीडीएजी को 'आदेशित' कहा जाता है यदि मूल से सभी पथों पर विभिन्न चर एक ही क्रम में प्रकट होते हैं। एक बीडीडी को 'कम' कहा जाता है यदि निम्नलिखित दो नियमों को इसके ग्राफ पर लागू किया गया है:
 * किसी भी समरूपी उप-अनुच्छेदों को मिलाइए।
-* ऐसे किसी भी नोड को हटा दें जिसके दो बच्चे समरूपी हों।
+* ऐसे किसी भी नोड को हटा दें जिसके दो चाइल्ड समरूपी हों।
-लोकप्रिय उपयोग में, बीडीडी शब्द लगभग हमेशा एक कम आदेशित द्विआधारी निर्णय आरेख होता है (साहित्य में आरओबीबीडी का उपयोग तब किया जाता है जब आदेश और कमी के पहलुओं पर जोर दिया जाना चाहिए)। ROBDD का लाभ यह है कि यह किसी विशेष कार्य और परिवर्तनशील क्रम के लिए विहित (अद्वितीय) है।<ref name="Bryant1986"/> यह गुण इसे कार्यात्मक तुल्यता जाँच और कार्यात्मक प्रौद्योगिकी मानचित्रण जैसे अन्य कार्यों में उपयोगी बनाता है।
+लोकप्रिय उपयोग में, बीडीडी शब्द लगभग हमेशा एक कम आदेशित द्विआधारी निर्णय आरेख होता है (साहित्य में आरओबीबीडी का उपयोग तब किया जाता है जब आदेश और कमी के पहलुओं पर जोर दिया जाना चाहिए)। आरओबीडीडी (ROBDD) 0 का लाभ यह है कि यह किसी विशेष कार्य और परिवर्तनशील क्रम के लिए विहित (अद्वितीय) है।<ref name="Bryant1986"/> यह गुण इसे कार्यात्मक तुल्यता जाँच और कार्यात्मक प्रौद्योगिकी मानचित्रण जैसे अन्य कार्यों में उपयोगी बनाता है।
-रूट नोड से 1-टर्मिनल तक का पथ एक (संभवतः आंशिक) वैरिएबल असाइनमेंट का प्रतिनिधित्व करता है जिसके लिए प्रतिनिधित्व एक बूलियन फ़ंक्शन सत्य है। चूंकि पथ एक नोड से निचले (या उच्चतर) बच्चे तक जाता है, उस नोड का चर 0 (क्रमशः) नियत किया जाता है।
+रूट नोड से 1-टर्मिनल तक का पथ एक (संभवतः आंशिक) वैरिएबल असाइनमेंट का प्रतिनिधित्व करता है जिसके लिए प्रतिनिधित्व एक बूलियन फ़ंक्शन सत्य है। चूंकि पथ एक नोड से निचले (या उच्चतर) चाइल्ड तक जाता है, उस नोड का चर 0 (क्रमशः) नियत किया जाता है।
 === उदाहरण ===
-नीचे दिया गया आंकड़ा एक द्विआधारी निर्णय पेड़ दिखाता है (कमी नियम लागू नहीं होते हैं), और एक सत्य तालिका, प्रत्येक फ़ंक्शन <math>f(x1, x2, x3)</math> का प्रतिनिधित्व करता है। बाईं ओर के पेड़ में, किसी दिए गए चर असाइनमेंट के लिए फ़ंक्शन का मान निर्धारित किया जा सकता है एक टर्मिनल के लिए ग्राफ़ के नीचे पथ का अनुसरण करना। नीचे दिए गए आंकड़ों में, बिंदीदार रेखाएं कम बच्चे के किनारों का प्रतिनिधित्व करती हैं, जबकि ठोस रेखाएं किनारों को उच्च बच्चे को दर्शाती हैं। इसलिए, f(0,1,1) को खोजने के लिए, x1 से शुरू करें, बिंदीदार रेखा को x2 तक ले जाएं (चूंकि x1 में 0 को असाइनमेंट है), और फिर दो ठोस रेखाएं नीचे आती हैं (चूंकि x2 और x3 प्रत्येक में एक को असाइनमेंट होता है)। यह टर्मिनल 1 की ओर जाता है, जो <math>f(0, 1, 1)</math> का मान है।
+नीचे दिया गया आंकड़ा एक द्विआधारी  डिसिशन ट्री  दिखाता है (कमी नियम लागू नहीं होते हैं), और एक सत्य तालिका, प्रत्येक फ़ंक्शन <math>f(x1, x2, x3)</math> का प्रतिनिधित्व करता है। बाईं ओर के ट्री में, किसी दिए गए चर असाइनमेंट के लिए फ़ंक्शन का मान निर्धारित किया जा सकता हैl एक टर्मिनल के लिए ग्राफ़ के नीचे पथ का अनुसरण करना और नीचे दिए गए आंकड़ों में, बिंदीदार रेखाएं कम चाइल्ड के किनारों का प्रतिनिधित्व करती हैं, जबकि ठोस रेखाएं किनारों को उच्च चाइल्ड को दर्शाती हैं। इसलिए, f(0,1,1) को खोजने के लिए, x1 से शुरू करें, बिंदीदार रेखा को x2 तक ले जाएं (चूंकि x1 में 0 को असाइनमेंट है), और फिर दो ठोस रेखाएं नीचे आती हैं (चूंकि x2 और x3 प्रत्येक में एक को असाइनमेंट होता है)। यह टर्मिनल 1 की ओर जाता है, जो <math>f(0, 1, 1)</math> का मान है। बायीं आकृति में बाइनरी निर्णय ट्री को दो कमी नियमों के अनुसार अधिकतम को कम करके बाइनरी निर्णय आरेख में बदला जा सकता है। परिणामी बीडीडी को सही आकृति में दिखाया गया है।
-बायीं आकृति में बाइनरी निर्णय ट्री को दो कमी नियमों के अनुसार अधिकतम को कम करके बाइनरी निर्णय आरेख में बदला जा सकता है। परिणामी BDD को सही आकृति में दिखाया गया है।
 {| align="center"
 |-
-| [[File:BDD.png|thumb|546px|Binary decision tree and [[truth table]] for the function <math>f(x_1, x_2, x_3)=(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1 \wedge x_2) \vee (x_2 \wedge x_3)</math>, described in notation for [[Boolean algebra#Basic operations|Boolean operators]].]]
+| [[File:BDD.png|thumb|546px|फ़ंक्शन के लिए बाइनरी डिसीजन ट्री और ट्रुथ टेबल<math>f(x_1, x_2, x_3)=(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1 \wedge x_2) \vee (x_2 \wedge x_3)</math>, बूलियन ऑपरेटरों के लिए संकेतन में वर्णित है।]]
-| [[File:BDD simple.svg|thumb|189px|BDD for the function ''f'']]
+| [[File:BDD simple.svg|thumb|189px|फ़ंक्शन ''f'' के लिए बीडीडी ]]
 |}
 इस बूलियन फ़ंक्शन को लिखने के लिए एक और संकेतन <math>\overline{x}_1 \overline{x}_2 \overline{x}_3 + x_1 x_2 + x_2 x_3</math> है।
@@ Line 24: / Line 23: @@
 === पूरक किनारे ===
-[[File:BDD diagram with complemented edges.png|thumb|alt=Diagram of a binary decision diagram represented using complemented edges। एक द्विआधारी निर्णय आरेख का आरेख पूरक किनारों का उपयोग करके दर्शाया गया है।]]
+[[File:BDD diagram with complemented edges.png|thumb|alt=Diagram of a binary decision diagram represented using complemented edges। एक द्विआधारी निर्णय आरेख का आरेख पूरक किनारों का उपयोग करके दर्शाया गया है।|पूरक किनारों का उपयोग करके दर्शाए गए द्विआधारी निर्णय आरेख का आरेख।]]
-एक ROBDD को पूरक किनारों का उपयोग करके और भी अधिक सघन रूप से दर्शाया जा सकता है।<ref name="Brace"/><ref name="Somenzi1999"/> पूरक किनारों का निर्माण निम्नलिखित किनारों को पूरक के रूप में व्याख्या करके किया गया है या नहीं। यदि एक किनारे को पूरक किया जाता है, तो यह एक बूलियन फ़ंक्शन की अस्वीकृति को संदर्भित करता है जो एक नोड से मेल खाता है जो एक किनारे की ओर इशारा करता है (बूलियन फ़ंक्शन उस नोड की जड़ के साथ बीडीडी द्वारा दर्शाया गया है)। यह सुनिश्चित करने के लिए कि परिणामी BDD प्रतिनिधित्व एक विहित रूप है, उच्च किनारों को पूरक नहीं किया गया है। इस निरूपण में, बीडीडी में एक एकल पत्ती नोड होता है, नीचे बताए गए कारणों के लिए।
+एक आरओबीडीडी (ROBDD) को पूरक किनारों का उपयोग करके और भी अधिक सघन रूप से दर्शाया जा सकता है।<ref name="Brace"/><ref name="Somenzi1999"/> पूरक किनारों का निर्माण निम्नलिखित किनारों को पूरक के रूप में व्याख्या करके किया गया है या नहीं। यदि एक किनारे को पूरक किया जाता है, तो यह एक बूलियन फ़ंक्शन की अस्वीकृति को संदर्भित करता है जो एक नोड से मेल खाता है जो एक किनारे की ओर इशारा करता है (बूलियन फ़ंक्शन उस नोड की जड़ के साथ बीडीडी द्वारा दर्शाया गया है)। यह सुनिश्चित करने के लिए कि परिणामी बीडीडी प्रतिनिधित्व एक विहित रूप है, उच्च किनारों को पूरक नहीं किया गया है। इस निरूपण में, बीडीडी में एक एकल पत्ती नोड होता है, नीचे बताए गए कारणों के लिए।
-BDDs का प्रतिनिधित्व करते समय पूरक किनारों का उपयोग करने के दो लाभ हैं:
+बीडीडी का प्रतिनिधित्व करते समय पूरक किनारों का उपयोग करने के दो लाभ हैं:
-* BDD के निषेध की गणना करने में निरंतर समय लगता है
+* बीडीडी के निषेध की गणना करने में निरंतर समय लगता है
 * स्पेस उपयोग (यानी, आवश्यक मेमोरी) कम हो जाता है
-इस प्रतिनिधित्व में, बीडीडी का संदर्भ एक (संभवतः पूरक) "किनारे" है जो बीडीडी की जड़ को इंगित करता है। यह पूरक किनारों के उपयोग के बिना प्रतिनिधित्व में बीडीडी के संदर्भ के विपरीत है, जो बीडीडी के मूल नोड हैं। इस प्रतिनिधित्व में एक संदर्भ बढ़त होने का कारण यह है कि प्रत्येक बूलियन फ़ंक्शन के लिए, फ़ंक्शन और इसके निषेध को एक किनारे से दर्शाया जाता है जो एक BDD की मूल तक जाता है, और एक ही BDD की जड़ के पूरक किनारे का प्रतिनिधित्व करता है। यही कारण है कि नकारने में निरंतर समय लगता है। यह यह भी बताता है कि एक एकल निष्पर्ण पर्याप्त क्यों है: FALSE को एक पूरक किनारे द्वारा दर्शाया जाता है जो एक पत्ती नोड को इंगित करता है, और TRUE को एक साधारण किनारे (अर्थात, पूरक नहीं) द्वारा दर्शाया जाता है जो कि निष्पर्ण को इंगित करता है।
+इस प्रतिनिधित्व में, बीडीडी का संदर्भ एक (संभवतः पूरक) "किनारे" है जो बीडीडी की जड़ को इंगित करता है। यह पूरक किनारों के उपयोग के बिना प्रतिनिधित्व में बीडीडी के संदर्भ के विपरीत है, जो बीडीडी के मूल नोड हैं। इस प्रतिनिधित्व में एक संदर्भ बढ़त होने का कारण यह है कि प्रत्येक बूलियन फ़ंक्शन के लिए, फ़ंक्शन और इसके निषेध को एक किनारे से दर्शाया जाता है जो एक बीडीडी की मूल तक जाता है, और एक ही बीडीडी की जड़ के पूरक किनारे का प्रतिनिधित्व करता है। यही कारण है कि नकारने में निरंतर समय लगता है। यह यह भी बताता है कि एक एकल निष्पर्ण पर्याप्त क्यों है: FALSE को एक पूरक किनारे द्वारा दर्शाया जाता है जो एक पत्ती नोड को इंगित करता है, और TRUE को एक साधारण किनारे (अर्थात, पूरक नहीं) द्वारा दर्शाया जाता है जो कि निष्पर्ण को इंगित करता है।
-उदाहरण के लिए, मान लीजिए कि एक बूलियन फ़ंक्शन को पूरक किनारों का उपयोग करके दर्शाए गए BDD के साथ दर्शाया गया है। एक चर के लिए दिए गए असाइनमेंट (बूलियन) के लिए एक बूलियन फ़ंक्शन का मान खोजने के लिए, हम संदर्भ किनारे से शुरू करते हैं, जो BDD की जड़ को इंगित करता है और दिए गए चर मानों द्वारा परिभाषित पथ का अनुसरण करता है (बाद में) यदि नोड को लेबल करने वाला चर FALSE के बराबर है और उच्च किनारे का अनुसरण करता है यदि नोड को लेबल करने वाला चर TRUE के बराबर है), जब तक हम निष्पर्ण तक नहीं पहुंच जाते। इस पथ का अनुसरण करते हुए, हम गिनते हैं कि हमने कितने पूरक किनारों को पार किया है। यदि हम निष्पर्ण तक पहुँचते हैं तो हमने विषम संख्या में पूरक किनारों को पार कर लिया है, तो दिए गए चर असाइनमेंट के लिए बूलियन फ़ंक्शन का मान FALSE है, अन्यथा (यदि हमने पूरक किनारों की एक सम संख्या को पार कर लिया है), तो का मान दिए गए चर असाइनमेंट के लिए बूलियन फ़ंक्शन TRUE है।
+उदाहरण के लिए, मान लीजिए कि एक बूलियन फ़ंक्शन को पूरक किनारों का उपयोग करके दर्शाए गए बीडीडी के साथ दर्शाया गया है। एक चर के लिए दिए गए असाइनमेंट (बूलियन) के लिए एक बूलियन फ़ंक्शन का मान खोजने के लिए, हम संदर्भ किनारे से शुरू करते हैं, जो बीडीडी की जड़ को इंगित करता है और दिए गए चर मानों द्वारा परिभाषित पथ का अनुसरण करता है (बाद में) यदि नोड को लेबल करने वाला चर FALSE के बराबर है और उच्च किनारे का अनुसरण करता है यदि नोड को लेबल करने वाला चर TRUE के बराबर है), जब तक हम निष्पर्ण तक नहीं पहुंच जाते। इस पथ का अनुसरण करते हुए, हम गिनते हैं कि हमने कितने पूरक किनारों को पार किया है। यदि हम निष्पर्ण तक पहुँचते हैं तो हमने विषम संख्या में पूरक किनारों को पार कर लिया है, तो दिए गए चर असाइनमेंट के लिए बूलियन फ़ंक्शन का मान FALSE है, अन्यथा (यदि हमने पूरक किनारों की एक सम संख्या को पार कर लिया है), तो का मान दिए गए चर असाइनमेंट के लिए बूलियन फ़ंक्शन TRUE है।
-इस प्रतिनिधित्व में एक बीडीडी का एक उदाहरण आरेख दाईं ओर दिखाया गया है, और उसी बूलियन अभिव्यक्ति का प्रतिनिधित्व करता है जैसा कि ऊपर के चित्र में दिखाया गया है, अर्थात <math>(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1 \wedge x_2) \vee (x_2 \wedge x_3)</math>। कम किनारों को धराशायी कर दिया जाता है, उच्च किनारों को ठोस, और पूरक किनारों को "-1" लेबल द्वारा दर्शाया जाता है। नोड जिसका लेबल @ प्रतीक से शुरू होता है, वह BDD के संदर्भ का प्रतिनिधित्व करता है, अर्थात संदर्भ किनारा वह किनारा है जो इस नोड से शुरू होता है।
+इस प्रतिनिधित्व में एक बीडीडी का एक उदाहरण आरेख दाईं ओर दिखाया गया है, और उसी बूलियन अभिव्यक्ति का प्रतिनिधित्व करता है जैसा कि ऊपर के चित्र में दिखाया गया है, अर्थात <math>(\neg x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1 \wedge x_2) \vee (x_2 \wedge x_3)</math>। कम किनारों को धराशायी कर दिया जाता है, उच्च किनारों को ठोस, और पूरक किनारों को "-1" लेबल द्वारा दर्शाया जाता है। नोड जिसका लेबल @ प्रतीक से शुरू होता है, वह बीडीडी के संदर्भ का प्रतिनिधित्व करता है, अर्थात संदर्भ किनारा वह किनारा है जो इस नोड से शुरू होता है।
 == इतिहास ==
-मूल विचार जिससे डेटा संरचना बनाई गई थी वह शैनन विस्तार है। एक स्विचिंग फ़ंक्शन को एक चर (सीएफ अगर-तब-अन्य सामान्य रूप) निर्दिष्ट करके दो उप-फ़ंक्शन (सहकारकों) में विभाजित किया जाता है। यदि ऐसे उप-कार्य को उप-वृक्ष के रूप में माना जाता है, तो इसे एक द्विआधारी निर्णय ट्री द्वारा दर्शाया जा सकता है। बाइनरी निर्णय आरेख (BDDs) को सी. वाई. ली द्वारा पेश किया गया था,<ref name="Lee"/> और शेल्डन बी. एकर्स <ref name="Akers"/> और रेमंड टी. आगे के अध्ययन के बारे में बाउट द्वारा जाना जाता था।<ref name="Boute_1976"/> इन लेखकों से स्वतंत्र रूप से, यूके में "कैननिकल ब्रैकेट फॉर्म" नाम से एक बीडीडी पेश किया गया था। सीएडी में वी मोशन-इंडिपेंडेंट सर्किट ममरुकोव के विश्लेषण के लिए। <ref>[https://b-ok.asia/book/3701100/47f57d Yu. V. Mamrukov, Analysis of aperiodic circuits and asynchronous processes. Ph.D. dissertation. Leningrad Electrotechnical Institute, 1984, 219 p.]</ref> डेटा संरचना के आधार पर कुशल कलन विधि के लिए पूरी क्षमता की जांच कार्नेगी मेलन विश्वविद्यालय में रैंडल ब्रायंट द्वारा की गई थी: उनके प्रमुख एक्सटेंशन एक निश्चित चर ऑर्डर (कैनोनिकल प्रतिनिधित्व के लिए) और साझा उप-ग्राफ (संपीड़न के लिए) का उपयोग करने के लिए थे। इन दो अवधारणाओं को लागू करने से समुच्चय और संबंधों के प्रतिनिधित्व के लिए एक कुशल डेटा संरचना और कलन विधि का परिणाम होता है।<ref name="Bryant-1986"/><ref name="Bryant-1992"/> साझाकरण को कई BDDs तक विस्तारित करके, अर्थात कई BDD द्वारा एक उप-ग्राफ का उपयोग किया जाता है, डेटा संरचना साझा कम किए गए आदेशित बाइनरी निर्णय आरेख को परिभाषित किया गया है।<ref name="Brace"/> BDD की धारणा अब आमतौर पर उस विशेष डेटा संरचना को संदर्भित करने के लिए उपयोग की जाती है।
+मूल विचार जिससे डेटा संरचना बनाई गई थी वह शैनन विस्तार है। एक स्विचिंग फ़ंक्शन को एक चर (सीएफ अगर-तब-अन्य सामान्य रूप) निर्दिष्ट करके दो उप-फ़ंक्शन (सहकारकों) में विभाजित किया जाता है। यदि ऐसे उप-कार्य को उप-वृक्ष के रूप में माना जाता है, तो इसे एक द्विआधारी निर्णय ट्री द्वारा दर्शाया जा सकता है। बाइनरी निर्णय आरेख (बीडीडी) को सी. वाई. ली द्वारा पेश किया गया था,<ref name="Lee"/> और शेल्डन बी. एकर्स <ref name="Akers"/> और रेमंड टी. आगे के अध्ययन के बारे में बाउट द्वारा जाना जाता था।<ref name="Boute_1976"/> इन लेखकों से स्वतंत्र रूप से, यूके में "कैननिकल ब्रैकेट फॉर्म" नाम से एक बीडीडी पेश किया गया था। सीएडी में वी मोशन-इंडिपेंडेंट सर्किट ममरुकोव के विश्लेषण के लिए। <ref>[https://b-ok.asia/book/3701100/47f57d Yu. V. Mamrukov, Analysis of aperiodic circuits and asynchronous processes. Ph.D. dissertation. Leningrad Electrotechnical Institute, 1984, 219 p.]</ref> डेटा संरचना के आधार पर कुशल कलन विधि के लिए पूरी क्षमता की जांच कार्नेगी मेलन विश्वविद्यालय में रैंडल ब्रायंट द्वारा की गई थी: उनके प्रमुख विस्तार एक निश्चित चर क्रम (कैनोनिकल प्रतिनिधित्व के लिए) और साझा उप-ग्राफ (संपीड़न के लिए) का उपयोग करने के लिए थे। इन दो अवधारणाओं को लागू करने से समुच्चय और संबंधों के प्रतिनिधित्व के लिए एक कुशल डेटा संरचना और कलन विधि का परिणाम होता है।<ref name="Bryant-1986"/><ref name="Bryant-1992"/> साझाकरण को कई बीडीडी तक विस्तारित करके, अर्थात कई बीडीडी द्वारा एक उप-ग्राफ का उपयोग किया जाता है, डेटा संरचना साझा कम किए गए आदेशित बाइनरी निर्णय आरेख को परिभाषित किया गया है।<ref name="Brace"/> बीडीडी की धारणा अब आमतौर पर उस विशेष डेटा संरचना को संदर्भित करने के लिए उपयोग की जाती है।
-अपने वीडियो लेक्चर फन विद बाइनरी निर्णय आरेखों (Fun with Binary Decision Diagrams) में,डोनाल्ड नुथ ने BDDs को "पिछले पच्चीस वर्षों में सामने आए एकमात्र वास्तव में मौलिक डेटा संरचनाओं में से एक" कहा और उल्लेख किया कि ब्रायंट का 1986 का पेपर कुछ समय के लिए था। कंप्यूटर विज्ञान में सबसे ज्यादा उद्धृत पत्रों में से एक था।
+अपने वीडियो लेक्चर फन विद बाइनरी निर्णय आरेखों (Fun with Binary Decision Diagrams) में,डोनाल्ड नुथ ने बीडीडी को "पिछले पच्चीस वर्षों में सामने आए एकमात्र वास्तव में मौलिक डेटा संरचनाओं में से एक" कहा और उल्लेख किया कि ब्रायंट का 1986 का पेपर कुछ समय के लिए था। कंप्यूटर विज्ञान में सबसे ज्यादा उद्धृत पत्रों में से एक था।<ref name="Stanford"/>
-अदनान डारविच और उनके सहयोगियों ने दिखाया है कि BDD बूलियन कार्यों के लिए कई सामान्य रूपों में से एक है, प्रत्येक आवश्यकताओं के एक अलग संयोजन द्वारा संचालित है। डारविच द्वारा पहचाना जाने वाला एक अन्य महत्वपूर्ण सामान्य रूप है डीकंपोजेबल नेगेटिव नॉर्मल फॉर्म, या डीएनएफ(DNNF)है।
+अदनान डारविच और उनके सहयोगियों ने दिखाया है कि बीडीडी बूलियन कार्यों के लिए कई सामान्य रूपों में से एक है, प्रत्येक आवश्यकताओं के एक अलग संयोजन द्वारा संचालित है। डारविच द्वारा पहचाना जाने वाला एक अन्य महत्वपूर्ण सामान्य रूप है डीकंपोजेबल नेगेटिव नॉर्मल फॉर्म, या डीएनएफ (DNNF) है।
 == अनुप्रयोग ==
-सर्किट (तर्क संश्लेषण) को संश्लेषित करने और औपचारिक सत्यापन में बीडीडी का व्यापक रूप से सीएडी सॉफ्टवेयर में उपयोग किया जाता है। BDD में कई कम-ज्ञात अनुप्रयोग हैं, जिनमें फॉल्ट ट्री विश्लेषण, बायेसियन लॉजिक, उत्पाद विन्यास और निजी सूचना पुनर्प्राप्ति शामिल हैं।<ref name="Jensen"/><ref name="Lipmaa"/>{{Citation needed|reason=Please provide examples of these applications in the literature.|date=June 2010}}
+सर्किट (तर्क संश्लेषण) को संश्लेषित करने और औपचारिक सत्यापन में बीडीडी का व्यापक रूप से सीएडी सॉफ्टवेयर में उपयोग किया जाता है। बीडीडी में कई कम-ज्ञात अनुप्रयोग हैं, जिनमें फॉल्ट ट्री विश्लेषण, बायेसियन लॉजिक, उत्पाद विन्यास और निजी सूचना पुनर्प्राप्ति शामिल हैं।<ref name="Jensen"/><ref name="Lipmaa"/>{{Citation needed|reason=Please provide examples of these applications in the literature.|date=June 2010}}
-कोई भी मनमाना बीडीडी (भले ही इसे कम किया गया हो या ऑर्डर न किया गया हो) प्रत्येक नोड को 2 से 1 मल्टीप्लेक्सर से बदलकर सीधे हार्डवेयर में लागू किया जा सकता है; प्रत्येक बहुसंकेतक एक FPGA में 4-LUT द्वारा सीधे लागू किया जा सकता है। लॉजिक गेट्स के एक मनमाने नेटवर्क से BDD [उद्धरण वांछित] (AND-इन्वर्टर ग्राफ़ के विपरीत) में परिवर्तित करना इतना आसान नहीं है।
+कोई भी मनमाना बीडीडी (भले ही इसे कम किया गया हो या ऑर्डर न किया गया हो) प्रत्येक नोड को 2 से 1 मल्टीप्लेक्सर से बदलकर सीधे हार्डवेयर में लागू किया जा सकता है; प्रत्येक बहुसंकेतक एक FPGA में 4-LUT द्वारा सीधे लागू किया जा सकता है। लॉजिक गेट्स के एक मनमाने नेटवर्क से बीडीडी [उद्धरण वांछित] (AND-इन्वर्टर ग्राफ़ के विपरीत) में परिवर्तित करना इतना आसान नहीं है।
 == चर आदेश ==
-BDD का आकार फ़ंक्शन का प्रतिनिधित्व किया जा रहा है और चर के चुने हुए क्रम द्वारा निर्धारित किया जाता है।वहाँ बूलियन कार्य मौजूद हैं <math>f(x_1,\ldots, x_{n})</math> जिसके लिए चर के आदेश के आधार पर हम एक ग्राफ प्राप्त कर रहे हैं, जिसकी संख्या नोड्स की संख्या रैखिक होगी (सबसे अच्छा और सबसे अच्छा और घातीय रूप से सबसे खराब (जैसे, एक तरंग कैरी एडडर)।बूलियन फ़ंक्शन पर विचार करें <math>f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \cdots + x_{2n-1}x_{2n}.</math> चर आदेश का उपयोग करना <math>x_1 < x_3 < \cdots < x_{2n-1} < x_2 < x_4 < \cdots < x_{2n}</math>, BDD की जरूरत है <math>2^{n+1}</math> फ़ंक्शन का प्रतिनिधित्व करने के लिए नोड्स।आदेश का उपयोग करना <math>x_1 < x_2 < x_3 < x_4 < \cdots < x_{2n-1} < x_{2n}</math>, BDD में शामिल हैं <math>2n+2</math> नोड्स।
+बीडीडी का आकार प्रतिनिधित्व किए जा रहे फ़ंक्शन और चर के चुने हुए अनुक्रम द्वारा निर्धारित किया जाता है। बूलियन फ़ंक्शन मौजूद हैं <math>f(x_1,\ldots, x_{n})</math> जिसके लिए चर के आदेश के आधार पर हम एक ग्राफ प्राप्त कर रहे हैं, जिसकी संख्या नोड्स की संख्या रैखिक होगी (सबसे अच्छा और सबसे अच्छा और घातीय रूप से सबसे खराब (जैसे, एक तरंग कैरी एडडर)। बूलियन फ़ंक्शन पर विचार करें <math>f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \cdots + x_{2n-1}x_{2n}.</math> चर आदेश का उपयोग करना <math>x_1 < x_3 < \cdots < x_{2n-1} < x_2 < x_4 < \cdots < x_{2n}</math>, बीडीडी की जरूरत है <math>2^{n+1}</math> फ़ंक्शन का प्रतिनिधित्व करने के लिए नोड्स। आदेश का उपयोग करना <math>x_1 < x_2 < x_3 < x_4 < \cdots < x_{2n-1} < x_{2n}</math>, बीडीडी में शामिल हैं <math>2n+2</math> नोड्स।
 {| align="center"
 |-
-| [[File:BDD Variable Ordering Bad.svg|thumb|638px|BDD for the function ''ƒ''(''x''<sub>1</sub>, ..., ''x''<sub>8</sub>) = ''x''<sub>1</sub>''x''<sub>2</sub> + ''x''<sub>3</sub>''x''<sub>4</sub> + ''x''<sub>5</sub>''x''<sub>6</sub> + ''x''<sub>7</sub>''x''<sub>8</sub> using bad variable ordering]]
+| [[File:BDD Variable Ordering Bad.svg|thumb|638px|फ़ंक्शन के लिए बीडीडी ''ƒ''(''x''<sub>1</sub>, ..., ''x''<sub>8</sub>) = ''x''<sub>1</sub>''x''<sub>2</sub> + ''x''<sub>3</sub>''x''<sub>4</sub> + ''x''<sub>5</sub>''x''<sub>6</sub> + ''x''<sub>7</sub>''x''<sub>8</sub> खराब चर क्रम का उपयोग करना]]
-| [[File:BDD Variable Ordering Good.svg|thumb|156px|Good variable ordering]]
+| [[File:BDD Variable Ordering Good.svg|thumb|156px|अच्छा परिवर्तन क्रम]]
 |}
-व्यवहार में इस डेटा संरचना को लागू करते समय चर आदेश के बारे में देखभाल करना महत्वपूर्ण महत्व है।सबसे अच्छा चर आदेश खोजने की समस्या एनपी-हार्ड है।<ref name="Bollig"/>किसी भी निरंतर c & nbsp; & nbsp; 1 के लिए यह एक चर ऑर्डर की गणना करने के लिए एनपी-हार्ड भी है, जिसके परिणामस्वरूप एक आकार के साथ एक OBDD होता है जो कि एक इष्टतम से अधिक सी गुना अधिक होता है।<ref name="Sieling"/>हालांकि, समस्या से निपटने के लिए कुशल हेयूरिस्टिक्स मौजूद हैं।<ref name="Rice"/>
+इस डेटा संरचना को व्यवहार में लागू करते समय चर क्रम का ध्यान रखना महत्वपूर्ण है। सबसे अच्छा परिवर्तनीय अनुक्रम खोजने की समस्या एनपी-हार्ड है। <ref name="Bollig"/>किसी भी स्थिरांक c> 1 के लिए एक चर क्रम की गणना करना और भी अधिक एनपी-कठिन है, जिसके परिणामस्वरूप एक Oबीडीडी एक आकार के साथ होता है जो एक इष्टतम से अधिक से अधिक c गुना बड़ा होता है।<ref name="Sieling"/>हालांकि, समस्या से निपटने के लिए प्रभावी अनुमान मौजूद हैं।<ref name="Rice"/>
-ऐसे कार्य हैं जिनके लिए ग्राफ का आकार हमेशा घातीय होता है - चर आदेश के स्वतंत्र।यह उदा।गुणन फ़ंक्शन के लिए।<ref name="Bryant1986"/>वास्तव में, फ़ंक्शन दो के उत्पाद के मध्य बिट की गणना करता है <math>n</math>-बिट संख्याओं में एक obdd की तुलना में छोटा नहीं है <math>2^{\lfloor n/2 \rfloor} / 61 - 4</math> कोने।<ref name="Woelfel_2005"/>(यदि गुणन फ़ंक्शन में बहुपद-आकार के OBDDs थे, तो यह दिखाएगा कि पूर्णांक कारक p/poly में है, जो सच नहीं है।<ref name="Lipton_2009"/>
+ऐसे फ़ंक्शन हैं जिनके लिए ग्राफ़ का आकार हमेशा घातीय होता है-चर क्रम से स्वतंत्र। यह धारण उदा. गुणन फ़ंक्शन के लिए।<ref name="Bryant1986"/>वास्तव में, फ़ंक्शन दो के उत्पाद के मध्य बिट की गणना करता है <math>n</math>-बिट संख्याओं में एक Oबीडीडी की तुलना में छोटा नहीं है <math>2^{\lfloor n/2 \rfloor} / 61 - 4</math> कोने।<ref name="Woelfel_2005"/> (यदि गुणन फ़ंक्शन में बहुपद-आकार के ओबीडीडी थे, तो यह दिखाएगा कि पूर्णांक कारक पी/पाली (p/poly)) में है, जो सच नहीं है।<ref name="Lipton_2009"/>
-शोधकर्ताओं ने बीएमडी (बाइनरी मोमेंट आरेख), जेडडीडी (शून्य-दमनकारी निर्णय आरेख), एफडीडी (मुक्त द्विआधारी निर्णय आरेख), पीडीडी (समता निर्णय आरेख) जैसे कई संबंधित रेखांकन, जैसे कई संबंधित रेखांकन के लिए बीडीडी डेटा संरचना पर शोधन का सुझाव दिया है।, और MTBDDS (कई टर्मिनल BDDs)।
-== BDDS पर तार्किक संचालन ==
+शोधकर्ता बीडीडी डेटा संरचना पर एक शोधन का सुझाव देते हैं, जो बीएमडी (बाइनरी मोमेंट डायग्राम), जेडडीडी (जीरो-सप्रेस्ड डिसीजन डायग्राम), एफडीडी (फ्री बाइनरी डिसीजन डायग्राम), पीडीडी (पैरिटी डिसीजन डायग्राम) जैसे कई संबंधित ग्राफों को रास्ता देता है। ), और एमटीबीडीडी (MTBDDs) 0 (एकाधिक टर्मिनल बीडीडी)।
-BDDs पर कई तार्किक संचालन को बहुपद-समय ग्राफ हेरफेर एल्गोरिदम द्वारा लागू किया जा सकता है:<ref name="Andersen_1999"/>{{rp|20}}
+== बीडीडी पर तार्किक संचालन ==
+बीडीडी पर कई तार्किक संचालन बहुपद-समय ग्राफ हेरफेर एल्गोरिदम द्वारा कार्यान्वित किए जा सकते हैं <ref name="Andersen_1999"/>{{rp|20}}
 * संयोजक
 * असंतुष्ट
 * उपेक्षा
-हालांकि, इन कार्यों को कई बार दोहराते हुए, उदाहरण के लिए, BDDs के एक सेट के संयोजन या विघटन का निर्माण, सबसे खराब स्थिति में सबसे बड़े BDD के परिणामस्वरूप हो सकता है।इसका कारण यह है कि दो बीडीडी के लिए पूर्ववर्ती संचालन में से कोई भी बीडीडी के आकार के साथ बीडीडी के आकार के उत्पाद के लिए आनुपातिक हो सकता है, और परिणामस्वरूप कई बीडीडी के लिए आकार संचालन की संख्या में घातीय हो सकता है।परिवर्तनीय आदेश को दूर करने की आवश्यकता है;बीडीडी के सेट के लिए (कुछ) के लिए एक अच्छा आदेश क्या हो सकता है, ऑपरेशन के परिणाम के लिए एक अच्छा आदेश नहीं हो सकता है।इसके अलावा, एक बूलियन फ़ंक्शन के BDD का निर्माण करने से NP- पूर्ण बूलियन संतोषजनक समस्या और CO-NP- पूर्ण टॉटोलॉजी समस्या का समाधान होता है, BDD का निर्माण करने से बूलियन फॉर्मूला के आकार में घातीय समय लग सकता है, जिसके परिणामस्वरूप BDD छोटा होता है।
+हालांकि, इन संचालनों को कई बार दोहराते हुए, उदाहरण के लिए, बीडीडी या संयोजनों का एक समुच्चय बनाना, सबसे खराब स्थिति में तेजी से बड़ा बीडीडी हो सकता है। इसका कारण यह है कि दो बीडीडी के लिए किसी भी पिछले संचालन के परिणामस्वरूप बीडीडी के आकार के उत्पाद के आनुपातिक आकार के साथ बीडीडी हो सकता है, और इसके परिणामस्वरूप कई बीडीडी के लिए आकार संचालन की संख्या में घातीय हो सकता है। परिवर्तनीय क्रम को एक नए रूप की जरूरत है; बीडीडी के समुच्चय (इनमें से कुछ) के लिए एक अच्छा क्रम क्या हो सकता है, संचालन के परिणाम के लिए एक अच्छा क्रम नहीं हो सकता है। इसके अलावा, चूंकि बूलियन फ़ंक्शन के बीडीडी के निर्माण से एनपी-पूर्ण (NP-complete) बूलियन संतुष्टि समस्या और सह-एनपी-पूर्ण (co-NP-complete) पुनरुक्ति समस्या हल हो जाती है, बीडीडी के निर्माण में बूलियन फॉर्मूला के आकार के लिए घातीय समय लग सकता है, भले ही जिसके परिणामस्वरूप बीडीडी छोटा है। .
-कम BDDs के कई चर पर अस्तित्व संबंधी अमूर्तता की गणना एनपी-पूर्ण है।<ref name="Huth"/>
+कम बीडीडी के कई चर पर अस्तित्व संबंधी अमूर्तता की गणना एनपी-पूर्ण है (NP-complete)।<ref name="Huth"/>
-मॉडल-गिनती, एक बूलियन फॉर्मूला के संतोषजनक असाइनमेंट की संख्या की गिनती, बीडीडी के लिए बहुपद समय में किया जा सकता है।सामान्य प्रस्ताव के सूत्रों के लिए समस्या isp-c-पूर्ण है और सबसे अच्छे ज्ञात एल्गोरिदम को सबसे खराब स्थिति में एक घातीय समय की आवश्यकता होती है।
+मॉडल-गिनती, एक बूलियन सूत्र को संतुष्ट करने वाले असाइनमेंट की संख्या की गणना, बीडीडी के लिए बहुपद समय में की जा सकती है। सामान्य प्रस्ताव संबंधी सूत्रों के लिए, समस्या पी-पूर्ण है और सबसे अच्छी तरह से ज्ञात कलन विधि को सबसे खराब स्थिति में घातीय समय की आवश्यकता होती है।
 == यह भी देखें ==
-* बूलियन संतोषजनक समस्या, कैनोनिकल एनपी-पूर्ण कम्प्यूटेशनल समस्या
+* बूलियन संतुष्टि समस्या, विहित एनपी-पूर्ण कम्प्यूटेशनल समस्या
-* एल/पॉली, एक जटिलता वर्ग जिसमें सख्ती से बहुपद आकार के बीडीडी के साथ समस्याओं का सेट होता है{{Citation needed|date=February 2020}}
+*एल/पॉली, एक जटिलता वर्ग जिसमें बहुपद आकार के बीडीडी के साथ समस्याओं का समुच्चय सख्ती से शामिल है{{Citation needed|date=February 2020}}
 * मॉडल जाँच
 * रेडिक्स ट्री
-* नेकां (जटिलता)#बैरिंगटन का प्रमेय | बैरिंगटन का प्रमेय
+* बैरिंगटन की प्रमेय
 * हार्डवेयर एक्सिलरेशन
-* कर्णघ मैप, बूलियन बीजगणित अभिव्यक्तियों को सरल बनाने की एक विधि
+* कर्णघ मानचित्र, बूलियन बीजगणित के भावों को सरल बनाने की एक विधि
+*शून्य दबाया निर्णय आरेख
 == संदर्भ ==
@@ Line 111: / Line 112: @@
 * R. Ubar, "Test Generation for Digital Circuits Using Alternative Graphs (in Russian)", in Proc. Tallinn Technical University, 1976, No. 409, Tallinn Technical University, Tallinn, Estonia, pp.&nbsp;75–81.
 * D. E. Knuth, "[[The Art of Computer Programming]] Volume 4, Fascicle 1: Bitwise tricks & techniques; Binary Decision Diagrams" (Addison–Wesley Professional, March 27, 2009) viii+260pp, {{ISBN|0-321-58050-8}}. [http://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz Draft of Fascicle 1b] available for download.
-* Ch. Meinel, T. Theobald, "[http://www.hpi.uni-potsdam.de/fileadmin/hpi/FG_ITS/books/OBDD-Book.pdf Algorithms and Data Structures in VLSI-Design: OBDD – Foundations and Applications"], Springer-Verlag, Berlin, Heidelberg, New York, 1998. Complete textbook available for download.
+* Ch. Meinel, T. Theobald, "[http://www.hpi.uni-potsdam.de/fileadmin/hpi/FG_ITS/books/OBDD-Book.pdf Algorithms and Data Structures in VLSI-Design: Oबीडीडी – Foundations and Applications"], Springer-Verlag, Berlin, Heidelberg, New York, 1998. Complete textbook available for download.
 * {{cite book |author-first1=Rüdiger |author-last1=Ebendt |author-first2=Görschwin |author-last2=Fey |author-first3=Rolf |author-last3=Drechsler |title=Advanced BDD optimization |date=2005 |publisher=Springer |isbn=978-0-387-25453-1}}
 * {{cite book |author-first1=Bernd |author-last1=Becker |author-first2=Rolf |author-last2=Drechsler |title=Binary Decision Diagrams: Theory and Implementation |date=1998 |publisher=Springer |isbn=978-1-4419-5047-5}}
@@ Line 119: / Line 120: @@
 {{Commons category|Binary decision diagrams}}
 * [https://www.youtube.com/watch?v=SQE21efsf7Y Fun With Binary Decision Diagrams (BDDs)], lecture by [[Donald Knuth]]
-* [https://github.com/johnyf/tool_lists/blob/master/bdd.md List of BDD software libraries] for several programming languages.
+* [https://github.com/johnyf/tool_lists/blob/master/bdd.md List of बीडीडी software libraries] for several programming languages.
 {{Data structures}}
@@ Line 125: / Line 126: @@
 {{DEFAULTSORT:Binary Decision Diagram}}
+[[Category:AC with 0 elements|Binary Decision Diagram]]
+[[Category:All articles with unsourced statements|Binary Decision Diagram]]
+[[Category:Articles with invalid date parameter in template|Binary Decision Diagram]]
+[[Category:Articles with unsourced statements from February 2020|Binary Decision Diagram]]
+[[Category:Articles with unsourced statements from June 2010|Binary Decision Diagram]]
+[[Category:CS1 maint|Binary Decision Diagram]]
+[[Category:Collapse templates|Binary Decision Diagram]]
+[[Category:Commons category link is locally defined|Binary Decision Diagram]]
+[[Category:Exclude in print|Binary Decision Diagram]]
+[[Category:Interwiki category linking templates|Binary Decision Diagram]]
+[[Category:Interwiki link templates|Binary Decision Diagram]]
+[[Category:Machine Translated Page|Binary Decision Diagram]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Binary Decision Diagram]]
+[[Category:Pages with reference errors|Binary Decision Diagram]]
+[[Category:Pages with script errors|Binary Decision Diagram]]
+[[Category:Sidebars with styles needing conversion|Binary Decision Diagram]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Binary Decision Diagram]]
+[[Category:Templates generating microformats|Binary Decision Diagram]]
+[[Category:Templates that add a tracking category|Binary Decision Diagram]]
+[[Category:Templates that are not mobile friendly|Binary Decision Diagram]]
+[[Category:Templates used by AutoWikiBrowser|Cite web]]
+[[Category:Templates using TemplateData|Binary Decision Diagram]]
+[[Category:Wikimedia Commons templates|Binary Decision Diagram]]
+[[Category:Wikipedia metatemplates|Binary Decision Diagram]]

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

बाइनरी निर्णय आरेख: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:51, 4 September 2023

Contents

परिभाषा

उदाहरण

पूरक किनारे

इतिहास

अनुप्रयोग

चर आदेश

बीडीडी पर तार्किक संचालन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बाइनरी निर्णय आरेख: Difference between revisions

Latest revision as of 10:51, 4 September 2023

परिभाषा

उदाहरण

पूरक किनारे

इतिहास

अनुप्रयोग

चर आदेश

बीडीडी पर तार्किक संचालन

यह भी देखें

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories