रैंडमाइज्ड एल्गोरिदम
रैंडमाइज्ड एल्गोरिदम निष्पादन के दौरान दक्षता, सरलता या सुदृढ़ता प्राप्त करने के लिए यादृच्छिक विकल्प चुनते हैं, जिसमें प्रदर्शन और शुद्धता को सबसे खराब स्थिति की निश्चितताओं के बजाय संभाव्य गारंटियों के रूप में व्यक्त किया जाता है।
Definition
एक रैंडमाइज्ड एल्गोरिदम एक एल्गोरिदम है जो अपने कुछ निर्णय लेने के लिए यादृच्छिक बिट्स के स्रोत का उपयोग करता है, ताकि उसका चलने का समय, आउटपुट, या दोनों यादृच्छिक चर हों जिनका विश्लेषण उनकी अपेक्षा या संभाव्यता वितरण द्वारा किया जाता है।
Scope
यह विषय उन एल्गोरिदम को शामिल करता है जो यादृच्छिकता को एक कम्प्यूटेशनल संसाधन के रूप में उपयोग करते हैं: लास वेगास मॉडल (हमेशा सही, यादृच्छिक चलने का समय) और मोंटे कार्लो मॉडल (निश्चित चलने का समय, सीमित त्रुटि संभावना), यादृच्छिक क्विकसॉर्ट, यादृच्छिक चयन, प्राइमलिटी परीक्षण जैसे विहित उदाहरण, और स्किप लिस्ट जैसी यादृच्छिक डेटा संरचनाएं, और संभाव्य विश्लेषण उपकरण (अपेक्षा, भिन्नता, टेल और एकाग्रता असमानताएं) जिनका उपयोग उनके बारे में तर्क करने के लिए किया जाता है।
Core questions
- यादृच्छिकता का परिचय किसी एल्गोरिदम को किसी भी ज्ञात नियतात्मक एल्गोरिदम की तुलना में तेज़ या सरल कैसे बना सकता है?
- लास वेगास और मोंटे कार्लो एल्गोरिदम के बीच क्या अंतर है?
- अपेक्षित चलने का समय या त्रुटि संभावना का विश्लेषण कैसे किया जाता है?
- एकाग्रता असमानताएं बुरे परिणामों की संभावना को कैसे सीमित करती हैं?
- पुनरावृत्ति द्वारा मोंटे कार्लो एल्गोरिदम की त्रुटि को कैसे कम किया जा सकता है?
Key concepts
- संसाधन के रूप में यादृच्छिक बिट्स
- लास वेगास एल्गोरिदम
- मोंटे कार्लो एल्गोरिदम
- अपेक्षित चलने का समय
- त्रुटि संभावना और प्रवर्धन
- एकाग्रता असमानताएं
- रैंडमाइज्ड क्विकसॉर्ट
- स्किप लिस्ट
Key theories
- लास वेगास बनाम मोंटे कार्लो
- लास वेगास एल्गोरिदम हमेशा एक सही परिणाम उत्पन्न करते हैं लेकिन उनका चलने का समय यादृच्छिक (अपेक्षा में विश्लेषण किया गया) होता है, जबकि मोंटे कार्लो एल्गोरिदम एक निश्चित समय के भीतर चलते हैं लेकिन सीमित संभावना के साथ एक गलत परिणाम उत्पन्न कर सकते हैं, जिसे पुनरावृत्ति से कम किया जा सकता है।
- संभाव्य प्राइमलिटी परीक्षण
- मिलर-राबिन जैसे रैंडमाइज्ड परीक्षण यादृच्छिक साक्ष्यों की जांच करके बहुपद समय में उच्च विश्वास के साथ प्राइमलिटी को प्रमाणित करते हैं; एक समग्र संख्या अधिकांश साक्ष्यों द्वारा उजागर होती है, इसलिए बार-बार परीक्षण करने से त्रुटि की संभावना नगण्य हो जाती है।
Clinical relevance
रैंडमाइज्ड एल्गोरिदम व्यापक रूप से तैनात किए जाते हैं: मिलर-राबिन प्राइमलिटी परीक्षण सार्वजनिक-कुंजी क्रिप्टोग्राफी को रेखांकित करता है, यादृच्छिक हैशिंग और लोड संतुलन वितरित प्रणालियों को कुशल रखते हैं, यादृच्छिक क्विकसॉर्ट और क्विकसेलेक्ट मजबूत अपेक्षित प्रदर्शन देते हैं, और यादृच्छिक नमूनाकरण और स्केचिंग बड़े डेटा स्ट्रीम के प्रसंस्करण को सक्षम करते हैं।
History
संभाव्य एल्गोरिदम 1970 के दशक में सोलोवे-स्ट्रैसन और मिलर-राबिन प्राइमलिटी परीक्षणों के साथ प्रमुखता में आए, जिन्होंने यादृच्छिकता को एक सम्मानजनक कम्प्यूटेशनल उपकरण बना दिया। 1980 और 1990 के दशक में यादृच्छिक डेटा संरचनाएं (स्किप लिस्ट, ट्रेप्स), यादृच्छिक ग्राफ और ज्यामितीय एल्गोरिदम, और मोटवानी और राघवन की 1995 की पाठ्यपुस्तक में संहिताबद्ध व्यवस्थित सिद्धांत देखे गए।
Key figures
- Michael Rabin
- Robert Solovay
- Volker Strassen
- Rajeev Motwani
- Prabhakar Raghavan
Related topics
Seminal works
- motwani1995
- rabin1980
- cormen2009
Frequently asked questions
- यदि मोंटे कार्लो एल्गोरिदम गलत हो सकता है तो उस पर कैसे भरोसा किया जा सकता है?
- इसकी त्रुटि संभावना सीमित और ज्ञात होती है, और एकतरफा-त्रुटि वाले एल्गोरिदम के लिए इसे स्वतंत्र यादृच्छिकता के साथ एल्गोरिदम को कई बार चलाकर मनमाने ढंग से छोटा किया जा सकता है। पर्याप्त पुनरावृत्ति के बाद गलत उत्तर की संभावना हार्डवेयर विफलता की संभावना से कहीं कम होती है।
- नियतात्मक क्विकसॉर्ट की तुलना में रैंडमाइज्ड क्विकसॉर्ट को क्यों पसंद किया जाता है?
- नियतात्मक क्विकसॉर्ट खराब पिवट विकल्पों के कारण प्रतिकूल या पहले से ही सॉर्ट किए गए इनपुट पर अपनी O(n वर्ग) सबसे खराब स्थिति में आ सकता है। पिवट को यादृच्छिक रूप से चुनने से इनपुट की परवाह किए बिना वह सबसे खराब स्थिति अत्यंत असंभव हो जाती है, जिससे प्रत्येक इनपुट पर अपेक्षित O(n लॉग n) प्रदर्शन मिलता है।