सामान्य संख्या। एपिसोड II: डी ब्रूने अटैक

शुभ दोपहर, दयालु फेरीवाले। जैसा कि आप में से कुछ याद कर सकते हैं, पिछली पोस्ट में मैंने यह दिखाने की धमकी दी थी कि एक सामान्य संख्या का निर्माण कैसे किया जाता है, सामान्यता का प्रमाण प्राथमिक साधनों द्वारा किया जा सकता है। दुर्भाग्यवश, मुझे अपने खाते के अनपेक्षित परिवर्तन के कारण इस पोस्ट को एक महीने के लिए लिखने का अवसर नहीं मिला है। हालांकि, अब मैं वापस आ गया हूं, इसलिए बोलना, आराम करना और मैं वादा पूरा करने के लिए आगे बढ़ सकता हूं।

यदि आप जानते हैं कि सामान्य संख्याएं क्या हैं, और आप सोच रहे हैं कि उन्हें कैसे बनाया जाए, तो कृपया मुझे एक बिल्ली दें। यदि आपको पता नहीं है कि सामान्य संख्याएँ क्या हैं, तो पिछला लेख (ऊपर लिंक) पढ़ें, तो कृपया बिल्ली के नीचे आ जाएँ। यदि आप सामान्य संख्या का निर्माण करने के तरीके में रुचि नहीं रखते हैं, तो कृपया इसे वैसे भी काट दें, क्योंकि वहां मैं डी ब्रूने के चक्रों के बारे में बात करूंगा, जो अपने आप में बहुत दिलचस्प चीजें हैं।

निकोलस डी ब्रुने के नाम पर प्रशिक्षित संरचनाओं का सर्कस।

कॉमरेड डी ब्रूने (उर्फ डी ब्रूने, डी ब्रूने, और कभी-कभी डी ब्रूने) भी गॉस और यूलर नहीं हैं, लेकिन व्यक्तित्व भी काफी महत्वपूर्ण है। मेरे बीच, उन्हें कॉम्बिनेटरिक्स और ग्राफ सिद्धांत में अपने परिणामों के लिए जाना जाता है, हालांकि, वे कहते हैं कि वह कुछ और कर रहे थे। हालांकि, इस लेख के ढांचे में, अन्य क्षेत्रों में उनकी उपलब्धियों को निंदनीय रूप से उपेक्षित किया जा सकता है।

कुछ प्राकृतिक मापदंडों n और k के लिए एक डी ब्रुइन चक्र k- संख्या प्रणाली के k ⁿ अंकों का एक चक्रीय अनुक्रम है, जिसमें लंबाई के n के किसी भी संभावित बाद में (अनुक्रम) बिल्कुल एक बार होता है।

अलग-अलग k और n के लिए de Bruyne चक्र के उदाहरणों पर विचार करें।

n = 1, k = 2: अनुक्रम "01" वांछित चक्र होगा, क्योंकि इसमें लंबाई 1 (यानी, शून्य और एक) के सभी संभव बाइनरी अनुक्रम शामिल हैं।
n = 2, k = 2: अनुक्रम "0110" हमें सूट करता है। आज्ञा दें की जाँच करें: इसमें बाद में "01", "11", "10" और चक्रीय प्रकृति के कारण, "00" शामिल हैं। ये लंबाई 2 के सभी संभव द्विआधारी अनुक्रम हैं।
n = 3, k = 10:
सामान्य तौर पर, यहां, उदाहरण के लिए , किसी भी पैरामीटर के लिए एक ऑनलाइन डी ब्रुइन चक्र जनरेटर है जो बहुत बड़े नहीं हैं।

अफवाहों के अनुसार, डी ब्रुइन चक्रों के उपयोग से ब्रूट फोर्स के समय को कम किया जा सकता है यदि डिवाइस को तोड़ा जा रहा है, तो पिन कोड के रूप में एन अंतिम दर्ज किए गए वर्णों का उपयोग करता है। बदले में सभी k ⁿ संभव कोड दर्ज करने के बजाय (जो n * k ⁿ वर्ण देगा), आप एक छोटे से "पूंछ" (n - 1 वर्ण) को बंद करने के लिए कुछ de Bruyne चक्र (जो k ⁿ वर्ण देगा) के अंकों के अनुक्रम में प्रवेश कर सकते हैं। चक्र)। कुल समय लाभ लगभग n गुना है। हालांकि, मैं ऐसे उपकरणों से कभी नहीं मिला, इसलिए मेरे लिए यह सिर्फ एक अफवाह है। यदि आपको इस बारे में कुछ कहना है, तो कृपया टिप्पणियों में सदस्यता समाप्त करें, मुझे इसमें रुचि होगी।

पहला सवाल जो एक गणितज्ञ के ऊपर पढ़ने के बाद होना चाहिए: "क्या k और n के लिए कोई डे ब्रूने चक्र मौजूद है?" पहला सवाल जो एक प्रोग्रामर को उठाना चाहिए: "k और n के लिए डे ब्रूने चक्र कैसे उत्पन्न हो सकता है? »इन दोनों सवालों के जवाब के लिए, हम एक नई परिभाषा पेश करते हैं।

प्राकृतिक मानकों k और n के लिए de Bruyne ग्राफ एक ऐसा अभिमुख ग्राफ़ है, जिसके कोने सभी संभव n-अंक k-ary क्रमों के अनुरूप हैं, और किनारे उन और केवल उन जोड़ियों को जोड़ते हैं जिनके लिए पहले नंबर के अंतिम n-1 अंक पहले n- के साथ मेल खाते हैं दूसरे नंबर का 1 अंक।

जाहिर है, अगर हम इस ग्राफ में हैमिल्टनियन चक्र पाते हैं (यानी, इसके किनारों के साथ एक बंद रास्ता, जो प्रत्येक शीर्ष पर ठीक एक बार गुजरता है), तो हम उसी मानकों k और n के लिए de Bruyne चक्र पाएंगे (इसके बाद, हम संक्षिप्त नोटेशन का उपयोग करते हैं। बी (के, एन)), और इसके विपरीत। वास्तव में, डी ब्रूने चक्र है, संक्षेप में, सभी प्रकार के एन-वैल्यूएशन अनुक्रमों के "ग्लूइंग" उनके सामान्य (एन -1) -वास्तविकता के अनुसार। हालाँकि, ग्राफ डी ब्रुइन में हैमिल्टनियन चक्र "ग्लूइंग" का एक ऐसा तरीका प्रदान करता है।



इस प्रकार, हमने प्रोग्रामर के प्रश्न का उत्तर दिया। यदि B (k, n) मौजूद है, तो हम इसे संबंधित ग्राफ पर उपयुक्त एल्गोरिदम के साथ पा सकते हैं। हालांकि, गणितज्ञ संतुष्ट नहीं है। हैमिल्टनियन चक्र का अस्तित्व पूरी तरह से गैर-स्पष्ट चीज है, जिसका अर्थ है कि यह स्पष्ट नहीं है कि बी (के, एन) मौजूद है या नहीं । गणितज्ञ के लिए सौभाग्य से, काउंट डी ब्रूने की एक और उल्लेखनीय संपत्ति है: प्रत्येक ईयूलर (यानी, सभी किनारों से गुजरते हुए) एक चक्र कुछ डी ब्रुइन चक्र बी (के, एन + 1) से मेल खाता है। वास्तव में, ग्राफ डी ब्रूने का प्रत्येक किनारा "सरेस से जोड़ा हुआ" एन-वैल्यू सीक्वेंस है, जिसे एक (एन + 1) के रूप में व्याख्या किया जा सकता है। यदि एक किनारा उस शीर्ष पर प्रवेश करता है जिसमें से दूसरा निकलता है, तो इसका मतलब है कि इन किनारों के अनुरूप (n + 1) -वायु क्रमबद्ध हैं जो इस शीर्ष के अनुरूप सामान्य n-अंक अनुक्रम के साथ "चिपके" हैं।

यूलर चक्र का अस्तित्व एक अच्छी तरह से अध्ययन किया गया मुद्दा है; यूलर चक्र की उपस्थिति का मानदंड पाया जा सकता है, उदाहरण के लिए, विकिपीडिया पर :

एक निर्देशित ग्राफ में एक यूलर चक्र होता है यदि और केवल अगर यह कसकर जुड़ा हुआ है और ग्राफ़ के प्रत्येक शीर्ष के लिए इसकी अर्ध-डिग्री प्रविष्टि के बराबर है, तो इसके अर्ध-डिग्री परिणाम के बराबर है, अर्थात इसके किनारों के रूप में कई किनारे प्रवेश करते हैं।

मजबूत कनेक्टिविटी तब होती है जब एक निर्देशित ग्राफ में किसी भी जोड़ के लिए हम किनारों से, और इसके विपरीत एक से दूसरे तक पहुंच सकते हैं। दृष्टिकोण की अर्ध-डिग्री यह है कि कितने किनारे शीर्ष में प्रवेश करते हैं। परिणाम की अर्ध-डिग्री, तदनुसार, कितने किनारों से निकलती है। मैं पाठक को स्वतंत्र रूप से यह साबित करने के लिए आमंत्रित करता हूं कि ग्राफ डी ब्रुइन एक यूलर चक्र के अस्तित्व के लिए स्थिति को संतुष्ट करता है। गंभीरता से, यदि आपके पास खाली समय है जिसे लेने के लिए आपके पास कुछ भी नहीं है, तो टिप्पणियों में प्रमाण लिखें।

कहते हैं न कि ग्राफोमेनिया

फिर भी, ग्राफ़ एल्गोरिदम का उपयोग करते हुए डी ब्रुइन चक्रों की तलाश करना बहुत सुविधाजनक नहीं है, और यह थोड़ा पापपूर्ण है। इन छोरों के निर्माण के लिए अधिक कुशल तरीके हैं। यहां मैं उनमें से एक के बारे में बात करूंगा: हार का उपयोग करना। सबसे जिज्ञासु मूल लेख पढ़ सकता है, लेकिन मैं सब कुछ संक्षेप में और सबूत के बिना समझाऊंगा।

एक हार एक परिमित अनुक्रम है जिसे चक्रीय पारी तक माना जाता है। यही है, "1100", "1001", "0011" एक ही हार के विभिन्न रिकॉर्ड हैं। कई दिलचस्प कॉम्बिनेटरियल परिणाम हार के साथ जुड़े हुए हैं, लेकिन अब हम उनके द्वारा विचलित नहीं होंगे।

हम हार के प्रतिनिधि को रिकॉर्ड करेंगे जो लेक्सिकोग्राफ़िक क्रम में अन्य सभी प्रविष्टियों से पहले आता है। पिछले उदाहरण से हार को चार तरीकों से लिखा जा सकता है: "1100", "1001", "0011", "0110"। इनमें से "0011" रिकॉर्ड "वर्णानुक्रम में" जाने वाला पहला है, यह प्रतिनिधि होगा।

किसी अनुक्रम की आवधिक कमी इसकी सबसे छोटी अनुगामी होती है, जैसे कि मूल अनुक्रम में कई पुनरावृत्तियाँ होती हैं। उदाहरण के लिए, "0101" दो बार दोहराया गया है, इसलिए बाद में "01" अनुक्रम की एक आवधिक कमी है "0101"। अनुक्रम "0000" की आवधिक कमी बाद में "0" होगी। अधिकांश अनुक्रमों को कुछ छोटे "टुकड़े" की पुनरावृत्ति के रूप में प्रस्तुत नहीं किया जा सकता है, इसलिए उनके आवधिक कटौती खुद के साथ मेल खाती हैं।

अब, इन अवधारणाओं को तैयार करने के बाद, मैं हार का उपयोग करके B (k, n) के निर्माण के लिए एक एल्गोरिथ्म लिख सकता हूं:

1. लंबाई n के सभी संभव k- हार लें;
2. उनमें से प्रत्येक के लिए हम एक प्रतिनिधि का चयन करते हैं;
3. हम शाब्दिक आदेश में प्रतिनिधियों को लिखते हैं;
4. प्रत्येक प्रतिनिधि को आवधिक कमी द्वारा प्रतिस्थापित किया जाता है;
5. ???
6. हमने बी (के, एन) का निर्माण किया।

हम इस एल्गोरिथ्म को बी (2,3) के उदाहरण पर आजमाएंगे। हमारे पास तीन लंबाई के केवल चार बाइनरी हार हैं: सभी लोगों से, सभी शून्य से, एक शून्य और दो शून्य से। उनके प्रतिनिधि क्रमशः "111", "000", "001", "011" होंगे। उन्हें वर्णानुक्रम में क्रमबद्ध करें: "000", "001", "011", "111"। समय-समय पर कमी के बाद हमें "0", "001", "011", "1" मिलता है। इन चार बाइनरी शब्दों का संयोजन - "00010111" - बिल्कुल बी (2,3) होगा। आप इसकी जांच कर सकते हैं, आप मेरी बातों पर विश्वास कर सकते हैं।

वापस हमारे मेढ़े

तो, एक सामान्य संख्या का निर्माण। यह पैराग्राफ बहुत छोटा होगा। B '(k, n) अनुक्रम B (k, n) के द्वारा निरूपित करें, जिसमें इसके पहले n-1 वर्ण दाईं ओर जोड़े गए हैं। यह अच्छा है कि हर n-अंक k-ary अनुक्रम को इसमें शामिल किया जाता है, ठीक एक बार चक्रीयता को ध्यान में रखे बिना । एक k-ary संख्या का निर्माण करने के लिए, जिस सामान्यता के बारे में कोई संदेह नहीं है, हम असीम संघटन को उसके भिन्नात्मक भाग के रिकॉर्ड के रूप में लेते हैं: B '(k, 1) + B' (k, 2) + ... + '(k, n) + ...

सिद्धांत रूप में, यह पद पूरा हो सकता था, लेकिन सिर्फ मामले में, मैं समझाता हूं। लंबाई m के किसी भी क्रम को B '(k, n), n with m में शामिल किया गया है, लंबाई M के किसी भी अन्य अनुक्रम के समान आवृत्ति के साथ। यह वही है जो आपको एक सामान्य संख्या के लिए चाहिए। इसके विपरीत, आवृत्ति में त्रुटियां या तो n <m के लिए उत्पन्न हो सकती हैं (और यह परिमित लंबाई का एक प्रारंभिक टुकड़ा है, यह स्पर्शोन्मुख घनत्व को प्रभावित नहीं कर सकता है), या डी ब्रुइन चक्रों के बीच "जोड़ों" पर।

चूँकि n की लम्बाई बढ़ने से B '(k, n) तेजी से बढ़ता है, जोड़ों की विषमता शून्य होती है, जिसका अर्थ है कि जोड़ों को हमारे अनुक्रम के स्पर्शोन्मुख घनत्व को भी प्रभावित नहीं किया जा सकता है। निष्कर्ष: किसी भी n के लिए हमने जो संख्या बनाई है, उसके रिकॉर्ड में, लंबाई n के सभी क्रम एक ही विषम घनत्व के साथ मिलेंगे। यह एक सामान्य संख्या की परिभाषा है। आप "चीयर्स" चिल्ला सकते हैं और हवा में बोनट फेंक सकते हैं: प्रमेय साबित हो गया है।