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

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Technical|date=June 2022}}
{{Technical|date=June 2022}}


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


Line 9: Line 9:


प्रतिनिधित्व की प्रामाणिकता सुनिश्चित करने वाले नियम हैं:
प्रतिनिधित्व की प्रामाणिकता सुनिश्चित करने वाले नियम हैं:
* क्रम में उच्च चर पर निर्णय केवल क्रम में कम चर पर निर्णय की ओर इशारा कर सकता है।
* क्रम में उच्चतर चर पर निर्णय केवल क्रम में नीचे वाले चर पर निर्णय की ओर इशारा कर सकता है।
* कोई भी दो नोड समान नहीं हो सकते हैं (सामान्यीकरण में ऐसे नोड्स में से किसी एक नोड के सभी संदर्भों को दूसरे के संदर्भ में प्रतिस्थापित किया जाना चाहिए)
* कोई भी दो नोड समान नहीं हो सकते हैं (सामान्यीकरण में ऐसे नोड्स में से किसी एक नोड के सभी संदर्भों को दूसरे के संदर्भ में प्रतिस्थापित किया जाना चाहिए)
* किसी भी नोड में सभी निर्णय भाग 0 के समतुल्य नहीं हो सकते हैं (ऐसे नोड्स के लिंक को उनके हमेशा भाग के लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
* किसी भी नोड में सभी निर्णय भाग 0 के समतुल्य नहीं हो सकते हैं (ऐसे नोड्स के लिंक को उनके हमेशा भाग के लिंक द्वारा प्रतिस्थापित किया जाना चाहिए)
Line 48: Line 48:
== एज वेट ==
== एज वेट ==


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


उदाहरण के लिए, <math>(4x_2 + 2x_1 + x_0) (4y_2 + 2y_1 + y_0)</math> के रूप में प्रतिनिधित्व किया जा सकता है:
उदाहरण के लिए, <math>(4x_2 + 2x_1 + x_0) (4y_2 + 2y_1 + y_0)</math> के रूप में प्रतिनिधित्व किया जा सकता है:

Revision as of 17:42, 29 June 2023

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

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

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

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

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

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

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

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

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

एज वेट

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

उदाहरण के लिए, के रूप में प्रतिनिधित्व किया जा सकता है:

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

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

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

संदर्भ

  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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बाइनरी_मोमेंट_डायग्राम&oldid=207918’