बीजगणितीय निर्णय आरेख: Difference between revisions
No edit summary |
No edit summary |
||
| Line 5: | Line 5: | ||
== परिभाषा == | == परिभाषा == | ||
ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है <math>\{0,1\}^n</math> स्थिरांक S, या [[बीजगणितीय संरचना]] के वाहक के परिमित समुच्चय के लिए है। ADD एक रूटेड, निर्देशित, चक्रीय ग्राफ है, जिसमें BDD की तरह कई | ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है <math>\{0,1\}^n</math> स्थिरांक S, या [[बीजगणितीय संरचना]] के वाहक के परिमित समुच्चय के लिए है। ADD एक रूटेड, निर्देशित, चक्रीय ग्राफ है, जिसमें BDD की तरह कई बिंदु होते हैं। चूंकि, ADD में दो से अधिक सीमान्त बिंदु हो सकते हैं जो BDD के विपरीत सेट S के तत्व हैं। | ||
एक ADD को फ़ंक्शन के कोडोमेन को विस्तारित करके बूलियन फ़ंक्शन या [[वेक्टर बूलियन फ़ंक्शन]] के रूप में भी देखा जा सकता है, जैसे कि <math>f: \{0,1\}^n \to Q </math> के साथ <math>S \subseteq Q</math> और <math>card(Q) = 2^n</math> कुछ पूर्णांक n के लिए इसलिए, [[बूलियन बीजगणित]] के प्रमेय ADD पर लागू होते हैं, विशेष रूप से बूल के विस्तार प्रमेय पर लागू होते हैं।<ref name=":1" /> | एक ADD को फ़ंक्शन के कोडोमेन को विस्तारित करके बूलियन फ़ंक्शन या [[वेक्टर बूलियन फ़ंक्शन]] के रूप में भी देखा जा सकता है, जैसे कि <math>f: \{0,1\}^n \to Q </math> के साथ <math>S \subseteq Q</math> और <math>card(Q) = 2^n</math> कुछ पूर्णांक n के लिए इसलिए, [[बूलियन बीजगणित]] के प्रमेय ADD पर लागू होते हैं, विशेष रूप से बूल के विस्तार प्रमेय पर लागू होते हैं।<ref name=":1" /> | ||
प्रत्येक | प्रत्येक बिंदु को एक बूलियन चर द्वारा वर्गीकरण किया जाता है और इसके दो आउटगोइंग किनारे होते हैं: 1-किनारे जो कि मान ट्रू के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए फॉल्स का प्रतिनिधित्व करता है। | ||
ADD, BDD (या कम किए गए ऑर्डर वाले [[Index.php?title=BDD|BDD]]) के समान | ADD, BDD (या कम किए गए ऑर्डर वाले [[Index.php?title=BDD|BDD]]) के समान निगमन नियमों को नियोजित करता है: | ||
* किसी भी [[Index.php?title= | * किसी भी [[Index.php?title=Index.php?title= समरूपी|समरूपी]] सबग्राफ को मर्ज करें, और | ||
* ऐसे किसी भी | * ऐसे किसी भी बिंदु को हटा दें जो समरूपी हों। | ||
ADD एक विशेष चर क्रम के अनुसार विहित होते हैं। | ADD एक विशेष चर क्रम के अनुसार विहित होते हैं। | ||
| Line 23: | Line 23: | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
ADDs को सबसे पहले विरल [[मैट्रिक्स गुणन]] और सबसे छोटे पथ एल्गोरिदम | ADDs को सबसे पहले विरल [[मैट्रिक्स गुणन]] और सबसे छोटे पथ एल्गोरिदम के लिए प्रयुक्त किया गया था।<ref name=":1" /> | ||
Revision as of 14:08, 29 June 2023
एक बीजगणितीय निर्णय आरेख (ADD) या एक बहु-सीमान्त बाइनरी डिसीजन डायग्राम, एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है बाइनरी डिसीजन डायग्राम, या साहित्य में सामान्यतः बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो सीमान्त बिंदु बूलियन वैल्यू 0 (फॉल्स) और 1 (ट्रू) तक सीमित नहीं हैं।[1][2] सीमान्त बिंदु स्थिरांक S के सेट से कोई भी मान ले सकता है।
परिभाषा
ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है स्थिरांक S, या बीजगणितीय संरचना के वाहक के परिमित समुच्चय के लिए है। ADD एक रूटेड, निर्देशित, चक्रीय ग्राफ है, जिसमें BDD की तरह कई बिंदु होते हैं। चूंकि, ADD में दो से अधिक सीमान्त बिंदु हो सकते हैं जो BDD के विपरीत सेट S के तत्व हैं।
एक ADD को फ़ंक्शन के कोडोमेन को विस्तारित करके बूलियन फ़ंक्शन या वेक्टर बूलियन फ़ंक्शन के रूप में भी देखा जा सकता है, जैसे कि के साथ और कुछ पूर्णांक n के लिए इसलिए, बूलियन बीजगणित के प्रमेय ADD पर लागू होते हैं, विशेष रूप से बूल के विस्तार प्रमेय पर लागू होते हैं।[1]
प्रत्येक बिंदु को एक बूलियन चर द्वारा वर्गीकरण किया जाता है और इसके दो आउटगोइंग किनारे होते हैं: 1-किनारे जो कि मान ट्रू के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए फॉल्स का प्रतिनिधित्व करता है।
ADD, BDD (या कम किए गए ऑर्डर वाले BDD) के समान निगमन नियमों को नियोजित करता है:
- किसी भी समरूपी सबग्राफ को मर्ज करें, और
- ऐसे किसी भी बिंदु को हटा दें जो समरूपी हों।
ADD एक विशेष चर क्रम के अनुसार विहित होते हैं।
मैट्रिक्स विभाजन
एक ADD को उसके सहकारकों के अनुसार एक मैट्रिक्स द्वारा दर्शाया जा सकता है।[2][1]
अनुप्रयोग
ADDs को सबसे पहले विरल मैट्रिक्स गुणन और सबसे छोटे पथ एल्गोरिदम के लिए प्रयुक्त किया गया था।[1]
यह भी देखें
- बाइनरी डिसीजन डायग्राम
- ज़ीरो-सुप्प्रेस्सेड डिसीजन डायग्राम
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Bahar, R.I.; Frohm, E.A.; Gaona, C.M.; Hachtel, G.D.; Macii, E.; Pardo, A.; Somenzi, F. (1993). "बीजगणितीय निर्णय आरेख और उनके अनुप्रयोग". Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) (in English). IEEE Comput. Soc. Press: 188–191. doi:10.1109/iccad.1993.580054. ISBN 0-8186-4490-7. S2CID 43177472.
- ↑ 2.0 2.1 Fujita, M.; McGeer, P.C.; Yang, J.C.-Y. (1997-04-01). "Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation". Formal Methods in System Design (in English). 10 (2): 149–169. doi:10.1023/A:1008647823331. ISSN 1572-8102. S2CID 30494217.
