ब्रुइज़न टोरस: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Array containing every possible matrix of size m × n}} File:de_bruijn_torus_3x3.stl|thumb|250px|लिंक=http://viewstl.com/classic/?embedded&url=ht...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Array containing every possible matrix of size m × n}} | {{Short description|Array containing every possible matrix of size m × n}} | ||
[[File:de_bruijn_torus_3x3.stl|thumb|250px | [[File:de_bruijn_torus_3x3.stl|thumb|250px|STL (फ़ाइल स्वरूप) डी ब्रुइज़न टोरस का मॉडल {{math|(16,32;3,3){{sub|2}}}} 1s को पैनल के रूप में और 0s को जाल में छेद के रूप में - सुसंगत अभिविन्यास के साथ, प्रत्येक {{math|3×3}} आव्यूह बिल्कुल एक बार दिखाई देता है]] | ||
डी | |||
संयुक्त गणित में, एक डी ब्रुइज़न टोरस, जिसका नाम डच गणितज्ञ निकोलस गोवर्ट डी ब्रुइज़न के नाम पर रखा गया है, एक वर्णमाला ( अधिकांशतः केवल 0 और 1) से प्रतीकों की एक सरणी है जिसमें दिए गए आयाम {{math|''m'' × ''n''}} के हर संभावित आव्यूह को एक बार में सम्मिलित किया जाता है। यह एक टोरस है क्योंकि आव्यूह खोजने के उद्देश्य से किनारों को रैपराउंड माना जाता है। इसका नाम डी ब्रुइज़न अनुक्रम से आया है, जिसे एक विशेष स्थिति माना जा सकता है जहां {{math|1=''n'' = 1}} (एक आयाम)। | |||
{{mvar|n }} | |||
डी ब्रुइज़न टोरी के संबंध में मुख्य विवर्त प्रश्नों में से एक यह है कि क्या किसी विशेष वर्णमाला आकार के लिए डी ब्रुइज़न टोरस का निर्माण किसी दिए गए {{mvar|m}} और {{mvar|n}} के लिए किया जा सकता है। यह ज्ञात है कि ये सदैव तब उपस्थित होते हैं जब {{math|1=''n'' = 1}} होता है, तब से हमें बस डी ब्रुइज़न अनुक्रम मिलते हैं, जो सदैव उपस्थित रहते हैं। यह भी ज्ञात है कि "वर्ग" टोरी तब उपस्थित होती है जब {{math|1=''m'' = ''n''}} और सम (विषम स्थिति के लिए परिणामी टोरी वर्गाकार नहीं हो सकती)।<ref> | |||
{{cite journal| | {{cite journal| | ||
title=On de Bruijn arrays.| | title=On de Bruijn arrays.| | ||
| Line 26: | Line 31: | ||
doi-access=free}} | doi-access=free}} | ||
</ref><ref>{{cite journal|title=ग्रे कोड और सार्वभौमिक चक्रों पर अनुसंधान समस्याएं|author1=Jackson|first1=Brad|last2=Stevens|first2=Brett|last3=Hurlbert|first3=Glenn|journal=Discrete Mathematics|volume=309|issue=17|date=Sep 2009|pages=5341–5348|doi=10.1016/j.disc.2009.04.002|doi-access=free}}</ref> | </ref><ref>{{cite journal|title=ग्रे कोड और सार्वभौमिक चक्रों पर अनुसंधान समस्याएं|author1=Jackson|first1=Brad|last2=Stevens|first2=Brett|last3=Hurlbert|first3=Glenn|journal=Discrete Mathematics|volume=309|issue=17|date=Sep 2009|pages=5341–5348|doi=10.1016/j.disc.2009.04.002|doi-access=free}}</ref> | ||
== | सबसे छोटा संभव बाइनरी "स्क्वायर" डी ब्रुइज़न टोरस, ऊपर दाईं ओर दर्शाया गया है, जिसे {{math|(4,4;2,2){{sub|2}}}} डी ब्रुइज़न टोरस (या बस {{math|''B''{{sub|2}}}}) के रूप में दर्शाया गया है, इसमें सभी {{math|2×2}} बाइनरी आव्यूह सम्मिलित हैं। | ||
[[File:2-2-4-4-de-Bruijn-torus.svg|thumb|upright|(4,4;2,2) डी ब्रुइज़न टोरस। प्रत्येक 2-बाय-2 बाइनरी | |||
=={{math|''B''{{sub|2}}}}== | |||
[[File:2-2-4-4-de-Bruijn-torus.svg|thumb|upright|(4,4;2,2) डी ब्रुइज़न टोरस। प्रत्येक 2-बाय-2 बाइनरी आव्यूह को इसके भीतर ठीक एक बार पाया जा सकता है।]] | |||
"अनुवाद", "व्युत्क्रम " (0s और 1s का आदान-प्रदान) और "घूर्णन " (90 डिग्री तक) के अतिरिक्त , कोई अन्य (4,4;2,2)2 डी ब्रुइज़न टोरी संभव नहीं है - यह सभी 216 बाइनरी आव्यूह (या 0s और 1s की समान संख्या जैसे उपसमुच्चय पूर्ति बाधाओं) के पूर्ण निरीक्षण द्वारा दिखाया जा सकता है।<ref> | |||
{{cite journal|title=The Binatorix B2.|author1=Eggen|first1=Bernd R.|journal=Private communication|year=1990}} | {{cite journal|title=The Binatorix B2.|author1=Eggen|first1=Bernd R.|journal=Private communication|year=1990}} | ||
</ref> | </ref> | ||
[[File:de_bruijn_torus_3x2.svg|thumb|upright|डी ब्रुइज़न टोरस (8,8;3,2) जिसमें सभी 64 संभावित 3-पंक्ति × 2-कॉलम | [[File:de_bruijn_torus_3x2.svg|thumb|upright|डी ब्रुइज़न टोरस (8,8;3,2) जिसमें सभी 64 संभावित 3-पंक्ति × 2-कॉलम आव्यूह ठीक एक बार सम्मिलित हैं, रैपअराउंड के साथ - निचला आधा शीर्ष आधे का नकारात्मक है]] | ||
n−1 पंक्तियों और स्तंभों को दोहराकर टोरस को अनियंत्रित किया जा सकता है। बिना रैपराउंड के सभी n×n सबमैट्रिस, जैसे कि एक छायांकित पीला, फिर पूरा समुच्चय बनाते हैं: | |||
:{| class="wikitable" | :{| class="wikitable" | ||
| 1 || style="background:#ccc;"|0 || 1 || 1 || rowspan="5" style="border-left:solid; padding:0;"| || 1 | | 1 || style="background:#ccc;"|0 || 1 || 1 || rowspan="5" style="border-left:solid; padding:0;"| || 1 | ||
| Line 46: | Line 58: | ||
==बड़ा उदाहरण: | ==बड़ा उदाहरण: ''B''<sub>4</sub>== | ||
[[File:Visualisation of a (256,256;4,4) 2 de Bruijn torus.svg|thumb|right|260px|B<sub>4</sub> एक बाइनरी वर्ग | [[File:Visualisation of a (256,256;4,4) 2 de Bruijn torus.svg|thumb|right|260px|B<sub>4</sub> एक बाइनरी वर्ग आव्यूह के रूप में<br>ग्रिड 4×4 आव्यूह में से कुछ को हाइलाइट करता है, जिसमें ऊपरी मार्जिन पर [[शून्य मैट्रिक्स|शून्य]] आव्यूह और आव्यूह सम्मिलित हैं।]]अगले संभावित बाइनरी स्क्वायर डी ब्रुइज़न टोरस का एक उदाहरण, {{math|1=(256,256;4,4)<sub>2</sub>}} (संक्षिप्त रूप में ''B''<sub>4</sub>), स्पष्ट रूप से निर्मित किया गया है।<ref> | ||
{{cite journal|title=Decoding de Bruijn arrays constructed by the FFMS method.|author1=Shiu|first1=Wai-Chee|journal=Ars Combinatoria|volume=47|issue=17|year=1997|pages=33–48}} | {{cite journal|title=Decoding de Bruijn arrays constructed by the FFMS method.|author1=Shiu|first1=Wai-Chee|journal=Ars Combinatoria|volume=47|issue=17|year=1997|pages=33–48}} | ||
</ref> | </ref> | ||
जिस पेपर में {{math|1=(256,256;4,4)<sub>2</sub>}} डी ब्रुइजन टोरस का एक उदाहरण बनाया गया था, उसमें कम फ़ॉन्ट आकार के अतिरिक्त , बाइनरी के 10 से अधिक पृष्ठ सम्मिलित थे, जिसमें सरणी की प्रति पंक्ति तीन पंक्तियों की आवश्यकता होती थी। | |||
==बड़े आकार की बाइनरी डी ब्रुइज़न टोरी== | ==बड़े आकार की बाइनरी डी ब्रुइज़न टोरी== | ||
जिस पेपर में {{math|1=(256,256;4,4)<sub>2</sub>}} डी ब्रुइजन टोरस का एक उदाहरण बनाया गया था, उसमें कम फ़ॉन्ट आकार के अतिरिक्त , बाइनरी के 10 से अधिक पृष्ठ सम्मिलित थे, जिसमें सरणी की प्रति पंक्ति तीन पंक्तियों की आवश्यकता होती थी। | |||
बाद में संभावित बाइनरी डी ब्रुइज़न टोरस, जिसमें सभी बाइनरी | बाद में संभावित बाइनरी डी ब्रुइज़न टोरस, जिसमें सभी बाइनरी सम्मिलित हैं {{math|1=6×6}} मैट्रिसेस, होगा {{math|1=2<sup>36</sup> = 68,719,476,736}} प्रविष्टियाँ, आयाम की एक वर्गाकार सरणी उत्पन्न करती हैं {{math|1=262,144×262,144}}, निरूपित ए {{math|1=(262144,262144;6,6)<sub>2</sub>}} डी ब्रुइज़न टोरस या बस ''B''<sub>6</sub>. इसे सरलता से कंप्यूटर पर संग्रहीत किया जा सकता है - यदि 0.1 मिमी किनारे के पिक्सेल के साथ मुद्रित किया जाता है, तो ऐसे आव्यूह को लगभग 26×26 [[वर्ग मीटर]] के क्षेत्र की आवश्यकता होगी। | ||
वस्तु | वस्तु ''B''<sub>8</sub>, जिसमें सभी बाइनरी 8×8 आव्यूह सम्मिलित हैं और {{math|1=(4294967296,4294967296;8,8)<sub>2</sub>}} दर्शाया गया है, में कुल 2<sup>64</sup> ≈ 18.447×10<sup>18</sup> प्रविष्टियाँ हैं: ऐसे आव्यूह को संग्रहीत करने के लिए 18.5 एक्साबिट्स, या 2.3 एक्साबाइट स्टोरेज की आवश्यकता होगी। उपरोक्त मापदंड पर, यह 429×429 वर्ग किलोमीटर को कवर करेगा। | ||
निम्न तालिका सुपर-घातीय वृद्धि को दर्शाती है। | निम्न तालिका सुपर-घातीय वृद्धि को दर्शाती है। | ||
{| class="wikitable" style="text-align:right;line-height:1;" | {| class="wikitable" style="text-align:right;line-height:1;" | ||
! ''n'' | ! ''n'' | ||
! | ! कोशिकाओं में | ||
! | सबमैट्रिक्स | ||
! ''B<sub>n</sub>'' | |||
= ''n''<sup>2</sup> | |||
! 2<sup>''n''<sup>2</sup></sup> की संख्या | |||
उपमैट्रिस | |||
!''B<sub>n</sub>'' पक्ष | |||
लंबाई | |||
= 2<sup>(''n''2/2)</sup> | |||
|- | |- | ||
| 2 || 4 || 16 || 4 | | 2 || 4 || 16 || 4 | ||
Revision as of 15:30, 24 July 2023
संयुक्त गणित में, एक डी ब्रुइज़न टोरस, जिसका नाम डच गणितज्ञ निकोलस गोवर्ट डी ब्रुइज़न के नाम पर रखा गया है, एक वर्णमाला ( अधिकांशतः केवल 0 और 1) से प्रतीकों की एक सरणी है जिसमें दिए गए आयाम m × n के हर संभावित आव्यूह को एक बार में सम्मिलित किया जाता है। यह एक टोरस है क्योंकि आव्यूह खोजने के उद्देश्य से किनारों को रैपराउंड माना जाता है। इसका नाम डी ब्रुइज़न अनुक्रम से आया है, जिसे एक विशेष स्थिति माना जा सकता है जहां n = 1 (एक आयाम)।
n
डी ब्रुइज़न टोरी के संबंध में मुख्य विवर्त प्रश्नों में से एक यह है कि क्या किसी विशेष वर्णमाला आकार के लिए डी ब्रुइज़न टोरस का निर्माण किसी दिए गए m और n के लिए किया जा सकता है। यह ज्ञात है कि ये सदैव तब उपस्थित होते हैं जब n = 1 होता है, तब से हमें बस डी ब्रुइज़न अनुक्रम मिलते हैं, जो सदैव उपस्थित रहते हैं। यह भी ज्ञात है कि "वर्ग" टोरी तब उपस्थित होती है जब m = n और सम (विषम स्थिति के लिए परिणामी टोरी वर्गाकार नहीं हो सकती)।[1][2][3]
सबसे छोटा संभव बाइनरी "स्क्वायर" डी ब्रुइज़न टोरस, ऊपर दाईं ओर दर्शाया गया है, जिसे (4,4;2,2)2 डी ब्रुइज़न टोरस (या बस B2) के रूप में दर्शाया गया है, इसमें सभी 2×2 बाइनरी आव्यूह सम्मिलित हैं।
B2
"अनुवाद", "व्युत्क्रम " (0s और 1s का आदान-प्रदान) और "घूर्णन " (90 डिग्री तक) के अतिरिक्त , कोई अन्य (4,4;2,2)2 डी ब्रुइज़न टोरी संभव नहीं है - यह सभी 216 बाइनरी आव्यूह (या 0s और 1s की समान संख्या जैसे उपसमुच्चय पूर्ति बाधाओं) के पूर्ण निरीक्षण द्वारा दिखाया जा सकता है।[4]
n−1 पंक्तियों और स्तंभों को दोहराकर टोरस को अनियंत्रित किया जा सकता है। बिना रैपराउंड के सभी n×n सबमैट्रिस, जैसे कि एक छायांकित पीला, फिर पूरा समुच्चय बनाते हैं:
1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 1 1
बड़ा उदाहरण: B4
_2_de_Bruijn_torus.svg)
B4 एक बाइनरी वर्ग आव्यूह के रूप में
ग्रिड 4×4 आव्यूह में से कुछ को हाइलाइट करता है, जिसमें ऊपरी मार्जिन पर शून्य आव्यूह और आव्यूह सम्मिलित हैं।
ग्रिड 4×4 आव्यूह में से कुछ को हाइलाइट करता है, जिसमें ऊपरी मार्जिन पर शून्य आव्यूह और आव्यूह सम्मिलित हैं।
अगले संभावित बाइनरी स्क्वायर डी ब्रुइज़न टोरस का एक उदाहरण, (256,256;4,4)2 (संक्षिप्त रूप में B4), स्पष्ट रूप से निर्मित किया गया है।[5]
जिस पेपर में (256,256;4,4)2 डी ब्रुइजन टोरस का एक उदाहरण बनाया गया था, उसमें कम फ़ॉन्ट आकार के अतिरिक्त , बाइनरी के 10 से अधिक पृष्ठ सम्मिलित थे, जिसमें सरणी की प्रति पंक्ति तीन पंक्तियों की आवश्यकता होती थी।
बड़े आकार की बाइनरी डी ब्रुइज़न टोरी
जिस पेपर में (256,256;4,4)2 डी ब्रुइजन टोरस का एक उदाहरण बनाया गया था, उसमें कम फ़ॉन्ट आकार के अतिरिक्त , बाइनरी के 10 से अधिक पृष्ठ सम्मिलित थे, जिसमें सरणी की प्रति पंक्ति तीन पंक्तियों की आवश्यकता होती थी।
बाद में संभावित बाइनरी डी ब्रुइज़न टोरस, जिसमें सभी बाइनरी सम्मिलित हैं 6×6 मैट्रिसेस, होगा 236 = 68,719,476,736 प्रविष्टियाँ, आयाम की एक वर्गाकार सरणी उत्पन्न करती हैं 262,144×262,144, निरूपित ए (262144,262144;6,6)2 डी ब्रुइज़न टोरस या बस B6. इसे सरलता से कंप्यूटर पर संग्रहीत किया जा सकता है - यदि 0.1 मिमी किनारे के पिक्सेल के साथ मुद्रित किया जाता है, तो ऐसे आव्यूह को लगभग 26×26 वर्ग मीटर के क्षेत्र की आवश्यकता होगी।
वस्तु B8, जिसमें सभी बाइनरी 8×8 आव्यूह सम्मिलित हैं और (4294967296,4294967296;8,8)2 दर्शाया गया है, में कुल 264 ≈ 18.447×1018 प्रविष्टियाँ हैं: ऐसे आव्यूह को संग्रहीत करने के लिए 18.5 एक्साबिट्स, या 2.3 एक्साबाइट स्टोरेज की आवश्यकता होगी। उपरोक्त मापदंड पर, यह 429×429 वर्ग किलोमीटर को कवर करेगा।
निम्न तालिका सुपर-घातीय वृद्धि को दर्शाती है।
| n | कोशिकाओं में
सबमैट्रिक्स = n2 |
2n2 की संख्या
उपमैट्रिस |
Bn पक्ष
लंबाई = 2(n2/2) |
|---|---|---|---|
| 2 | 4 | 16 | 4 |
| 4 | 16 | 65 536 | 256 |
| 6 | 36 | 68 719 476 736 | 262 144 |
| 8 | 64 | ~1.84×1019 | ~4.29×109 |
| 10 | 100 | ~1.27×1030 | ~1.13×1015 |
| 12 | 144 | ~2.23×1043 | ~4.72×1021 |
| 14 | 196 | ~1.00×1059 | ~3.17×1029 |
| 16 | 256 | ~1.16×1077 | ~3.40×1038 |
| 18 | 324 | ~3.42×1097 | ~5.85×1048 |
| 20 | 400 | ~2.60×10120 | ~1.61×1060 |
यह भी देखें
- डी ब्रुइन अनुक्रम
- डी ब्रुइन ग्राफ
संदर्भ
- ↑ Fan, C. T.; Fan, S. M.; Ma, S. L.; Siu, M. K. (1985). "On de Bruijn arrays". Ars Combinatoria A. 19: 205–213.
- ↑ Chung, F.; Diaconis, P.; Graham, R. (1992). "Universal cycles for combinatorial structures". Discrete Mathematics. 110 (1): 43–59. doi:10.1016/0012-365x(92)90699-g.
- ↑ Jackson, Brad; Stevens, Brett; Hurlbert, Glenn (Sep 2009). "ग्रे कोड और सार्वभौमिक चक्रों पर अनुसंधान समस्याएं". Discrete Mathematics. 309 (17): 5341–5348. doi:10.1016/j.disc.2009.04.002.
- ↑ Eggen, Bernd R. (1990). "The Binatorix B2". Private communication.
- ↑ Shiu, Wai-Chee (1997). "Decoding de Bruijn arrays constructed by the FFMS method". Ars Combinatoria. 47 (17): 33–48.
