एल्गोरिदम में संभावना। यांडेक्स व्याख्यान

कई एल्गोरिदम नियतात्मक हैं - अर्थात्, उनके कार्यों का अनुक्रम केवल इनपुट डेटा और कार्यक्रम पर निर्भर करता है। लेकिन क्या होता है अगर आप एल्गोरिदम को यादृच्छिक संख्याओं का उपयोग करने की अनुमति देते हैं जैसे आप काम करते हैं?

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

हैश फ़ंक्शन

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

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

यहाँ कुंजी हैश फ़ंक्शन का विकल्प है। यह वह है जो दक्षता को प्रभावित करता है। यदि हम h (k) = 0 चुनते हैं, तो हमारा सभी हैश शून्य होगा, और अंत में हमें एक श्रृंखला मिलेगी जिसमें हम हमेशा खोज करेंगे। यह बहुत धीमा और लाभहीन है। लेकिन अगर हैश फ़ंक्शन के मान कुछ यादृच्छिक हैं, तो ऐसा नहीं होगा।

दुर्घटना

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

अब एक औसत यादृच्छिक चर की अवधारणा पर विचार करें। अगर हमारी कंपनी में प्राथमिक ईवेंट्स इकाइयाँ हैं ( ₁ , ..., a), और उन्हें सौंपी गई संभावनाएँ हैं (p ₁ , ..., p _n ), और हमारे फंक्शन प्राथमिक घटनाओं को मानों (x ₁ , ..., x _n ) में मैप करते हैं, तो हमारा मतलब है कि फॉर्म x ₁ p ₁ + x ₂ p ₂ + ... x _n p _n का भारित योग। यानी आपको यह देखने की जरूरत है कि किन मूल्यों के साथ और किन संभावनाओं को स्वीकार किया जाता है, और फिर एक गुणांक के साथ औसत है जो एक या किसी अन्य प्राथमिक घटना की शुरुआत की संभावना के बराबर है।

मार्कोव असमानता

इस लेम्मा का अनौपचारिक अर्थ इस प्रकार है: यदि एक यादृच्छिक चर में बहुत बड़ा औसत नहीं है, तो यह अक्सर बड़े मान नहीं ले सकता है। हम समस्या के औपचारिक विवरण और प्रमाण पर विचार करते हैं। एक असतत संभावना स्थान (Ω, p) दिया जाए और उस पर एक यादृच्छिक चर - f * ability → R _१ । हम ऐसी घटना की संभावना में रुचि रखते हैं कि एक यादृच्छिक चर ε के बराबर या उससे अधिक मूल्य लेता है, जहां positive एक निश्चित सकारात्मक संख्या है।



हम प्रमाण को पास करते हैं। सिद्ध असमानता को अलग तरह से लिखा जा सकता है:



स्मरण करें कि E [f] = x ₁ p ₁ + x _{2 2} + _n + x _n p _n । इससे हम निम्नलिखित निष्कर्ष निकाल सकते हैं:



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