ब्लॉक डिजाइन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
[[साहचर्य]] गणित में, ब्लॉक संरचना [[घटना संरचना]] है जिसमें उपसमुच्चय के परिवार के साथ मिलकर समुच्चय होता है जिसे 'ब्लॉक' के रूप में जाना जाता है, इस तरह चुना जाता है कि तत्वों की आवृत्ति कुछ शर्तों को पूरा करती है जिससे ब्लॉक का संग्रह [[समरूपता]] (संतुलन) प्रदर्शित करता है। ब्लॉक संरचनाों में प्रयोगात्मक संरचना, [[परिमित ज्यामिति]], [[भौतिक रसायन]] शास्त्र, [[सॉफ़्टवेयर परीक्षण]], [[क्रिप्टोग्राफी]] और [[बीजगणितीय ज्यामिति]] सहित कई क्षेत्रों में अनुप्रयोग हैं। | [[साहचर्य]] गणित में, ब्लॉक संरचना [[घटना संरचना]] है जिसमें उपसमुच्चय के परिवार के साथ मिलकर समुच्चय होता है जिसे 'ब्लॉक' के रूप में जाना जाता है, इस तरह चुना जाता है कि तत्वों की आवृत्ति कुछ शर्तों को पूरा करती है जिससे ब्लॉक का संग्रह [[समरूपता]] (संतुलन) प्रदर्शित करता है। ब्लॉक संरचनाों में प्रयोगात्मक संरचना, [[परिमित ज्यामिति]], [[भौतिक रसायन]] शास्त्र, [[सॉफ़्टवेयर परीक्षण]], [[क्रिप्टोग्राफी]] और [[बीजगणितीय ज्यामिति]] सहित कई क्षेत्रों में अनुप्रयोग हैं। | ||
आगे विशिष्टताओं के बिना 'ब्लॉक संरचना' शब्द सामान्यतः संतुलित अपूर्ण ब्लॉक संरचना (बीआईबीडी) को संदर्भित करता है, विशेष रूप से (और समानार्थक रूप से) 2-संरचना, जो संरचना में इसके अनुप्रयोग के कारण ऐतिहासिक रूप से सबसे गहन अध्ययन प्रकार रहा है। '''प्रयोगों का।'''<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pp.17−19}}</ref><ref>{{harvnb|Stinson|2003|loc=p.1}}</ref> इसके प्रयोगों का सामान्यीकरण को t-संरचना के रूप में जाना जाता है।''' | आगे विशिष्टताओं के बिना 'ब्लॉक संरचना' शब्द सामान्यतः संतुलित अपूर्ण ब्लॉक संरचना (बीआईबीडी) को संदर्भित करता है, विशेष रूप से (और समानार्थक रूप से) 2-संरचना, जो संरचना में इसके अनुप्रयोग के कारण ऐतिहासिक रूप से सबसे गहन अध्ययन प्रकार रहा है। '''प्रयोगों का।'''<ref>{{harvnb|Colbourn|Dinitz|2007|loc=pp.17−19}}</ref><ref>{{harvnb|Stinson|2003|loc=p.1}}</ref> इसके प्रयोगों का सामान्यीकरण को t-संरचना के रूप में जाना जाता है। '''[[क्रिप्टोग्राफी]] और [[बीजगणितीय ज्यामिति]] सहित कई क्षेत्रों में अनुप्रयोग हैं।''' | ||
== अवलोकन == | == अवलोकन == | ||
| Line 19: | Line 19: | ||
सबसे सरल प्रकार की संतुलित संरचना (t = 1) को 'सामरिक विन्यास' या '1-संरचना' के रूप में जाना जाता है। [[ज्यामिति]] में संबंधित घटना संरचना को 'विन्यास' के रूप में जाना जाता है, [[विन्यास (ज्यामिति)]] देखें। ऐसा संरचना एक समान और नियमित है: प्रत्येक ब्लॉक में k तत्व होते हैं और प्रत्येक तत्व r ब्लॉक में समाहित होता है। समुच्चय तत्वों की संख्या v और ब्लॉकों की संख्या b से संबंधित हैं <math> bk = vr </math>, जो तत्वों की घटनाओं की कुल संख्या है। | सबसे सरल प्रकार की संतुलित संरचना (t = 1) को 'सामरिक विन्यास' या '1-संरचना' के रूप में जाना जाता है। [[ज्यामिति]] में संबंधित घटना संरचना को 'विन्यास' के रूप में जाना जाता है, [[विन्यास (ज्यामिति)]] देखें। ऐसा संरचना एक समान और नियमित है: प्रत्येक ब्लॉक में k तत्व होते हैं और प्रत्येक तत्व r ब्लॉक में समाहित होता है। समुच्चय तत्वों की संख्या v और ब्लॉकों की संख्या b से संबंधित हैं <math> bk = vr </math>, जो तत्वों की घटनाओं की कुल संख्या है। | ||
निरंतर पंक्ति और स्तंभ योगों वाला प्रत्येक [[बाइनरी मैट्रिक्स]] नियमित वर्दी ब्लॉक संरचना का [[घटना मैट्रिक्स]] है। इसके अतिरिक्त, प्रत्येक विन्यास में संबंधित [[बिरेगुलर ग्राफ]] [[द्विपक्षीय ग्राफ]] [[ग्राफ (असतत गणित)]] होता है जिसे इसकी घटना या [[लेवी ग्राफ| | निरंतर पंक्ति और स्तंभ योगों वाला प्रत्येक [[बाइनरी मैट्रिक्स]] नियमित वर्दी ब्लॉक संरचना का [[घटना मैट्रिक्स]] है। इसके अतिरिक्त, प्रत्येक विन्यास में संबंधित [[बिरेगुलर ग्राफ]] [[द्विपक्षीय ग्राफ]] [[ग्राफ (असतत गणित)]] होता है जिसे इसकी घटना या [[लेवी ग्राफ|v ग्राफ]] के रूप में जाना जाता है। | ||
== जोड़ीदार संतुलित वर्दी संरचना (2-संरचना या बीआईबीडी) == | == जोड़ीदार संतुलित वर्दी संरचना (2-संरचना या बीआईबीडी) == | ||
परिमित समुच्चय X (बिंदु कहे जाने वाले तत्वों का) और पूर्णांक k, r, λ ≥ 1 को देखते हुए, हम 2-संरचना (या बीआईबीडी, संतुलित अपूर्ण ब्लॉक संरचना के लिए खड़े) B को परिभाषित करते हैं, जो कि X के k-तत्व सबसमुच्चय का परिवार है। , ब्लॉक कहा जाता है, जैसे कि X में कोई भी x r ब्लॉक में समाहित है, और X में अलग-अलग बिंदु x और y की कोई भी जोड़ी λ ब्लॉक में समाहित है। यहां, शर्त यह है कि x में कोई भी x r ब्लॉक में निहित है, जैसा कि नीचे दिखाया गया | परिमित समुच्चय X (बिंदु कहे जाने वाले तत्वों का) और पूर्णांक k, r, λ ≥ 1 को देखते हुए, हम 2-संरचना (या बीआईबीडी, संतुलित अपूर्ण ब्लॉक संरचना के लिए खड़े) B को परिभाषित करते हैं, जो कि X के k-तत्व सबसमुच्चय का परिवार है। , ब्लॉक कहा जाता है, जैसे कि X में कोई भी x r ब्लॉक में समाहित है, और X में अलग-अलग बिंदु x और y की कोई भी जोड़ी λ ब्लॉक में समाहित है। यहां, शर्त यह है कि x में कोई भी x r ब्लॉक में निहित है, जैसा कि नीचे दिखाया गया है। | ||
यहाँ v (X के तत्वों की संख्या, जिसे बिंदु कहा जाता है), b (ब्लॉक की संख्या), k, r, और λ संरचना के पैरामीटर हैं। (पतित उदाहरणों से बचने के लिए, यह भी माना जाता है कि v > k, ताकि किसी भी ब्लॉक में समुच्चय के सभी तत्व सम्मिलित न हों। इन संरचनाों के नाम में अपूर्णता का यही अर्थ है।) तालिका में: | यहाँ v (X के तत्वों की संख्या, जिसे बिंदु कहा जाता है), b (ब्लॉक की संख्या), k, r, और λ संरचना के पैरामीटर हैं। (पतित उदाहरणों से बचने के लिए, यह भी माना जाता है कि v > k, ताकि किसी भी ब्लॉक में समुच्चय के सभी तत्व सम्मिलित न हों। इन संरचनाों के नाम में अपूर्णता का यही अर्थ है।) तालिका में: | ||
| Line 129: | Line 129: | ||
m आकार का [[हैडमार्ड मैट्रिक्स]] m × m मैट्रिक्स 'H' है जिसकी प्रविष्टियाँ ±1 ऐसी हैं कि 'HH'<sup>⊤</sup> = mi<sub>m</sub>, जहां H<sup>⊤</sup> H और I<sub>''m''</sub> का स्थानान्तरण है<sub>''m''</sub> m × m पहचान मैट्रिक्स है। हैडमार्ड मैट्रिक्स को मानकीकृत रूप में रखा जा सकता है (अर्थात, समकक्ष हैडमार्ड मैट्रिक्स में परिवर्तित) जहां पहली पंक्ति और पहली कॉलम प्रविष्टियां सभी +1 हैं। यदि आकार m > 2 है तो m 4 का गुणक होना चाहिए। | m आकार का [[हैडमार्ड मैट्रिक्स]] m × m मैट्रिक्स 'H' है जिसकी प्रविष्टियाँ ±1 ऐसी हैं कि 'HH'<sup>⊤</sup> = mi<sub>m</sub>, जहां H<sup>⊤</sup> H और I<sub>''m''</sub> का स्थानान्तरण है<sub>''m''</sub> m × m पहचान मैट्रिक्स है। हैडमार्ड मैट्रिक्स को मानकीकृत रूप में रखा जा सकता है (अर्थात, समकक्ष हैडमार्ड मैट्रिक्स में परिवर्तित) जहां पहली पंक्ति और पहली कॉलम प्रविष्टियां सभी +1 हैं। यदि आकार m > 2 है तो m 4 का गुणक होना चाहिए। | ||
मानकीकृत रूप में आकार 4a के हैडमार्ड मैट्रिक्स को देखते हुए, पहली पंक्ति और पहले कॉलम को हटा दें और प्रत्येक −1 को 0 में बदलें। परिणामी 0–1 मैट्रिक्स 'M' सममित 2-(4a − 1, का आपतन मैट्रिक्स है, 2a − 1, a − 1) संरचना जिसे 'हैडमार्ड 2-संरचना' कहा जाता है।<ref>{{harvnb|Stinson|2003|loc=pg. 74, Theorem 4.5}}</ref> इसमें है <math>4a-1</math> ब्लॉक | मानकीकृत रूप में आकार 4a के हैडमार्ड मैट्रिक्स को देखते हुए, पहली पंक्ति और पहले कॉलम को हटा दें और प्रत्येक −1 को 0 में बदलें। परिणामी 0–1 मैट्रिक्स 'M' सममित 2-(4a − 1, का आपतन मैट्रिक्स है, 2a − 1, a − 1) संरचना जिसे 'हैडमार्ड 2-संरचना' कहा जाता है।<ref>{{harvnb|Stinson|2003|loc=pg. 74, Theorem 4.5}}</ref> इसमें है <math>4a-1</math> ब्लॉक अंक; प्रत्येक में सम्मिलित है / इसमें निहित है <math>2a-1</math> अंक ब्लॉक। अंकों की प्रत्येक जोड़ी बिल्कुल में समाहित है <math>a-1</math> ब्लॉक। | ||
यह निर्माण प्रतिवर्ती है, और इन मापदंडों के साथ सममित 2-संरचना की घटना मैट्रिक्स का उपयोग आकार 4a के हैडमार्ड मैट्रिक्स को बनाने के लिए किया जा सकता है। | यह निर्माण प्रतिवर्ती है, और इन मापदंडों के साथ सममित 2-संरचना की घटना मैट्रिक्स का उपयोग आकार 4a के हैडमार्ड मैट्रिक्स को बनाने के लिए किया जा सकता है। | ||
Revision as of 21:21, 25 March 2023
साहचर्य गणित में, ब्लॉक संरचना घटना संरचना है जिसमें उपसमुच्चय के परिवार के साथ मिलकर समुच्चय होता है जिसे 'ब्लॉक' के रूप में जाना जाता है, इस तरह चुना जाता है कि तत्वों की आवृत्ति कुछ शर्तों को पूरा करती है जिससे ब्लॉक का संग्रह समरूपता (संतुलन) प्रदर्शित करता है। ब्लॉक संरचनाों में प्रयोगात्मक संरचना, परिमित ज्यामिति, भौतिक रसायन शास्त्र, सॉफ़्टवेयर परीक्षण, क्रिप्टोग्राफी और बीजगणितीय ज्यामिति सहित कई क्षेत्रों में अनुप्रयोग हैं।
आगे विशिष्टताओं के बिना 'ब्लॉक संरचना' शब्द सामान्यतः संतुलित अपूर्ण ब्लॉक संरचना (बीआईबीडी) को संदर्भित करता है, विशेष रूप से (और समानार्थक रूप से) 2-संरचना, जो संरचना में इसके अनुप्रयोग के कारण ऐतिहासिक रूप से सबसे गहन अध्ययन प्रकार रहा है। प्रयोगों का।[1][2] इसके प्रयोगों का सामान्यीकरण को t-संरचना के रूप में जाना जाता है। क्रिप्टोग्राफी और बीजगणितीय ज्यामिति सहित कई क्षेत्रों में अनुप्रयोग हैं।
अवलोकन
संरचना को संतुलित (t तक) कहा जाता है यदि मूल समुच्चय के सभी t-उपसमुच्चय समान रूप से कई (यानी, λ) ब्लॉकों में होते हैं। जब t निर्दिष्ट नहीं होता है, तो इसे सामान्यतः 2 माना जा सकता है, जिसका अर्थ है कि तत्वों की प्रत्येक जोड़ी समान संख्या में ब्लॉक में पाई जाती है और संरचना जोड़ीदार संतुलित है। t = 1 के लिए, प्रत्येक तत्व समान संख्या में ब्लॉक (प्रतिकृति संख्या, निरूपित r) में होता है और संरचना को नियमित कहा जाता है। t तक संतुलित कोई भी संरचना t के सभी निचले मूल्यों (चूंकि विभिन्न λ-मानों के साथ) में भी संतुलित है, इसलिए उदाहरण के लिए जोड़ीदार संतुलित (t = 2) संरचना भी नियमित (t = 1) है। जब संतुलन की आवश्यकता विफल हो जाती है, तब भी संरचना आंशिक रूप से संतुलित हो सकता है यदि t-उपसमुच्चय को n वर्गों में विभाजित किया जा सकता है, प्रत्येक का अपना (अलग) λ-मूल्य है। t = 2 के लिए इन्हें 'पीबीआईबीडी (n) संरचना' के रूप में जाना जाता है, जिनकी कक्षाएं संघ योजना बनाती हैं।
संरचना को सामान्यतः अधूरा कहा जाता है (या माना जाता है), जिसका अर्थ है कि किसी भी ब्लॉक में समुच्चय के सभी तत्व नहीं होते हैं, इस प्रकार तुच्छ संरचना को बेकार कर दिया जाता है।
ब्लॉक संरचना जिसमें सभी ब्लॉकों का आकार समान होता है (सामान्यतः k को निरूपित किया जाता है) को समान या उचित कहा जाता है। इस आलेख में चर्चा की गई संरचना सभी समान हैं। ब्लॉक संरचना जो आवश्यक रूप से एक समान नहीं हैं, का भी अध्ययन किया गया है; t = 2 के लिए वे साहित्य में सामान्य नाम कॉम्बिनेटरियल संरचना # जोड़ीदार संतुलित संरचना (पीबीडी) के अंतर्गत जाने जाते हैं।
ब्लॉक संरचना में बार-बार ब्लॉक हो भी सकते हैं और नहीं भी। दोहराए गए ब्लॉक के बिना संरचना सरल कहलाते हैं,[3] इस स्थितियों में ब्लॉक का परिवार मल्टीसेट के अतिरिक्त समुच्चय (गणित) है।
आँकड़ों में, ब्लॉक संरचना की अवधारणा को गैर-बाइनरी ब्लॉक संरचनाों तक बढ़ाया जा सकता है, जिसमें ब्लॉक में तत्व की कई प्रतियां हो सकती हैं (ब्लॉकिंग (आँकड़े) देखें)। वहां, संरचना जिसमें प्रत्येक तत्व एक ही कुल संख्या में होता है, उसे समकक्ष कहा जाता है, जिसका अर्थ केवल नियमित संरचना होता है, जब संरचना भी द्विआधारी होता है। गैर-बाइनरी संरचना की घटना मैट्रिक्स प्रत्येक ब्लॉक में प्रत्येक तत्व के दोहराए जाने की संख्या को सूचीबद्ध करती है।
नियमित वर्दी संरचना (विन्यास)
सबसे सरल प्रकार की संतुलित संरचना (t = 1) को 'सामरिक विन्यास' या '1-संरचना' के रूप में जाना जाता है। ज्यामिति में संबंधित घटना संरचना को 'विन्यास' के रूप में जाना जाता है, विन्यास (ज्यामिति) देखें। ऐसा संरचना एक समान और नियमित है: प्रत्येक ब्लॉक में k तत्व होते हैं और प्रत्येक तत्व r ब्लॉक में समाहित होता है। समुच्चय तत्वों की संख्या v और ब्लॉकों की संख्या b से संबंधित हैं , जो तत्वों की घटनाओं की कुल संख्या है।
निरंतर पंक्ति और स्तंभ योगों वाला प्रत्येक बाइनरी मैट्रिक्स नियमित वर्दी ब्लॉक संरचना का घटना मैट्रिक्स है। इसके अतिरिक्त, प्रत्येक विन्यास में संबंधित बिरेगुलर ग्राफ द्विपक्षीय ग्राफ ग्राफ (असतत गणित) होता है जिसे इसकी घटना या v ग्राफ के रूप में जाना जाता है।
जोड़ीदार संतुलित वर्दी संरचना (2-संरचना या बीआईबीडी)
परिमित समुच्चय X (बिंदु कहे जाने वाले तत्वों का) और पूर्णांक k, r, λ ≥ 1 को देखते हुए, हम 2-संरचना (या बीआईबीडी, संतुलित अपूर्ण ब्लॉक संरचना के लिए खड़े) B को परिभाषित करते हैं, जो कि X के k-तत्व सबसमुच्चय का परिवार है। , ब्लॉक कहा जाता है, जैसे कि X में कोई भी x r ब्लॉक में समाहित है, और X में अलग-अलग बिंदु x और y की कोई भी जोड़ी λ ब्लॉक में समाहित है। यहां, शर्त यह है कि x में कोई भी x r ब्लॉक में निहित है, जैसा कि नीचे दिखाया गया है।
यहाँ v (X के तत्वों की संख्या, जिसे बिंदु कहा जाता है), b (ब्लॉक की संख्या), k, r, और λ संरचना के पैरामीटर हैं। (पतित उदाहरणों से बचने के लिए, यह भी माना जाता है कि v > k, ताकि किसी भी ब्लॉक में समुच्चय के सभी तत्व सम्मिलित न हों। इन संरचनाों के नाम में अपूर्णता का यही अर्थ है।) तालिका में:
v अंक, x के तत्वों की संख्या b ब्लॉक की संख्या r दिए गए बिंदु वाले ब्लॉकों की संख्या k ब्लॉक में अंकों की संख्या λ किसी भी 2 (या अधिक सामान्यतः t) अलग-अलग बिंदुओं वाले ब्लॉक की संख्या
संरचना को a (v, k, λ)-संरचना या a (v, b, r, k, λ)-संरचना कहा जाता है। पैरामीटर सभी स्वतंत्र नहीं हैं; v, k, और λ b और r निर्धारित करते हैं, और v, k, और λ के सभी संयोजन संभव नहीं हैं। इन मापदंडों को जोड़ने वाले दो मूलभूत समीकरण हैं
- जोड़े (B, p) की संख्या की गणना करके प्राप्त किया गया जहां b ब्लॉक है और p उस ब्लॉक में बिंदु है, और
निश्चित x के लिए गिनने से प्राप्त ट्रिपल (x, y, B) जहां x और y अलग-अलग बिंदु हैं और B ऐसा ब्लॉक है जिसमें ये दोनों सम्मिलित हैं। प्रत्येक x के लिए यह समीकरण यह भी सिद्ध करता है कि r स्थिर है (x से स्वतंत्र) भले ही इसे स्पष्ट रूप से ग्रहण न किया गया हो, इस प्रकार यह सिद्ध होता है कि x में कोई भी x r ब्लॉक में समाहित है, यह निरर्थक है और r की गणना अन्य मापदंडों से की जा सकती है।
ये शर्तें पर्याप्त नहीं हैं, उदाहरण के लिए, (43,7,1)-संरचना उपस्थित नहीं है।[4]
2-संरचना का क्रम n = r − λ के रूप में परिभाषित किया गया है। 2-संरचना का 'पूरक' बिंदु समुच्चय X में प्रत्येक ब्लॉक को इसके पूरक के साथ बदलकर प्राप्त किया जाता है। यह 2-संरचना भी है और इसके पैरामीटर v′ = v, b′ = b, r′ = b − r हैं , k′ = v − k, λ′ = λ + b − 2r। 2-संरचना और उसके पूरक का एक ही क्रम है।
मौलिक प्रमेय, फिशर की असमानता, जिसका नाम सांख्यिकीविद् रोनाल्ड फिशर के नाम पर रखा गया है, वह किसी भी 2-संरचना में b ≥ v है।
उदाहरण
अद्वितीय (6,3,2)-संरचना (v = 6, k = 3, λ = 2) में 10 ब्लॉक (b = 10) हैं और प्रत्येक तत्व को 5 बार (r = 5) दोहराया जाता है।[5] प्रतीकों 0 − 5 का उपयोग करते हुए, ब्लॉक निम्नलिखित त्रिगुण हैं:
- 012 013 024 035 045 125 134 145 234 235।
और संबंधित घटना मैट्रिक्स v × b बाइनरी मैट्रिक्स निरंतर पंक्ति योग r और निरंतर स्तंभ योग k के साथ) है:
चार गैर-समरूपी (8,4,3)-संरचनाों में से में 14 ब्लॉक हैं जिनमें प्रत्येक तत्व को 7 बार दोहराया गया है। प्रतीकों 0 − 7 का उपयोग करते हुए ब्लॉक निम्नलिखित 4-ट्यूपल हैं:[5]:
0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456।
अद्वितीय (7,3,1)-संरचना सममित है और इसमें 7 ब्लॉक हैं जिनमें प्रत्येक तत्व को 3 बार दोहराया गया है। प्रतीकों 0 − 6 का उपयोग करते हुए, ब्लॉक निम्नलिखित त्रिक हैं:[5]:
013 026 045 124 156 235 346।
यह संरचना फानो विमान के साथ जुड़ा हुआ है, संरचना फ़ानो प्लेन के तत्वों और ब्लॉकों के साथ # प्लेन के पॉइंट्स और लाइन्स के लिए ब्लॉक संरचना सिद्धांत है। इसके संबंधित घटना मैट्रिक्स भी सममित हो सकते हैं, यदि लेबल या ब्लॉक को सही तरीके से क्रमबद्ध किया गया हो: