सर्किट (कंप्यूटर विज्ञान): Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[सैद्धांतिक कंप्यूटर विज्ञान]] में, एक परिपथ गणना का एक मॉडल है जिसमें इनपुट मान गेट्स के अनुक्रम के माध्यम से आगे बढ़ते हैं, जिनमें से प्रत्येक एक कार्य (कंप्यूटर विज्ञान) की गणना करता है। इस तरह के परिपथ [[बूलियन सर्किट|बूलियन]] परिपथ का एक सामान्यीकरण और [[ डिजिटल तर्क ]] परिपथ के लिए एक गणितीय मॉडल प्रदान करते हैं। परिपथ को उन गेट्स द्वारा परिभाषित किया जाता है जिनमें वे होते हैं और वे मान जो गेट्स उत्पन्न कर सकते हैं। उदाहरण के लिए, बूलियन परिपथ में मान [[बूलियन डेटा प्रकार]] के मान हैं, और परिपथ में लॉजिकल संयोजन, [[तार्किक संयोजन]] और [[ तार्किक निषेध ]] गेट्स सम्मिलित हैं। एक [[पूर्णांक]] परिपथ में मान पूर्णांकों के [[सेट (गणित)]] होते हैं और गेट्स [[ संघ स्थापित करें ]][[ चौराहा सेट करें | प्रतिच्छेदन सेट करें]] | [[सैद्धांतिक कंप्यूटर विज्ञान]] में, एक परिपथ गणना का एक मॉडल है जिसमें इनपुट मान गेट्स के अनुक्रम के माध्यम से आगे बढ़ते हैं, जिनमें से प्रत्येक एक कार्य (कंप्यूटर विज्ञान) की गणना करता है। इस तरह के परिपथ [[बूलियन सर्किट|बूलियन]] परिपथ का एक सामान्यीकरण और [[ डिजिटल तर्क |डिजिटल तर्क]] परिपथ के लिए एक गणितीय मॉडल प्रदान करते हैं। परिपथ को उन गेट्स द्वारा परिभाषित किया जाता है जिनमें वे होते हैं और वे मान जो गेट्स उत्पन्न कर सकते हैं। उदाहरण के लिए, बूलियन परिपथ में मान [[बूलियन डेटा प्रकार]] के मान हैं, और परिपथ में लॉजिकल संयोजन, [[तार्किक संयोजन]] और [[ तार्किक निषेध |तार्किक निषेध]] गेट्स सम्मिलित हैं। एक [[पूर्णांक]] परिपथ में मान पूर्णांकों के [[सेट (गणित)]] होते हैं और गेट्स [[ संघ स्थापित करें |संघ स्थापित करें]] [[ चौराहा सेट करें |प्रतिच्छेदन सेट करें]] और [[सेट पूरक]], साथ ही साथ अंकगणितीय संचालन जोड़ और गुणन की गणना करते हैं। | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
एक परिपथ एक ट्रिपल है <math>(M, L, G)</math>, जहाँ | एक परिपथ एक ट्रिपल है <math>(M, L, G)</math>, जहाँ | ||
* <math>M</math> मानो का एक समूह है, | * <math>M</math> मानो का एक समूह है, | ||
*<math>L</math> | *<math>L</math> गेट लेबल का एक सेट है, जिनमें से प्रत्येक <math>M^{i}</math> से <math>M</math> तक कुछ गैर-नकारात्मक पूर्णांक <math>i</math> (जहां <math>i</math> गेट में इनपुट की संख्या का प्रतिनिधित्व करता है) के लिए एक कार्य है और | ||
* <math>G</math>,<math>L</math> से लेबल के साथ एक [[लेबल वाला ग्राफ]] निर्देशित चक्रीय ग्राफ है | * <math>G</math>,<math>L</math> से लेबल के साथ एक [[लेबल वाला ग्राफ]] निर्देशित चक्रीय ग्राफ है | ||
ग्राफ के शीर्षों को गेट्स कहा जाता है। इन-डिग्री <math>i</math> के प्रत्येक गेट <math>g</math> के लिए, गेट <math>g</math> को <math>L</math> के सभी तत्वों <math>\ell</math> द्वारा लेबल किया जा सकता है यदि और केवल यदि <math>\ell</math> को | ग्राफ के शीर्षों को गेट्स कहा जाता है। इन-डिग्री <math>i</math> के प्रत्येक गेट <math>g</math> के लिए, गेट <math>g</math> को <math>L</math> के सभी तत्वों <math>\ell</math> द्वारा लेबल किया जा सकता है यदि और केवल यदि <math>\ell</math> को <math>M^{i}.</math> पर परिभाषित किया गया है। | ||
=== शब्दावली === | === शब्दावली === | ||
इन-डिग्री 0 के गेट्स को इनपुट्स या लीव्स कहा जाता है। आउट-डिग्री 0 के गेट्स को आउटपुट कहा जाता है। यदि ग्राफ<math>G</math> में गेट <math>g</math> से गेट <math>h</math> तक कोई किनारा है तो <math>h</math> को <math>g</math> का चाइल्ड कहा जाता है। हमें लगता है कि ग्राफ के शीर्ष पर एक क्रम है, इसलिए हम गेट के <math>k</math> वें बच्चे के बारे में बात कर सकते हैं जब <math>k</math> गेट के आउट-डिग्री से कम है। | इन-डिग्री 0 के गेट्स को इनपुट्स या लीव्स कहा जाता है। आउट-डिग्री 0 के गेट्स को आउटपुट कहा जाता है। यदि ग्राफ<math>G</math> में गेट <math>g</math> से गेट <math>h</math> तक कोई किनारा है तो <math>h</math> को <math>g</math> का चाइल्ड कहा जाता है। हमें लगता है कि ग्राफ के शीर्ष पर एक क्रम है, इसलिए हम गेट के <math>k</math> वें बच्चे के बारे में बात कर सकते हैं जब <math>k</math> गेट के आउट-डिग्री से कम है। | ||
परिपथ का आकार परिपथ के नोड्स की संख्या है। गेट <math>g</math> | परिपथ का आकार परिपथ के नोड्स की संख्या है। गेट <math>g</math> की गहराई <math>G</math> में आउटपुट गेट तक '''<math>g</math>''' से प्रारंभ होने वाले सबसे लंबे पथ की लंबाई है। विशेष रूप से, आउट-डिग्री 0 के द्वार केवल गहराई के द्वार हैं। एक परिपथ की गहराई किसी भी द्वार की अधिकतम गहराई है। | ||
स्तर <math>i</math> गहराई के सभी द्वारों का समुच्चय है <math>i</math> एक समतल परिपथ एक ऐसा परिपथ होता है | स्तर <math>i</math> गहराई के सभी द्वारों का समुच्चय है <math>i</math> एक समतल परिपथ एक ऐसा परिपथ होता है जिसमें गहराई के द्वार <math>i</math> के किनारे <math>i + 1</math> या इनपुट से ही गहराई के द्वार से आते हैं। दूसरे शब्दों में, किनारे केवल परिपथ के आसन्न स्तरों के बीच उपस्थित होते हैं। समतल परिपथ की चौड़ाई किसी भी स्तर का अधिकतम आकार है। | ||
=== मूल्यांकन === | === मूल्यांकन === | ||
| Line 32: | Line 32: | ||
पत्तियों के लेबल वेरिएबल्स भी हो सकते हैं जो <math>M</math> में मान लेते हैं। यदि <math>n</math> पत्तियां हैं, तो परिपथ को <math>M^{n}</math> से <math>M</math> तक एक कार्य के रूप में देखा जा सकता है। फिर परिपथ के एक वर्ग पर विचार करना सामान्य है <math>(C_n)_{n\in\mathbb{N}}</math>, पूर्णांकों द्वारा अनुक्रमित परिपथ का एक क्रम जहां परिपथ <math>C_n</math> में <math>n</math> चर होते हैं। परिपथ के वर्गों को इस प्रकार <math>M^{*}</math> से <math>M</math> तक के कार्यों के रूप में देखा जा सकता है। | पत्तियों के लेबल वेरिएबल्स भी हो सकते हैं जो <math>M</math> में मान लेते हैं। यदि <math>n</math> पत्तियां हैं, तो परिपथ को <math>M^{n}</math> से <math>M</math> तक एक कार्य के रूप में देखा जा सकता है। फिर परिपथ के एक वर्ग पर विचार करना सामान्य है <math>(C_n)_{n\in\mathbb{N}}</math>, पूर्णांकों द्वारा अनुक्रमित परिपथ का एक क्रम जहां परिपथ <math>C_n</math> में <math>n</math> चर होते हैं। परिपथ के वर्गों को इस प्रकार <math>M^{*}</math> से <math>M</math> तक के कार्यों के रूप में देखा जा सकता है। | ||
आकार, गहराई और चौड़ाई की धारणाओं को स्वाभाविक रूप से कार्यों के वर्गों तक बढ़ाया जा सकता है, जो <math>\mathbb{N}</math> से <math>\mathbb{N}</math> तक के कार्य बन जाते हैं; उदाहरण के लिए, <math>size(n)</math> वर्ग | आकार, गहराई और चौड़ाई की धारणाओं को स्वाभाविक रूप से कार्यों के वर्गों तक बढ़ाया जा सकता है, जो <math>\mathbb{N}</math> से <math>\mathbb{N}</math> तक के कार्य बन जाते हैं; उदाहरण के लिए, <math>size(n)</math> वर्ग के nवें परिपथ का आकार है। | ||
== जटिलता और एल्गोरिथम समस्याएं == | == जटिलता और एल्गोरिथम समस्याएं == | ||
किसी विशिष्ट इनपुट पर दिए गए बूलियन परिपथ के आउटपुट की गणना करना एक [[पी-पूर्ण]] समस्या है। यदि इनपुट एक पूर्णांक परिपथ है, चूँकि | किसी विशिष्ट इनपुट पर दिए गए बूलियन परिपथ के आउटपुट की गणना करना एक [[पी-पूर्ण]] समस्या है। यदि इनपुट एक पूर्णांक परिपथ है, चूँकि यह अज्ञात है कि यह समस्या निर्णायक है। | ||
[[सर्किट जटिलता|परिपथ जटिलता]] बूलियन कार्यों को उन परिपथ के आकार या गहराई के संबंध में वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकते हैं। | [[सर्किट जटिलता|परिपथ जटिलता]] बूलियन कार्यों को उन परिपथ के आकार या गहराई के संबंध में वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकते हैं। | ||
== यह भी देखें == | |||
'''ई की धारणाओं को स्वाभाविक रूप से कार्यों के वर्गों तक बढ़ाया जा सकता है, जो <math>\mathbb{N}</math> से <math>\mathbb{N}</math> तक के कार्य बन जाते हैं; उदाहरण के लिए, <math>size(n)</math> वर्ग के nवें परिपथ का आ''' | |||
== यह भी देखें == | |||
* [[अंकगणितीय सर्किट जटिलता|अंकगणितीय परिपथ जटिलता]] | * [[अंकगणितीय सर्किट जटिलता|अंकगणितीय परिपथ जटिलता]] | ||
* बूलियन परिपथ | * बूलियन परिपथ | ||
| Line 46: | Line 49: | ||
* [[प्राकृतिक संख्याओं के सेट पर सर्किट|प्राकृतिक संख्याओं के सेट पर परिपथ]] | * [[प्राकृतिक संख्याओं के सेट पर सर्किट|प्राकृतिक संख्याओं के सेट पर परिपथ]] | ||
* [[जटिलता वर्ग]] [[नेकां (जटिलता)]], [[एसी (जटिलता)]] और [[टीसी (जटिलता)]] | * [[जटिलता वर्ग]] [[नेकां (जटिलता)]], [[एसी (जटिलता)]] और [[टीसी (जटिलता)]] | ||
* [[ यह कितना घूमता है? ]] और [[बीक्यूपी]] | * [[ यह कितना घूमता है? | यह कितना घूमता है?]] और [[बीक्यूपी]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 12:30, 17 May 2023
सैद्धांतिक कंप्यूटर विज्ञान में, एक परिपथ गणना का एक मॉडल है जिसमें इनपुट मान गेट्स के अनुक्रम के माध्यम से आगे बढ़ते हैं, जिनमें से प्रत्येक एक कार्य (कंप्यूटर विज्ञान) की गणना करता है। इस तरह के परिपथ बूलियन परिपथ का एक सामान्यीकरण और डिजिटल तर्क परिपथ के लिए एक गणितीय मॉडल प्रदान करते हैं। परिपथ को उन गेट्स द्वारा परिभाषित किया जाता है जिनमें वे होते हैं और वे मान जो गेट्स उत्पन्न कर सकते हैं। उदाहरण के लिए, बूलियन परिपथ में मान बूलियन डेटा प्रकार के मान हैं, और परिपथ में लॉजिकल संयोजन, तार्किक संयोजन और तार्किक निषेध गेट्स सम्मिलित हैं। एक पूर्णांक परिपथ में मान पूर्णांकों के सेट (गणित) होते हैं और गेट्स संघ स्थापित करें प्रतिच्छेदन सेट करें और सेट पूरक, साथ ही साथ अंकगणितीय संचालन जोड़ और गुणन की गणना करते हैं।
औपचारिक परिभाषा
एक परिपथ एक ट्रिपल है , जहाँ
- मानो का एक समूह है,
- गेट लेबल का एक सेट है, जिनमें से प्रत्येक से तक कुछ गैर-नकारात्मक पूर्णांक (जहां गेट में इनपुट की संख्या का प्रतिनिधित्व करता है) के लिए एक कार्य है और
- , से लेबल के साथ एक लेबल वाला ग्राफ निर्देशित चक्रीय ग्राफ है
ग्राफ के शीर्षों को गेट्स कहा जाता है। इन-डिग्री के प्रत्येक गेट के लिए, गेट को के सभी तत्वों द्वारा लेबल किया जा सकता है यदि और केवल यदि को पर परिभाषित किया गया है।
शब्दावली
इन-डिग्री 0 के गेट्स को इनपुट्स या लीव्स कहा जाता है। आउट-डिग्री 0 के गेट्स को आउटपुट कहा जाता है। यदि ग्राफ में गेट से गेट तक कोई किनारा है तो को का चाइल्ड कहा जाता है। हमें लगता है कि ग्राफ के शीर्ष पर एक क्रम है, इसलिए हम गेट के वें बच्चे के बारे में बात कर सकते हैं जब गेट के आउट-डिग्री से कम है।
परिपथ का आकार परिपथ के नोड्स की संख्या है। गेट की गहराई में आउटपुट गेट तक से प्रारंभ होने वाले सबसे लंबे पथ की लंबाई है। विशेष रूप से, आउट-डिग्री 0 के द्वार केवल गहराई के द्वार हैं। एक परिपथ की गहराई किसी भी द्वार की अधिकतम गहराई है।
स्तर गहराई के सभी द्वारों का समुच्चय है एक समतल परिपथ एक ऐसा परिपथ होता है जिसमें गहराई के द्वार के किनारे या इनपुट से ही गहराई के द्वार से आते हैं। दूसरे शब्दों में, किनारे केवल परिपथ के आसन्न स्तरों के बीच उपस्थित होते हैं। समतल परिपथ की चौड़ाई किसी भी स्तर का अधिकतम आकार है।
मूल्यांकन
इन-डिग्री और लेबल वाले गेट का स्पष्ट मान सभी गेट के लिए पुनरावर्ती रूप से परिभाषित किया गया है।
जहां प्रत्येक , का अभिभावक है
परिपथ का मान प्रत्येक आउटपुट गेट का मान है।
कार्य के रूप में परिपथ
पत्तियों के लेबल वेरिएबल्स भी हो सकते हैं जो में मान लेते हैं। यदि पत्तियां हैं, तो परिपथ को से तक एक कार्य के रूप में देखा जा सकता है। फिर परिपथ के एक वर्ग पर विचार करना सामान्य है , पूर्णांकों द्वारा अनुक्रमित परिपथ का एक क्रम जहां परिपथ में चर होते हैं। परिपथ के वर्गों को इस प्रकार से तक के कार्यों के रूप में देखा जा सकता है।
आकार, गहराई और चौड़ाई की धारणाओं को स्वाभाविक रूप से कार्यों के वर्गों तक बढ़ाया जा सकता है, जो से तक के कार्य बन जाते हैं; उदाहरण के लिए, वर्ग के nवें परिपथ का आकार है।
जटिलता और एल्गोरिथम समस्याएं
किसी विशिष्ट इनपुट पर दिए गए बूलियन परिपथ के आउटपुट की गणना करना एक पी-पूर्ण समस्या है। यदि इनपुट एक पूर्णांक परिपथ है, चूँकि यह अज्ञात है कि यह समस्या निर्णायक है।
परिपथ जटिलता बूलियन कार्यों को उन परिपथ के आकार या गहराई के संबंध में वर्गीकृत करने का प्रयास करती है जो उनकी गणना कर सकते हैं।
ई की धारणाओं को स्वाभाविक रूप से कार्यों के वर्गों तक बढ़ाया जा सकता है, जो से तक के कार्य बन जाते हैं; उदाहरण के लिए, वर्ग के nवें परिपथ का आ
यह भी देखें
- अंकगणितीय परिपथ जटिलता
- बूलियन परिपथ
- परिपथ जटिलता
- प्राकृतिक संख्याओं के सेट पर परिपथ
- जटिलता वर्ग नेकां (जटिलता), एसी (जटिलता) और टीसी (जटिलता)
- यह कितना घूमता है? और बीक्यूपी
संदर्भ
- Vollmer, Heribert (1999). Introduction to Circuit Complexity. Berlin: Springer. ISBN 978-3-540-64310-4.
- Yang, Ke (2001). "Integer Circuit Evaluation Is PSPACE-Complete". Journal of Computer and System Sciences. 63 (2, September 2001): 288–303. doi:10.1006/jcss.2001.1768. ISSN 0022-0000.
