बीजगणितीय निर्णय आरेख: Difference between revisions

Latest revision as of 07:54, 15 July 2023

एक बीजगणितीय निर्णय आरेख (ADD) या एक बहु-सीमान्त बाइनरी डिसीजन डायग्राम, एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक बूलियन फ़ंक्शन का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है बाइनरी डिसीजन डायग्राम, या साहित्य में सामान्यतः बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो सीमान्त बिंदु बूलियन वैल्यू 0 (फॉल्स) और 1 (ट्रू) तक सीमित नहीं हैं।^[1]^[2] सीमान्त बिंदु स्थिरांक S के सेट से कोई भी मान ले सकता है।

परिभाषा

ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है $\{0,1\}^{n}$ स्थिरांक S, या बीजगणितीय संरचना के वाहक के परिमित समुच्चय के लिए है। ADD एक रूटेड, निर्देशित, चक्रीय ग्राफ है, जिसमें BDD की तरह कई बिंदु होते हैं। चूंकि, ADD में दो से अधिक सीमान्त बिंदु हो सकते हैं जो BDD के विपरीत सेट S के तत्व हैं।

एक ADD को फ़ंक्शन के कोडोमेन को विस्तारित करके बूलियन फ़ंक्शन या वेक्टर बूलियन फ़ंक्शन के रूप में भी देखा जा सकता है, जैसे कि $f:\{0,1\}^{n}\to Q$ के साथ $S\subseteq Q$ और $card(Q)=2^{n}$ कुछ पूर्णांक 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.

[:1-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.

[:0-2] 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.

[1]

[2]

@@ Line 1: / Line 1: @@
 {{Short description|Symbolic boolean function representation, extension of BDDs}}
-एक बीजगणितीय निर्णय आरेख (ADD) या एक बहु-टर्मिनल बाइनरी निर्णय आरेख (MTBDD), एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक [[Index.php?title=बूलियन फ़ंक्शन|बूलियन फ़ंक्शन]] का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है [[Index.php?title=बाइनरी डिसीजन डायग्राम|बाइनरी डिसीजन डायग्राम]], या साहित्य में  आमतौर पर बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो टर्मिनल नोड्स बूलियन वैल्यू 0 (FALSE) और 1 (TRUE) तक सीमित नहीं हैं।<ref name=":1">{{Cite journal |last1=Bahar |first1=R.I. |last2=Frohm |first2=E.A. |last3=Gaona |first3=C.M. |last4=Hachtel |first4=G.D. |last5=Macii |first5=E. |last6=Pardo |first6=A. |last7=Somenzi |first7=F. |title=बीजगणितीय निर्णय आरेख और उनके अनुप्रयोग|url=https://doi.org/10.1109/ICCAD.1993.580054 |journal=Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) |year=1993 |pages=188–191 |language=en-US |publisher=IEEE Comput. Soc. Press |doi=10.1109/iccad.1993.580054|isbn=0-8186-4490-7 |s2cid=43177472 }}</ref><ref name=":0">{{Cite journal |last1=Fujita |first1=M. |last2=McGeer |first2=P.C. |last3=Yang |first3=J.C.-Y. |date=1997-04-01 |title=Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation |url=https://doi.org/10.1023/A:1008647823331 |journal=Formal Methods in System Design |language=en |volume=10 |issue=2 |pages=149–169 |doi=10.1023/A:1008647823331 |s2cid=30494217 |issn=1572-8102}}</ref> टर्मिनल नोड स्थिरांक S के सेट से कोई भी मान ले सकता है।
+एक '''बीजगणितीय निर्णय आरेख''' (ADD) या एक बहु-सीमान्त बाइनरी डिसीजन डायग्राम, एक डेटा संरचना है जिसका उपयोग प्रतीकात्मक रूप से एक [[Index.php?title=बूलियन फ़ंक्शन|बूलियन फ़ंक्शन]] का प्रतिनिधित्व करने के लिए किया जाता है जिसका कोडोमेन एक मनमाना परिमित सेट S है। एक ADD कम किए गए क्रम का विस्तार है [[Index.php?title=बाइनरी डिसीजन डायग्राम|बाइनरी डिसीजन डायग्राम]], या साहित्य में सामान्यतः बाइनरी डिसीजन डायग्राम (BDD) नाम दिया गया है, जो सीमान्त बिंदु बूलियन वैल्यू 0 (फॉल्स) और 1 (ट्रू) तक सीमित नहीं हैं।<ref name=":1">{{Cite journal |last1=Bahar |first1=R.I. |last2=Frohm |first2=E.A. |last3=Gaona |first3=C.M. |last4=Hachtel |first4=G.D. |last5=Macii |first5=E. |last6=Pardo |first6=A. |last7=Somenzi |first7=F. |title=बीजगणितीय निर्णय आरेख और उनके अनुप्रयोग|url=https://doi.org/10.1109/ICCAD.1993.580054 |journal=Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) |year=1993 |pages=188–191 |language=en-US |publisher=IEEE Comput. Soc. Press |doi=10.1109/iccad.1993.580054|isbn=0-8186-4490-7 |s2cid=43177472 }}</ref><ref name=":0">{{Cite journal |last1=Fujita |first1=M. |last2=McGeer |first2=P.C. |last3=Yang |first3=J.C.-Y. |date=1997-04-01 |title=Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation |url=https://doi.org/10.1023/A:1008647823331 |journal=Formal Methods in System Design |language=en |volume=10 |issue=2 |pages=149–169 |doi=10.1023/A:1008647823331 |s2cid=30494217 |issn=1572-8102}}</ref> सीमान्त बिंदु स्थिरांक S के सेट से कोई भी मान ले सकता है।
 == परिभाषा ==
-ADD एक बूलियन फ़ंक्शन का प्रतिनिधित्व करता है  <math>\{0,1\}^n</math> स्थिरांक S, या [[बीजगणितीय संरचना]] के वाहक के परिमित समुच्चय के लिए। ADD एक रूटेड, डायरेक्टेड, एसाइक्लिक ग्राफ है, जिसमें BDD की तरह कई नोड होते हैं। हालाँकि, ADD में दो से अधिक टर्मिनल नोड हो सकते हैं जो BDD के विपरीत सेट S के तत्व हैं।
+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-किनारे जो चर के मूल्य TRUE के मूल्यांकन का प्रतिनिधित्व करता है, और इसके मूल्यांकन के लिए FALSE के लिए 0-किनारे।
+प्रत्येक बिंदु को एक बूलियन चर द्वारा वर्गीकरण किया जाता है और इसके दो आउटगोइंग किनारे होते हैं: 1-किनारे जो कि मान ट्रू के लिए चर के मूल्यांकन का प्रतिनिधित्व करता है, और एक 0-किनारे इसके मूल्यांकन के लिए फॉल्स का प्रतिनिधित्व करता है।
-एक एडीडी बीडीडी (या [[आरओबीडीडी]]) के समान कटौती नियमों को नियोजित करता है:
+ADD, BDD (या कम किए गए ऑर्डर वाले [[Index.php?title=BDD|BDD]]) के समान निगमन नियमों को नियोजित करता है:
-* किसी भी [[ ग्राफ समरूपता ]] सबग्राफ को मर्ज करें, और
+* किसी भी  [[Index.php?title=Index.php?title= समरूपी|समरूपी]] सबग्राफ को मर्ज करें, और
-* किसी भी नोड को समाप्त करें जिसके दो बच्चे आइसोमोर्फिक हैं।
+* ऐसे किसी भी बिंदु को हटा दें जो समरूपी हों।
-ADD एक विशेष चर क्रम के अनुसार विहित हैं।
+ADD एक विशेष चर क्रम के अनुसार विहित होते हैं।
 == मैट्रिक्स विभाजन ==
-एक AD को उसके सहकारकों के अनुसार एक मैट्रिक्स द्वारा दर्शाया जा सकता है।<ref name=":0" /><ref name=":1" />
+एक ADD को उसके सहकारकों के अनुसार एक मैट्रिक्स द्वारा दर्शाया जा सकता है।<ref name=":0" /><ref name=":1" />
 == अनुप्रयोग ==
-ADDs को सबसे पहले [[मैट्रिक्स गुणन]] और सबसे छोटी पथ समस्या (बेलमैन-फोर्ड एल्गोरिथम | बेलमैन-फोर्ड, बार-बार स्क्वेरिंग, और फ़्लॉइड-वॉर्शल एल्गोरिथम | फ्लॉयड-वॉर्शल प्रक्रियाएँ) के लिए लागू किया गया था।<ref name=":1" />
+ADDs को सबसे पहले विरल [[मैट्रिक्स गुणन]] और सबसे छोटे पथ एल्गोरिदम के लिए प्रयुक्त किया गया था।<ref name=":1" />
 == यह भी देखें ==
-* बाइनरी निर्णय आरेख
+* बाइनरी डिसीजन डायग्राम
-* [[शून्य-दबा हुआ निर्णय आरेख]]
+* [[Index.php?title=ज़ीरो-सुप्प्रेस्सेड डिसीजन डायग्राम|ज़ीरो-सुप्प्रेस्सेड डिसीजन डायग्राम]]
 ==संदर्भ==
 {{Reflist}}
+[[Category:CS1 English-language sources (en)]]
-[[Category: चित्र]] [[Category: ग्राफ डेटा संरचनाएं]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 19/06/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:ग्राफ डेटा संरचनाएं]]
+[[Category:चित्र]]

Anonymous

Search

बीजगणितीय निर्णय आरेख: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 07:54, 15 July 2023

Contents

परिभाषा

मैट्रिक्स विभाजन

अनुप्रयोग

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बीजगणितीय निर्णय आरेख: Difference between revisions

Latest revision as of 07:54, 15 July 2023

परिभाषा

मैट्रिक्स विभाजन

अनुप्रयोग

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories