बाइनरी मोमेंट डायग्राम: Difference between revisions

Revision as of 17:26, 29 June 2023

एक बाइनरी पल आरेख (बीएमडी) बाइनरी निर्णय आरेख (बीडीडी) का एक सामान्यीकरण है जो बूलियन (जैसे बीडीडी) जैसे डोमेन पर रैखिक कार्यों के लिए होता है, लेकिन पूर्णांक या वास्तविक संख्याओं के लिए भी।^[1]^[2] वे बीडीडी की तुलना में जटिलता के साथ बूलियन समारोह से निपट सकते हैं, लेकिन बीडीडी में बहुत ही अक्षमता से निपटाए जाने वाले कुछ कार्यों को बीएमडी द्वारा आसानी से नियंत्रित किया जाता है, विशेष रूप से गुणन।

बीएमडी का सबसे महत्वपूर्ण गुण यह है कि, बीडीडी की तरह, प्रत्येक फ़ंक्शन में बिल्कुल एक विहित प्रतिनिधित्व होता है, और इन अभ्यावेदन पर कई ऑपरेशन कुशलता से किए जा सकते हैं।

बीडीडी से बीएमडी को अलग करने वाली मुख्य विशेषताएं बिंदुवार आरेखों के अतिरिक्त रैखिक का उपयोग कर रही हैं, और भारित किनारों वाले हैं।

प्रतिनिधित्व की प्रामाणिकता सुनिश्चित करने वाले नियम हैं:

क्रम में उच्च चर पर निर्णय केवल क्रम में कम चर पर निर्णय की ओर इशारा कर सकता है।
कोई भी दो नोड समान नहीं हो सकते हैं (सामान्यीकरण में ऐसे नोड्स में से किसी एक नोड के सभी संदर्भों को दूसरे के संदर्भ में प्रतिस्थापित किया जाना चाहिए)
किसी भी नोड में सभी निर्णय भाग 0 के समतुल्य नहीं हो सकते हैं (ऐसे नोड्स के लिंक को उनके हमेशा भाग के लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
किसी भी किनारे का भार शून्य नहीं हो सकता है (ऐसे सभी किनारों को 0 के सीधे लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
किनारों का वजन सह अभाज्य होना चाहिए। इस नियम या इसके समकक्ष के बिना, एक फ़ंक्शन के लिए कई प्रतिनिधित्व करना संभव होगा, उदाहरण के लिए 2x + 2 को 2·· (1 + x) या 1 · (2 + 2x) के रूप में दर्शाया जा सकता है।

बिंदुवार और रैखिक अपघटन

बिंदुवार अपघटन में, बीडीडी की तरह, प्रत्येक शाखा बिंदु पर हम सभी शाखाओं के परिणाम अलग-अलग संग्रहीत करते हैं। पूर्णांक फ़ंक्शन (2x + y) के लिए ऐसे अपघटन का एक उदाहरण है:

{\begin{cases}{\text{if }}x{\begin{cases}{\text{if }}y,3\\{\text{if }}\neg y,2\end{cases}}\\{\text{if }}\neg x{\begin{cases}{\text{if }}y{\text{ , }}1\\{\text{if }}\neg y{\text{ , }}0\end{cases}}\end{cases}}

रैखिक अपघटन में हम इसके अतिरिक्त एक डिफ़ॉल्ट मान और एक अंतर प्रदान करते हैं:

{\begin{cases}{\text{always}}{\begin{cases}{\text{always }}0\\{\text{if }}y,+1\end{cases}}\\{\text{if }}x,+2\end{cases}}

यह आसानी से देखा जा सकता है कि योगात्मक कार्यों के मामले में बाद वाला (रैखिक) प्रतिनिधित्व बहुत अधिक कुशल है, क्योंकि जब हम कई तत्वों को जोड़ते हैं तो बाद वाले प्रतिनिधित्व में केवल O(n) तत्व होंगे, जबकि पूर्व (बिंदुवार), साझा करने के साथ भी , घातीय रूप से कई।

एज वेट

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

उदाहरण के लिए, $(4x_{2}+2x_{1}+x_{0})(4y_{2}+2y_{1}+y_{0})$ के रूप में प्रतिनिधित्व किया जा सकता है:

परिणाम नोड, हमेशा 1 × नोड 2 का मान, यदि $x_{2}$ नोड 4 का 4× मान जोड़ें
नोड 3 का हमेशा 1× मान, यदि $x_{1}$ नोड 4 का 2× मान जोड़ें
हमेशा 0, यदि $x_{0}$ नोड 4 का 1× मान जोड़ें
हमेशा 1× नोड 5 का मान, यदि $y_{2}$ +4 जोड़ें
हमेशा 1 × नोड 6 का मान, यदि $y_{1}$ +2 जोड़ें
हमेशा 0, यदि $y_{0}$ +1 जोड़ें

भारित नोड्स के बिना अधिक जटिल प्रतिनिधित्व की आवश्यकता होगी:

परिणाम नोड, हमेशा नोड 2 का मान, यदि $x_{2}$ नोड 4 का मान
हमेशा नोड 3 का मान, यदि $x_{1}$ नोड 7 का मान
हमेशा 0, यदि $x_{0}$ नोड 10 का मान
हमेशा नोड 5 का मान, यदि $y_{2}$ +16 जोड़ें
हमेशा नोड 6 का मान, यदि $y_{1}$ +8 जोड़ें
हमेशा 0, यदि $y_{0}$ +4 जोड़ें
हमेशा नोड 8 का मान, यदि $y_{2}$ +8 जोड़ें
हमेशा नोड 9 का मान, यदि $y_{1}$ +4 जोड़ें
हमेशा 0, यदि $y_{0}$ +2 जोड़ें
हमेशा नोड 11 का मान, यदि $y_{2}$ +4 जोड़ें
हमेशा नोड 12 का मान, यदि $y_{1}$ +2 जोड़ें
हमेशा 0, यदि $y_{0}$ +1 जोड़ें

संदर्भ

↑ Nakanishi, Masaki; Hamaguchi, Kiyoharu; Kashiwabara, Toshinobu (1999-05-25). "पूर्णांक विभाजन का प्रतिनिधित्व करने वाले बाइनरी मोमेंट आरेख के आकार पर एक घातीय निचला बाउंड". IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences. E82-A (5): 756–766. ISSN 0916-8508.
↑ Sasao, T.; Nagayama, S. (May 2006). "बाइनरी मोमेंट डायग्राम का उपयोग करते हुए प्राथमिक कार्यों का प्रतिनिधित्व". 36th International Symposium on Multiple-Valued Logic (ISMVL'06): 28. doi:10.1109/ISMVL.2006.37. ISBN 0-7695-2532-6. S2CID 11622605.

[1] Nakanishi, Masaki; Hamaguchi, Kiyoharu; Kashiwabara, Toshinobu (1999-05-25). "पूर्णांक विभाजन का प्रतिनिधित्व करने वाले बाइनरी मोमेंट आरेख के आकार पर एक घातीय निचला बाउंड". IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences. E82-A (5): 756–766. ISSN 0916-8508.

[2] Sasao, T.; Nagayama, S. (May 2006). "बाइनरी मोमेंट डायग्राम का उपयोग करते हुए प्राथमिक कार्यों का प्रतिनिधित्व". 36th International Symposium on Multiple-Valued Logic (ISMVL'06): 28. doi:10.1109/ISMVL.2006.37. ISBN 0-7695-2532-6. S2CID 11622605.

[1]

[2]

@@ Line 2: / Line 2: @@
 एक बाइनरी पल आरेख (बीएमडी) बाइनरी निर्णय आरेख (बीडीडी) का एक सामान्यीकरण है जो बूलियन (जैसे बीडीडी) जैसे डोमेन पर रैखिक कार्यों के लिए होता है, लेकिन पूर्णांक या वास्तविक संख्याओं के लिए भी।<ref>{{Cite journal |last1=Nakanishi |first1=Masaki |last2=Hamaguchi |first2=Kiyoharu |last3=Kashiwabara |first3=Toshinobu |date=1999-05-25 |title=पूर्णांक विभाजन का प्रतिनिधित्व करने वाले बाइनरी मोमेंट आरेख के आकार पर एक घातीय निचला बाउंड|url=https://search.ieice.org/bin/summary.php?id=e82-a_5_756&category=A&year=1999&lang=E&abst= |journal=IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences |volume=E82-A |issue=5 |pages=756–766 |issn=0916-8508}}</ref><ref>{{Cite journal |last1=Sasao |first1=T. |last2=Nagayama |first2=S. |date=May 2006 |title=बाइनरी मोमेंट डायग्राम का उपयोग करते हुए प्राथमिक कार्यों का प्रतिनिधित्व|url=https://ieeexplore.ieee.org/document/1623980 |journal=36th International Symposium on Multiple-Valued Logic (ISMVL'06) |pages=28 |doi=10.1109/ISMVL.2006.37|isbn=0-7695-2532-6 |s2cid=11622605 }}</ref>
-वे BDDs की तुलना में जटिलता के साथ [[बूलियन समारोह]] से निपट सकते हैं, लेकिन BDD में बहुत ही अक्षमता से निपटाए जाने वाले कुछ कार्यों को BMD द्वारा आसानी से नियंत्रित किया जाता है, विशेष रूप से गुणन।
+वे बीडीडी की तुलना में जटिलता के साथ [[बूलियन समारोह]] से निपट सकते हैं, लेकिन बीडीडी में बहुत ही अक्षमता से निपटाए जाने वाले कुछ कार्यों को बीएमडी द्वारा आसानी से नियंत्रित किया जाता है, विशेष रूप से गुणन।
-BMD का सबसे महत्वपूर्ण गुण यह है कि, BDDs की तरह, प्रत्येक फ़ंक्शन में बिल्कुल एक विहित प्रतिनिधित्व होता है, और इन अभ्यावेदन पर कई ऑपरेशन कुशलता से किए जा सकते हैं।
+बीएमडी का सबसे महत्वपूर्ण गुण यह है कि, बीडीडी की तरह, प्रत्येक फ़ंक्शन में बिल्कुल एक विहित प्रतिनिधित्व होता है, और इन अभ्यावेदन पर कई ऑपरेशन कुशलता से किए जा सकते हैं।
-बीडीडी से बीएमडी को अलग करने वाली मुख्य विशेषताएं बिंदुवार आरेखों के बजाय रैखिक का उपयोग कर रही हैं, और भारित किनारों वाले हैं।
+बीडीडी से बीएमडी को अलग करने वाली मुख्य विशेषताएं बिंदुवार आरेखों के अतिरिक्त रैखिक का उपयोग कर रही हैं, और भारित किनारों वाले हैं।
 प्रतिनिधित्व की प्रामाणिकता सुनिश्चित करने वाले नियम हैं:
@@ Line 33: / Line 33: @@
 \end{cases}
 \end{cases}</math>
-रैखिक अपघटन में हम इसके बजाय एक डिफ़ॉल्ट मान और एक अंतर प्रदान करते हैं:
+रैखिक अपघटन में हम इसके  अतिरिक्त एक डिफ़ॉल्ट मान और एक अंतर प्रदान करते हैं:
 :<math>\begin{cases}
@@ Line 48: / Line 48: @@
 == एज वेट ==
-एक अन्य एक्सटेंशन किनारों के लिए वज़न का उपयोग कर रहा है। दिए गए नोड पर फ़ंक्शन का मान इसके नीचे सही नोड्स का योग है (नोड हमेशा के तहत, और संभवतः तय नोड) किनारों के वजन के गुणा।
+एक अन्य एक्सटेंशन किनारों के लिए वज़न का उपयोग कर रहा है। दिए गए नोड पर फ़ंक्शन का मान इसके नीचे सही नोड्स का योग है (नोड हमेशा के अनुसार, और संभवतः तय नोड) किनारों के वजन के गुणा।
 उदाहरण के लिए, <math>(4x_2 + 2x_1 + x_0) (4y_2 + 2y_1 + y_0)</math> के रूप में प्रतिनिधित्व किया जा सकता है:
 # परिणाम नोड, हमेशा 1 × नोड 2 का मान, यदि <math>x_2</math> नोड 4 का 4× मान जोड़ें
 # नोड 3 का हमेशा 1× मान, यदि <math>x_1</math> नोड 4 का 2× मान जोड़ें
-# हमेशा 0, अगर <math>x_0</math> नोड 4 का 1× मान जोड़ें
+# हमेशा 0, यदि <math>x_0</math> नोड 4 का 1× मान जोड़ें
 # हमेशा 1× नोड 5 का मान, यदि <math>y_2</math> +4 जोड़ें
 # हमेशा 1 × नोड 6 का मान, यदि <math>y_1</math> +2 जोड़ें
-# हमेशा 0, अगर <math>y_0</math> +1 जोड़ें
+# हमेशा 0, यदि <math>y_0</math> +1 जोड़ें
 भारित नोड्स के बिना अधिक जटिल प्रतिनिधित्व की आवश्यकता होगी:
 # परिणाम नोड, हमेशा नोड 2 का मान, यदि <math>x_2</math> नोड 4 का मान
 # हमेशा नोड 3 का मान, यदि <math>x_1</math> नोड 7 का मान
-# हमेशा 0, अगर <math>x_0</math> नोड 10 का मान
+# हमेशा 0, यदि <math>x_0</math> नोड 10 का मान
 # हमेशा नोड 5 का मान, यदि <math>y_2</math> +16 जोड़ें
 # हमेशा नोड 6 का मान, यदि <math>y_1</math> +8 जोड़ें
-# हमेशा 0, अगर <math>y_0</math> +4 जोड़ें
+# हमेशा 0, यदि <math>y_0</math> +4 जोड़ें
 # हमेशा नोड 8 का मान, यदि <math>y_2</math> +8 जोड़ें
 # हमेशा नोड 9 का मान, यदि <math>y_1</math> +4 जोड़ें
-# हमेशा 0, अगर <math>y_0</math> +2 जोड़ें
+# हमेशा 0, यदि <math>y_0</math> +2 जोड़ें
 # हमेशा नोड 11 का मान, यदि <math>y_2</math> +4 जोड़ें
 # हमेशा नोड 12 का मान, यदि <math>y_1</math> +2 जोड़ें
-# हमेशा 0, अगर <math>y_0</math> +1 जोड़ें
+# हमेशा 0, यदि <math>y_0</math> +1 जोड़ें
 ==संदर्भ==

Anonymous

Search

बाइनरी मोमेंट डायग्राम: Difference between revisions

Namespaces

More

Page actions

Revision as of 17:26, 29 June 2023

बिंदुवार और रैखिक अपघटन

एज वेट

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बाइनरी मोमेंट डायग्राम: Difference between revisions

Revision as of 17:26, 29 June 2023

बिंदुवार और रैखिक अपघटन

एज वेट

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories