ग्रे कोड और गणना कार्य

यह लेख निम्नलिखित प्रश्नों और कार्यों का एक उदाहरण के रूप में एल्गोरिदम को संकलित करने के लिए एक गणितीय दृष्टिकोण दिखाएगा:

• ग्रे के बाइनरी कोड। उनका अस्तित्व। न्यूनतम परिवर्तन के क्रम में दिए गए सेट के सबसेट की गणना।
• न्यूनतम परिवर्तन के क्रम में कश्मीर तत्वों के सबसेट की गणना का अस्तित्व और कार्यान्वयन।

तो चलिए शुरू करते हैं।

ग्रे बाइनरी कोड

क्रम n का एक ग्रे बाइनरी कोड सभी का एक क्रम है n- बिट कोड, जिसमें किसी भी दो पड़ोसी कोड एक बिट में बिल्कुल भिन्न होते हैं।

आदेश 2 के ग्रे कोड का एक उदाहरण:

• 00
• 01
• 11
• 10

यह नोटिस करना आसान है कि ऐसा अनुक्रम केवल एक ही नहीं है (यह कम से कम उलट हो सकता है)। इसलिए, आइए अन्य आदेशों के ग्रे बाइनरी कोड के अस्तित्व को देखें और एक ही समय में आगे के काम के लिए इस तरह के अनुक्रमों का चयन करें।

अस्तित्व

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

इस तरह से प्राप्त ग्रे कोड को परावर्तक या सममित रूप से परावर्तित कहा जाता है। भविष्य में, हम ग्रे रिफ्लेक्टिव बाइनरी कोड पर विचार करेंगे।

एक अभ्यास के रूप में, क्रमांक 3 में दिए गए फॉर्मूले का उपयोग करते हुए क्रमिक रूप से परिलक्षित ग्रे कोड्स लिखें: ।

अब हम कॉम्बिनेटरिक्स की कुछ समस्याओं को हल करने के लिए ग्रे कोड के आवेदन पर आगे बढ़ते हैं।

न्यूनतम परिवर्तन के क्रम में दिए गए सेट के सबसेट की गणना

निम्नलिखित समस्या पर विचार करें: “ n तत्वों के समूह को देखते हुए। इसके सभी उपसमुच्चय को इस तरह प्रदर्शित करना आवश्यक है कि प्रत्येक बाद के उपसमुच्चय को पिछले एक से हटाकर या ठीक एक तत्व (जो कि न्यूनतम परिवर्तन के क्रम में हो) जोड़कर प्राप्त किया जाता है। "

हम मानते हैं कि हमारे सेट के तत्व 1 से n तक गिने जाते हैं। फिर, सेट के किसी भी तत्व को n- बिट बाइनरी कोड के साथ जोड़ा जा सकता है: यदि सेट में i- th तत्व को शामिल किया गया है, तो i- th बिट कोड एक है, अन्यथा शून्य। इस प्रकार, सभी सबसेट की गणना को n के बाइनरी कोड की गणना के लिए कम किया जाता है, और न्यूनतम परिवर्तन के क्रम में सबसेट की गणना को बाइनरी ग्रे कोड की गणना के लिए किया जाता है।

ग्रे कोड के लिए एक पुनरावर्ती गणन एल्गोरिथ्म का विचार निश्चित रूप से उनके अस्तित्व के प्रमाण से अनुसरण करता है, अर्थात्, इसमें दी गई पुनरावृत्ति ।

दरअसल, जैसा कि प्रमाण में कहा गया है, ऑर्डर एन -1 का ग्रे कोड ऑर्डर एन -1 के ग्रे कोड से बाईं ओर शून्य असाइन किया गया है (यह एक फ़ंक्शन कॉल से मेल खाती है और इसके सामने असाइनमेंट) और ग्रे के रिवर्स कोड ऑफ ऑर्डर n-1 को बाईं ओर एक यूनिट असाइन करके (यह एक फ़ंक्शन कॉल से मेल खाती है और उसके सामने असाइनमेंट)।

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

एक अभ्यास के रूप में, पाठक को निम्न, संक्षिप्त पुनरावर्ती खोज एल्गोरिदम का विश्लेषण करने के लिए आमंत्रित किया जाता है।


मैं एक पुनरावृत्त खोज एल्गोरिथ्म के अस्तित्व और ग्रे कोड के अन्य उपयोगी गुणों के बारे में भी कहना चाहूंगा, जिन्हें इस लेख में नहीं माना गया है, और जिन्हें अन्य स्रोतों से सीखा जा सकता है, उदाहरण के लिए विकिपीडिया।

अब चलते हैं आखिरी और सबसे दिलचस्प काम पर।

न्यूनतम परिवर्तन के क्रम में k तत्वों के सबसेट की गणना।

आइए समस्या के कथन से शुरू करें: “ n तत्वों का एक समूह दिया गया है। इसके सभी उपसमुच्चय को वास्तव में k तत्वों से युक्त इस तरह से कटौती करने की आवश्यकता है कि प्रत्येक बाद के उपसमुच्चय को पिछले एक से बिल्कुल एक तत्व (यानी, न्यूनतम परिवर्तन के क्रम में) को बदलकर प्राप्त किया जाए। "

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

हम कुछ संकेतन प्रस्तुत करते हैं:

• क्या चरित्र x ( m समय) को समेटकर और वर्ण y ( k गुणा) को प्राप्त करके स्ट्रिंग प्राप्त की जाती है। एक उदाहरण: ।
• K इकाइयों के साथ सभी n- बिट कोड का अनुक्रम है, जिसमें कोड उस क्रम में जाते हैं जिसमें वे अनुक्रम में स्थित होते हैं ।
• K इकाइयों के साथ सभी n- बिट कोड का अनुक्रम है, जिसमें कोड उस क्रम में जाते हैं जिसमें वे अनुक्रम में स्थित होते हैं ।

लेम्मा

पहले बाइनरी कोड के साथ अनुक्रम में इकाइयाँ रूप है और आखिरी वाला या अगर ।

सबूत

हम पर प्रेरण द्वारा साबित होते हैं और ।
आधार - - सच (दो कोड 0 और 1 के लिए उपरोक्त सूत्रों को सत्यापित करना आसान है)।
संक्रमण। सूत्रों को सत्य मानें और कोई भी । ग्रे कोड के अस्तित्व के प्रमाण से सूत्र को याद करें: । यहां से हमें वह पहला कोड मिलता है अनुक्रम में इकाइयाँ बाईं ओर दिया गया शून्य पहला कोड है अनुक्रम में इकाइयाँ । पर हमें एकमात्र कोड मिलता है इकाई जिसके लिए सूत्र भी सत्य है। पर अंतिम कोड अनुक्रम में इकाइयाँ के साथ पहला कोड है यूनिट और यूनिट को अनुक्रम में बाईं ओर सौंपा गया है । पर सूत्र भी सत्य है।

प्रमेय

अनुक्रम में आसन्न बाइनरी कोड दो श्रेणियों में बिल्कुल भिन्न।

सबूत

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

अब हम प्रमेय के उल्लेखनीय परिणामों को बता सकते हैं।

• पहले से प्रस्तावित भोली एल्गोरिथ्म सही है, यदि अनुक्रम में है केवल उन बाइनरी कोड को छोड़ दें जिनमें बिल्कुल k इकाइयां हैं, फिर उन्हें न्यूनतम परिवर्तन के क्रम में व्यवस्थित किया जाएगा (प्रत्येक निम्नलिखित को एक तत्व को प्रतिस्थापित करके पिछले एक से प्राप्त किया जाता है)।
• अनुक्रम निम्नलिखित पुनरावृत्ति संबंध द्वारा परिभाषित किया गया है: । इसे इंडक्शन द्वारा सत्यापित किया जा सकता है।
• अनुक्रम निम्नलिखित पुनरावृत्ति संबंध द्वारा परिभाषित किया गया है: । इंडक्शन द्वारा भी सत्यापित।

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

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

यह नोटिस करना आसान है कि कॉल ट्री द्विआधारी होगा लेकिन पूरा नहीं होगा। आइए हम पेड़ों के संदर्भ में जटिलता के आकलन का एक समानांतर बनाएं: प्रत्येक पत्ती कुछ बाइनरी कोड प्राप्त करने से मेल खाती है, और पेड़ में पत्ती की दूरी n से अधिक नहीं होती है। मूल्यांकन हमें बताता है कि हमने सिर्फ चादरों के सभी रास्तों की लंबाई - n - के लिए ऊपरी बाउंड को सम्‍मिलित किया है। लेकिन आखिरकार, इन रास्तों में से कई की लंबाई n से कम है, और यहां तक ​​कि अधिक पथ एक दूसरे के साथ प्रतिच्छेद करते हैं। यह हमें इस विचार की ओर ले जाना चाहिए कि प्रस्तुत एल्गोरिथम का स्पर्शोन्मुख व्यवहार वास्तव में बहुत बेहतर है।

एसिम्पोटिक्स का एक सटीक अनुमान एक तुच्छ तथ्य से बहुत दूर है, जो कि ई। रींगोल्ड, जे। निवरगेल्ट और एन। डी। "कॉम्बिनेटरियल एल्गोरिदम द्वारा पुस्तक में पाया जा सकता है। सिद्धांत और व्यवहार ”, या इसे स्वयं सिद्ध करने का प्रयास करें।

इस पर मैं लेख को समाप्त करना चाहूंगा। धन्यवाद और जल्द ही मिलते हैं।