यादृच्छिकता सहायता का उपयोग करने से आपके कोड को तेज़ी से कैसे बनाया जा सकता है? यैंडेक्स पर मिखाइल विल्लि द्वारा व्याख्यान

और आधुनिक कंप्यूटर की ताकत और कमजोरी वे कितने सही हैं। आज यैंडेक्स से हमारी व्याख्यान श्रृंखला में, हम बात करते हैं कि कैसे यादृच्छिकता का उपयोग करके कंप्यूटिंग को अधिक कुशल बनाने में मदद मिल सकती है।

संभाव्य एल्गोरिदम सैद्धांतिक कंप्यूटर विज्ञान की कुछ समस्याओं को हल करना संभव बनाते हैं जिसके लिए नियतात्मक एल्गोरिदम काम नहीं करते हैं। सबसे दिलचस्प सवाल यह है कि रैंडमनेस का उपयोग करते हुए एल्गोरिथ्म के चलने का समय कितना कम हो जाता है? भाग में, इस प्रश्न का उत्तर पहले से ही दिया जा सकता है: कुछ मान्यताओं के तहत, वास्तविक यादृच्छिकता को झूठे और नियतात्मक रूप से किसी भी संभाव्य एल्गोरिथ्म को ऑपरेटिंग समय में मामूली नुकसान के साथ बदला जा सकता है। इन मान्यताओं का सत्यापन, जाहिरा तौर पर, 21 वीं सदी के सैद्धांतिक सूचना विज्ञान के केंद्रीय विषयों में से एक होगा।



व्याख्यान का नामकरण कम्प्यूटिंग सेंटर में एक वरिष्ठ शोधकर्ता द्वारा दिया गया है ए.ए. डॉरोडनिट्सना आरएएस, भौतिक और प्रौद्योगिकी के मास्को संस्थान के गणितीय प्रबंधन विभाग के एसोसिएट प्रोफेसर, भौतिक और गणितीय विज्ञान मिखाइल वायली के उम्मीदवार।

सबसे सरल से शुरू करते हैं। कल्पना कीजिए कि हमारे पास दो कैलकुलेटर हैं। एक सामान्य है, और दूसरे में एक अतिरिक्त बटन है जो दबाए जाने पर, एक अतिरिक्त बिट का उत्पादन करता है। आइए प्रश्न का उत्तर देने का प्रयास करें, क्या ऐसा कार्य उपयोगी होगा?



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



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

सबसे पहले, एक फ्लिप सिक्के के कई पहलू (परिणाम) हो सकते हैं। दूसरे, सभी संभावित परिणामों से बाहर गिरने की संभावना समान नहीं होनी चाहिए। हालाँकि, सभी संभावित परिणामों का योग हमेशा 1 होता है।

त्रुटि संभावना गणना

एक संभाव्य एल्गोरिथ्म की त्रुटि की संभावना की गणना करते समय, दो नियमों को ध्यान में रखा जाना चाहिए:

• स्वतंत्र घटनाओं की संभावनाएँ कई गुना अधिक हैं।
• असंगत घटनाओं की संभावनाओं को जोड़ते हैं।

एल्गोरिदम से कैसे संबंधित है जो गलत हो सकता है? अंत में, आप बस कुछ प्रश्न पूछ सकते हैं, जिनके लिए हाँ / नहीं के उत्तर की आवश्यकता होती है, एक दो तरफा सिक्के को उछालना और 1/2 की संभावना के साथ सही उत्तर प्राप्त करना। तो क्या गलती की संभावना है जो हमें सूट करती है? उदाहरण के लिए, क्या 9/10 में त्रुटि की उच्च संभावना है? यदि एक त्रुटि का पता लगाया जा सकता है, और एल्गोरिथ्म दोहराया निष्पादन की अनुमति देता है, तो बहुत अधिक नहीं।



यदि सही उत्तर हमारे लिए अज्ञात है, तो कार्य अधिक कठिन हो जाता है। एल्गोरिथ्म हमें "हां" या "नहीं" का जवाब देता है। यदि त्रुटि की संभावना ε <1/2 है, तो एल्गोरिथ्म की पुनरावृत्ति त्रुटि की संभावना को जल्दी से कम कर सकती है। यानी आपको एल्गोरिथ्म के समय को दोहराने की आवश्यकता है, और उत्तर दें कि आप अधिक बार मिले थे। त्रुटि की संभावना 1/3 होने दें। जब वोटिंग के स्वतंत्र निष्पादन में त्रुटि की संभावना की गणना की जाती है:



यदि 100 स्वतंत्र निष्पादन करते समय त्रुटि की संभावना भी 1/3 है, तो त्रुटि की संभावना की गणना निम्नानुसार की जा सकती है:



बढ़ते k के साथ , त्रुटि की संभावना बहुत जल्दी घट जाएगी:

संपर्क स्थापना

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



संपर्क स्थापित करने का एक निर्धारित तरीका मौजूद नहीं है। इसके अलावा, संपर्क स्थापित करने के लिए संभाव्य एल्गोरिथ्म बहुत सरल है: प्रत्येक चरण पर, आपको पिछले चरणों की तुलना में बेतरतीब ढंग से, समान रूप से और स्वतंत्र रूप से एक जगह चुनने की आवश्यकता है। आइए इस एल्गोरिथम का विश्लेषण करें। प्रत्येक चरण पर त्रुटि की संभावना 1/2 है। टी चरणों के बाद, त्रुटि की संभावना 2- ^टी होगी, जो एक बहुत छोटा मूल्य हो सकता है।

एक मध्यस्थ द्वारा समानता की जाँच का कार्य

अधिक जटिल स्थिति के साथ एक समस्या पर विचार करें। ऐलिस को बाइनरी शब्द x की लंबाई n पता है । बॉब एक ​​ही लंबाई के शब्द को जानता है। वे चार्ली को कुछ जानकारी (शब्द यू और वी ) से अवगत कराने में सक्षम हैं, जिसके अनुसार चार्ली को यह तय करना होगा कि क्या शब्द x और y समान हैं। उद्देश्य: संभव के रूप में कुछ बिट्स प्रसारित करने के लिए, बशर्ते कि चार्ली किसी भी एक्स, वाई का सही उत्तर दे। ऐलिस और बॉब एक ​​दूसरे के साथ संवाद नहीं कर सकते।



यदि u और v का निर्धारण x और y द्वारा निर्धारित किया जाता है, अर्थात। यू = एफ (एक्स), वी = जी (वाई) , फिर समानता समस्या को हल करने के लिए आपको कम से कम 2 एन बिट्स को स्थानांतरित करने की आवश्यकता है। एक पथ की लंबाई u n से कम है। तब u के संभावित मान 2 ⁿ से कम हैं , अर्थात संभव x मानों की संख्या से कम।



चार्ली के लिए, x ₁ और x ₂ अप्रभेद्य हैं।

"संचार चैनल" के रूप में दुर्घटना

आइए उसी समस्या को हल करने का प्रयास करें, लेकिन अब कल्पना करें कि ऐलिस और बॉब के पास यादृच्छिकता के एक आम स्रोत तक पहुंच है। कहते हैं, "यादृच्छिक संख्याओं की तालिका" पुस्तक के एक ही संस्करण में। उद्देश्य: जितना संभव हो उतना कम बिट्स प्रसारित करने के लिए, बशर्ते कि चार्ली की त्रुटि की संभावना किसी भी x, y पर छोटी हो।



आइए हम इस समस्या को हल करने का प्रयास करें और निर्धारित करें कि क्या नियतात्मक एल्गोरिथ्म का उपयोग करने की तुलना में इस तरह से कम बिट्स को प्रसारित करना संभव है।

ऐलिस और बॉब ने n से 2 n तक की सीमा में एक यादृच्छिक प्राइम पी (एक ही चीज़, दोनों के लिए एक संयोग सामान्य) का चयन किया।

एलिस यू = एक्स मॉड पी की गणना करता है, जहां एक्स एक नंबर है जिसका बाइनरी नोटेशन एलिस एक्स शब्द से मेल खाता है। बॉब वही करता है और V = Y mod p की गणना करता है। फिर वे दोनों चार्ली के यू और वी नंबर के बाइनरी रिकॉर्ड भेजते हैं। चार्ली का कहना है कि अगर x और y शब्द बराबर हैं तो u = v ।
चूंकि 0 , U, V <p ≤ 2n , संदेश की लंबाई log 2 + लॉग एन है ।

मामले में x = y, चार्ली हमेशा सही उत्तर देता है। यदि x error y, चार्ली की त्रुटि की संभावना 3/4 से अधिक नहीं है। हम इसे संख्या सिद्धांत से प्रमेय का उपयोग करके साबित करते हैं।

बहुत सारी अभाज्य संख्याएँ हैं। सभी पर्याप्त रूप से बड़े n के लिए, 1 से n तक के अपराधों की संख्या sufficient (n) असमानताओं को संतुष्ट करती है:



यदि X - Y ≠ 0 primes n ≤ p ₁ <... <p _k n 2n से विभाज्य है, तो

किसी त्रुटि की संभावना में कमी

प्रस्तावित प्रोटोकॉल की त्रुटि एक तरफ़ा है। यह प्रोटोकॉल को बार-बार निष्पादित करके त्रुटि की संभावना को कम करता है। यदि ऐलिस और बॉब सरल मॉड्यूल (बेतरतीब ढंग से और स्वतंत्र रूप से) चुनते हैं, तो त्रुटि की संभावना (3/4) ^s से कम हो जाती है। पर्याप्त रूप से बड़े s लेने से , त्रुटि की संभावना को मनमाने ढंग से छोटा किया जा सकता है।

किसी भी ε > 0 के लिए सामान्य यादृच्छिकता की उपस्थिति में, संदेशों को चुनने की एक विधि है जो समानता की समस्या के समाधान की गारंटी देता है, ε से कम त्रुटि की संभावना और ओ (लॉग एन ) बिट्स को प्रसारित करता है। अंकन g (n) = O (f (n)) का अर्थ है कि संख्याएँ C और n _{0 हैं} जैसे कि g (n) <Cf (n) सभी n> n _{0 के लिए} ।

सामान्य यादृच्छिकता की अनुपस्थिति में प्रोटोकॉल

यह कैसे साबित करें कि समता समस्या में u, v संदेशों को चुनने का एक तरीका है, जिसमें ऐलिस और बॉब एक-दूसरे के यादृच्छिक बिट्स को नहीं जानते हैं, O ( nn log n ) बिट्स संचरित होते हैं, और त्रुटि संभावना 1/3 से कम है?
N- तत्व सेट में आकार 2 Twon के दो यादृच्छिक सबसेट संभावना> 4/5 (लगभग 1 - 1 / ई ² ) के साथ प्रतिच्छेद सेट करते हैं। और यह पता चला है कि यह लगभग सभी है जो हम प्राप्त कर सकते हैं। हम बाबई-किमेल प्रमेय के एक विशेष मामले पर विचार करते हैं, जिसमें से यह है कि समानता समस्या में संदेशों की संभाव्य पसंद के किसी भी तरीके के लिए त्रुटि की संभावना की गारंटी 1/3 से कम है, प्रेषित संदेशों की लंबाई Ω (√n) है । अंकन g (n) = Ω (f (n)) का अर्थ है कि संख्याएँ C और n _{0 हैं} जैसे कि g (n)> Cf (n) सभी n> n _{0 के लिए} ।

व्याख्यान को अंत तक देखने के बाद, आप सीखेंगे कि कैसे, यादृच्छिकता की शुरूआत के माध्यम से, आप एल्गोरिथ्म को गति दे सकते हैं, साथ ही साथ नकली यादृच्छिकता की अवधारणा भी।