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

Latest revision as of 11:57, 15 September 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 6: / Line 6: @@
 बीएमडी का सबसे महत्वपूर्ण गुण यह है कि, बीडीडी की तरह, प्रत्येक फ़ंक्शन में बिल्कुल एक विहित प्रतिनिधित्व होता है, और इन अभ्यावेदन पर कई ऑपरेशन कुशलता से किए जा सकते हैं।
-बीएमडी को बीडीडी से अलग करने वाली मुख्य विशेषताएं बिंदुवार आरेखों के बजाय रैखिक का उपयोग करना और भारित किनारों का होना है।
+बीएमडी को बीडीडी से अलग करने वाली मुख्य विशेषताएं बिंदुवार आरेखों के अतिरिक्त रैखिक का उपयोग करना और भारित किनारों का होना है।
 प्रतिनिधित्व की प्रामाणिकता सुनिश्चित करने वाले नियम हैं:
 * क्रम में उच्चतर चर पर निर्णय केवल क्रम में नीचे वाले चर पर निर्णय की ओर इशारा कर सकता है।
 * कोई भी दो नोड समान नहीं हो सकते हैं (सामान्यीकरण में ऐसे नोड्स में से किसी एक नोड के सभी संदर्भों को दूसरे के संदर्भ में प्रतिस्थापित किया जाना चाहिए)
-* किसी भी नोड में सभी निर्णय भाग 0 के समतुल्य नहीं हो सकते हैं (ऐसे नोड्स के लिंक को उनके हमेशा भाग के लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
+* किसी भी नोड में सभी निर्णय भाग 0 के समतुल्य नहीं हो सकते हैं (ऐसे नोड्स के लिंक को उनके सदैव भाग के लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
 * किसी भी किनारे का भार शून्य नहीं हो सकता है (ऐसे सभी किनारों को 0 के सीधे लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
 * किनारों का वजन [[सह अभाज्य]] होना चाहिए। इस नियम या इसके समकक्ष के बिना, एक फ़ंक्शन के लिए कई प्रतिनिधित्व करना संभव होगा, उदाहरण के लिए 2x + 2 को 2·· (1 + x) या 1 · (2 + 2x) के रूप में दर्शाया जा सकता है।
@@ 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× मान जोड़ें
+# परिणाम नोड, सदैव 1 × नोड 2 का मान, यदि <math>x_2</math> नोड 4 का 4× मान जोड़ें
-# नोड 3 का हमेशा 1× मान, यदि <math>x_1</math> नोड 4 का 2× मान जोड़ें
+# नोड 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× नोड 5 का मान, यदि <math>y_2</math> +4 जोड़ें
-# हमेशा 1 × नोड 6 का मान, यदि <math>y_1</math> +2 जोड़ें
+# सदैव 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 का मान
+# परिणाम नोड, सदैव नोड 2 का मान, यदि <math>x_2</math> नोड 4 का मान
-# हमेशा नोड 3 का मान, यदि <math>x_1</math> नोड 7 का मान
+# सदैव नोड 3 का मान, यदि <math>x_1</math> नोड 7 का मान
-# हमेशा 0, यदि <math>x_0</math> नोड 10 का मान
+# सदैव 0, यदि <math>x_0</math> नोड 10 का मान
-# हमेशा नोड 5 का मान, यदि <math>y_2</math> +16 जोड़ें
+# सदैव नोड 5 का मान, यदि <math>y_2</math> +16 जोड़ें
-# हमेशा नोड 6 का मान, यदि <math>y_1</math> +8 जोड़ें
+# सदैव नोड 6 का मान, यदि <math>y_1</math> +8 जोड़ें
-# हमेशा 0, यदि <math>y_0</math> +4 जोड़ें
+# सदैव 0, यदि <math>y_0</math> +4 जोड़ें
-# हमेशा नोड 8 का मान, यदि <math>y_2</math> +8 जोड़ें
+# सदैव नोड 8 का मान, यदि <math>y_2</math> +8 जोड़ें
-# हमेशा नोड 9 का मान, यदि <math>y_1</math> +4 जोड़ें
+# सदैव नोड 9 का मान, यदि <math>y_1</math> +4 जोड़ें
-# हमेशा 0, यदि <math>y_0</math> +2 जोड़ें
+# सदैव 0, यदि <math>y_0</math> +2 जोड़ें
-# हमेशा नोड 11 का मान, यदि <math>y_2</math> +4 जोड़ें
+# सदैव नोड 11 का मान, यदि <math>y_2</math> +4 जोड़ें
-# हमेशा नोड 12 का मान, यदि <math>y_1</math> +2 जोड़ें
+# सदैव नोड 12 का मान, यदि <math>y_1</math> +2 जोड़ें
-# हमेशा 0, यदि <math>y_0</math> +1 जोड़ें
+# सदैव 0, यदि <math>y_0</math> +1 जोड़ें
 ==संदर्भ==
 {{Reflist}}
-[[Category: ग्राफ डेटा संरचनाएं]] [[Category: औपचारिक तरीके]]
+[[Category:All articles that are too technical]]
+[[Category:Articles with invalid date parameter in template]]
-[[Category: Machine Translated Page]]
+[[Category:CS1]]
 [[Category:Created On 19/06/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Wikipedia articles that are too technical from June 2022]]
+[[Category:औपचारिक तरीके]]
+[[Category:ग्राफ डेटा संरचनाएं]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 11:57, 15 September 2023

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

एज वेट

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 11:57, 15 September 2023

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

एज वेट

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories