यादृच्छिक एल्गोरिथ्म: Difference between revisions

Latest revision as of 14:50, 24 August 2023

यादृच्छिक एल्गोरिदम एक एल्गोरिदम है जो अपने तर्क या प्रक्रिया के भूमिका के रूप में यादृच्छिकता की कोटि को नियोजित करता है। एल्गोरिथ्म सामान्यतः यादृच्छिक बिट्स द्वारा निर्धारित यादृच्छिक के सभी संभावित विकल्पों पर "औसत मामले" में अच्छा प्रदर्शन प्राप्त करने की आशा में, अपने व्यवहार को निर्देशित करने के लिए सहायक इनपुट के रूप में एक समान यादृच्छिक (असतत) बिट्स का उपयोग करता है; इस प्रकार या तो चलने का समय, या आउटपुट (या दोनों) यादृच्छिक चर हैं।

किसी को यादृच्छिक इनपुट का उपयोग करने वाले एल्गोरिदम के बीच अंतर करना होगा जिससे कि वे हमेशा सही उत्तर के साथ समाप्त हो जाएं, लेकिन जहां अपेक्षित चलने का समय सीमित है (लास वेगास कलन विधि, उदाहरण के लिए क्विक सॉर्ट^[1]), और एल्गोरिदम जिनके पास गलत परिणाम उत्पन्न करने का मौका है (मोंटे कार्लो एल्गोरिथ्म, उदाहरण के लिए न्यूनतम फीडबैक आर्क सेट समस्या के लिए मोंटे कार्लो एल्गोरिदम^[2]) या तो विफलता का संकेत देकर या समाप्त करने में विफल होने पर परिणाम उत्पन्न करने में विफल हैं। कुछ स्थितियों में, समस्या को हल करने का एकमात्र व्यावहारिक साधन संभाव्य एल्गोरिदम हैं।^[3]

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

प्रेरणा

प्रेरक उदाहरण के रूप में, n तत्वों की सरणी डेटा संरचना में 'a' निष्कर्ष की समस्या पर विचार करें।

इनपुट: n≥2 तत्वों की सरणी, जिसमें आधे a हैं और अन्य आधे b हैं।

आउटपुट: सरणी में a खोजें।

हम एल्गोरिथ्म के दो संस्करण देते हैं, एक लास वेगास एल्गोरिथम और एक मोंटे कार्लो एल्गोरिथम।

लास वेगास एल्गोरिथम:

findingA_LV(array A, n)
begin
    repeat
        Randomly select one element out of n elements.
    until 'a' is found
end

यह एल्गोरिथ्म प्रायिकता 1 के साथ सफल होता है। पुनरावृत्तियों की संख्या भिन्न होती है और अक्रमतः बड़ी हो सकती है, लेकिन पुनरावृत्तियों की अपेक्षित संख्या है

\lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2

चूंकि यह स्थिर है, कई कॉलों पर अपेक्षित रन टाइम है $\Theta (1)$ . (बिग थीटा नोटेशन देखें)

मोंटे कार्लो एल्गोरिथम:

findingA_MC(array A, n, k)
begin
    i := 0
    repeat
        Randomly select one element out of n elements.
        i := i + 1
    until i = k or 'a' is found
end

यदि 'a' पाया जाता है, तो एल्गोरिथम सफल होता है, अन्यथा एल्गोरिथम विफल हो जाता है। k पुनरावृत्तियों के बाद, 'a' निष्कर्ष की संभावना है:

$\Pr[\mathrm {find~a} ]=1-(1/2)^{k}$

यह एल्गोरिदम सफलता की गारंटी नहीं देता है, लेकिन रन टाइम सीमित है। पुनरावृत्तियों की संख्या हमेशा k से कम या उसके बराबर होती है। k को स्थिर रखने के लिए रन टाइम (अपेक्षित और पूर्ण) $\Theta (1)$ है

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

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

अभिकलनात्मक जटिलता

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

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

प्रारंभिक इतिहास

सॉर्टिंग

क्विक सॉर्ट की खोज 1959 में टोनी होरे द्वारा की गई थी, और बाद में 1961 में प्रकाशित हुई थी।^[4] उसी वर्ष, होरे ने त्वरित चयन एल्गोरिथ्म प्रकाशित किया,^[5] जो रैखिक अपेक्षित समय में किसी सूची का मध्य तत्व पाता है। यह 1973 तक खुला रहा कि क्या नियतात्मक रैखिक-समय एल्गोरिथम सम्मिलित है।^[6]

संख्या सिद्धांत

1917 में, हेनरी कैबॉर्न पॉकलिंगटन ने यादृच्छिक एल्गोरिथम पेश किया, जिसे पॉकलिंगटन के एल्गोरिथ्म के रूप में जाना जाता है, जो कुशलतापूर्वक वर्गमूल मॉड्यूलो अभाज्य संख्या को निष्कर्ष के लिए है।^[7]1970 में, एल्विन बर्लेकैंप ने परिमित क्षेत्र पर बहुपद की वर्गमूल की कुशलता से गणना करने के लिए यादृच्छिक एल्गोरिथ्म पेश किया है।^[8] 1977 में, रॉबर्ट एम. सोलोवे और वोल्कर स्ट्रास ने बहुपद-समय सोलोवे-स्ट्रैसन प्रारंभिक परीक्षण की खोज की थी (अर्थात, किसी संख्या की प्रारंभिक परीक्षा का निर्धारण)। इसके तुरंत बाद माइकल ओ. राबिन ने प्रदर्शित किया कि 1976 मिलर के प्रारंभिक परीक्षण को बहुपद-समय यादृच्छिक एल्गोरिथम में भी बदला जा सकता है। उस समय, प्रारंभिक परीक्षण के लिए कोई सिद्ध बहुपद-समय नियतात्मक एल्गोरिथम ज्ञात नहीं था।

डेटा संरचनाएं

जल्द से जल्द यादृच्छिक डेटा संरचनाओं में से हैश तालिका है, जिसे 1953 में आईबीएम में हंस पीटर लुहान द्वारा पेश किया गया था।^[9] लुहान की हैश टेबल ने संघट्ट को हल करने के लिए चेनिंग का उपयोग किया और लिंक्ड सूची के पहले अनुप्रयोगों में से एक था।^[9]इसके बाद, 1954 में, आईबीएम रिसर्च के जीन अमदहल, ऐलेन एम. मैकग्रा, नथानिएल रोचेस्टर (कंप्यूटर वैज्ञानिक), और आर्थर सैमुअल (कंप्यूटर वैज्ञानिक) ने रैखिक जांच प्रारंभ की,^[9]चूंकि 1957 में स्वतंत्र रूप से एंड्री एर्शोव का भी यही विचार था।^[9]1962 में, डोनाल्ड नुथ ने रेखीय जांच का पहला सही विश्लेषण किया,^[9]हालाँकि उनके विश्लेषण वाला ज्ञापन बहुत बाद तक प्रकाशित नहीं हुआ था।^[10] पहला प्रकाशित विश्लेषण 1966 में कोनहेम और वीस के कारण हुआ था।^[11]

हैश टेबल पर प्रारंभिक कार्य या तो पूरी तरह यादृच्छिक हैश फ़ंक्शन तक पहुंच मानते हैं या मानते हैं कि कीज़ स्वयं यादृच्छिक थीं।^[9]1979 में, कार्टर और वेगमैन ने यूनिवर्सल हैशिंग की शुरुआत की,^[12] जो उन्होंने दिखाया कि प्रति ऑपरेशन निरंतर अपेक्षित समय के साथ चेन हैश टेबल को लागू करने के लिए उपयोग किया जा सकता है।

यादृच्छिक डेटा संरचनाओं पर प्रारंभिक कार्य भी हैश टेबल से आगे बढ़ता है। 1970 में, बर्टन हावर्ड ब्लूम ने अनुमानित-सदस्यता डेटा संरचना पेश की जिसे ब्लूम फिल्टर के रूप में जाना जाता है।^[13] 1989 में, रायमुंड सीडेल और सेसिलिया आर. आरागॉन ने यादृच्छिक संतुलित खोज तरु पेश किया जिसे ट्रीप के रूप में जाना जाता है।^[14] उसी वर्ष, विलियम पुघ (कंप्यूटर वैज्ञानिक) ने एक और यादृच्छिक खोज तरु पेश किया जिसे स्किप सूची के रूप में जाना जाता है।^[15]

कॉम्बिनेटरिक्स में अंतर्निहित उपयोग

कंप्यूटर विज्ञान में यादृच्छिक एल्गोरिदम के लोकप्रिय होने से पहले, पॉल एर्डोस ने गणितीय वस्तुओं के अस्तित्व को स्थापित करने के लिए गणितीय तकनीक के रूप में यादृच्छिक निर्माण के उपयोग को लोकप्रिय बनाया था। इस तकनीक को संभाव्य विधि के रूप में जाना जाने लगा।^[16] पॉल एर्दोस ने 1947 में संभाव्यता पद्धति का अपना पहला आवेदन दिया, जब उन्होंने रैमसे ग्राफ के अस्तित्व को स्थापित करने के लिए सरल यादृच्छिक निर्माण का उपयोग किया था।^[17] उन्होंने 1959 में उच्च परिधि और रंगीन संख्या वाले ग्राफ के अस्तित्व को स्थापित करने के लिए प्रसिद्ध रूप से अधिक परिष्कृत यादृच्छिक एल्गोरिथ्म का उपयोग किया था।^[18]^[16]

उदाहरण

क्विकसॉर्ट

क्विकसॉर्ट एक परिचित, सामान्यतः उपयोग किया जाने वाला एल्गोरिदम है जिसमें यादृच्छिकता उपयोगी हो सकती है। इस एल्गोरिथम के कई नियतात्मक संस्करणों के लिए O(n²) की आवश्यकता होती है कुछ अच्छी तरह से परिभाषित इनपुट वर्ग (जैसे कि पहले से ही क्रमबद्ध सरणी) के लिए n संख्याओं को सॉर्ट करने का समय, इनपुट के विशिष्ट वर्ग के साथ जो पिवट चयन के लिए प्रोटोकॉल द्वारा परिभाषित इस व्यवहार को उत्पन्न करता है। चूंकि, यदि एल्गोरिद्म पिवट तत्वों को यादृच्छिक रूप से समान रूप से चुनता है, तो इनपुट की विशेषताओं की परवाह किए बिना O(n log n) समय में समाप्त होने की संभावना काफी अधिक होती है।

ज्यामिति में यादृच्छिक वृद्धिशील निर्माण

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

न्यूनतम कट

इनपुट: ग्राफ सिद्धांत G(V,E)

आउटपुट: कट (ग्राफ सिद्धांत) L और R में कोने को विभाजित करता है, जिसमें L और R के बीच किनारों की न्यूनतम संख्या होती है।

याद रखें कि एक (बहु-) ग्राफ़ में दो नोड्स, u और v के किनारे का संकुचन, किनारों के साथ नया नोड u' देता है, जो u या v पर किनारों की घटना का संघ है, किसी भी किनारे को छोड़कर u और v को जोड़ता है। चित्र 1 शीर्ष A और B के संकुचन का उदाहरण देता है।

संकुचन के बाद, परिणामी ग्राफ़ में समानांतर किनार हो सकते हैं, लेकिन इसमें कोई सेल्फ लूप नहीं होता है।

चित्र 2: 10-शीर्ष ग्राफ़ पर कार्गर के एल्गोरिथम का सफल संचालन। न्यूनतम कट का आकार 3 है और इसे शीर्ष रंगों द्वारा दर्शाया गया है।

चित्र 1: शीर्ष A और B का संकुचन

कार्गर का^[20] बुनियादी एल्गोरिथ्म:

    begin

i = 1
    repeat
        repeat
            Take a random edge (u,v) ∈ E in G
            replace u and v with the contraction u'
        until only 2 nodes remain
        obtain the corresponding cut result C_i
        i = i + 1
    until i = m
    output the minimum cut among C₁, C₂, ..., C_m.
end

बाहरी लूप के प्रत्येक निष्पादन में, एल्गोरिथ्म आंतरिक लूप को तब तक दोहराता है जब तक कि केवल 2 नोड शेष न रह जाएं, संबंधित कट प्राप्त हो जाता है। एक निष्पादन का रन टाइम है $O(n)$ , और n शीर्षों की संख्या को दर्शाता है। बाहरी लूप के m बार निष्पादन के बाद, हम सभी परिणामों के बीच न्यूनतम कट का उत्पादन करते हैं। चित्र 2 एल्गोरिथ्म के एक निष्पादन का उदाहरण देता है। निष्पादन के बाद, हमें आकार 3 में कट मिलती है।

Lemma 1 — Let k be the min cut size, and let $C = {e 1, e 2, ..., e k}$ be the min cut. If, during iteration i, no edge $e \in C$ is selected for contraction, then $C i = C$ .

Proof

If G is not connected, then G can be partitioned into L and R without any edge between them. So the min cut in a disconnected graph is 0. Now, assume G is connected. Let $V = L \cup R$ be the partition of V induced by $C : C = { {u, v} \in E : u \in L, v \in R$ } (well-defined since G is connected). Consider an edge {u,v} of C. Initially, u,v are distinct vertices. As long as we pick an edge $f\neq e$ , $u$ and $v$ do not get merged. Thus, at the end of the algorithm, we have two compound nodes covering the entire graph, one consisting of the vertices of L and the other consisting of the vertices of R. As in figure 2, the size of min cut is 1, and C = {(A,B)}. If we don't select (A,B) for contraction, we can get the min cut.

Lemma 2 — If G is a multigraph with p vertices and whose min cut has size k, then G has at least pk/2 edges.

Proof

Because the min cut is k, every vertex v must satisfy degree(v) ≥ k. Therefore, the sum of the degree is at least pk. But it is well known that the sum of vertex degrees equals 2|E|. The lemma follows.

एल्गोरिदम का विश्लेषण

एल्गोरिद्म के सफल होने की प्रायिकता 1 − संभावना है कि सभी प्रयास विफल हो जाते हैं। स्वतंत्रता से, सभी प्रयासों के विफल होने की प्रायिकता है

\prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).

लेम्मा 1 द्वारा, संभावना है कि

C i = C

संभावना है कि पुनरावृत्ति i के दौरान C का कोई किनारा नहीं चुना गया है। आंतरिक पाश पर विचार करें और मान लीजिये

G j

, j किनारे के संकुचन के बाद ग्राफ़ को निरूपित करता है, जहाँ

j \in {0, 1, \dots, n - 3}

,

G j

में

n - j

शीर्ष हैं। हम सशर्त संभाव्यता के श्रृंखला नियम का उपयोग करते हैं। संभावना है कि पुनरावृत्ति j पर चुना गया किनारा C में नहीं है, यह देखते हुए कि C का कोई किनारा पहले नहीं चुना गया है

1-{\frac {k}{|E(G_{j})|}}

ध्यान दें कि

G j

अभी भी आकार k का न्यूनतम कट है, इसलिए लेम्मा 2 के अनुसार, यह अभी भी कम से कम

{\frac {(n-j)k}{2}}

किनारा है।

इस प्रकार, $1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}$ .

तो चेन नियम से, न्यूनतम कट C निष्कर्ष की संभावना है

\Pr[C_{i}=C]\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).

निरस्तीकरण देता है

\Pr[C_{i}=C]\geq {\frac {2}{n(n-1)}}

, इस प्रकार एल्गोरिथ्म के सफल होने की संभावना कम से कम है

1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}

है

m={\frac {n(n-1)}{2}}\ln n

, के लिए यह

1-{\frac {1}{n}}

के बराबर है एल्गोरिथ्म संभाव्यता के साथ न्यूनतम कट

1-{\frac {1}{n}}

, समय के भीतर

O(mn)=O(n^{3}\log n)

पाता है।

डेरेंडोमाइजेशन

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

ऐसे विशिष्ट तरीके हैं जिन्हें विशेष यादृच्छिक एल्गोरिदम को यादृच्छिक बनाने के लिए नियोजित किया जा सकता है:

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

जहां यादृच्छिकता मदद करती है

जब संगणना का मॉडल ट्यूरिंग मशीन तक ही सीमित है, तो यह वर्तमान में खुला प्रश्न है कि क्या यादृच्छिक विकल्प बनाने की क्षमता बहुपद काल में कुछ समस्याओं को हल करने की अनुमति देती है जिसे इस क्षमता के बिना बहुपद काल में हल नहीं किया जा सकता है; यह सवाल है कि P = BPP। हालाँकि, अन्य संदर्भों में, समस्याओं के विशिष्ट उदाहरण हैं जहाँ यादृच्छिककरण से सख्त सुधार होते हैं।

प्रारंभिक प्रेरक उदाहरण के आधार पर: 2^k की घातीय रूप से लंबी स्ट्रिंग दी गई है वर्ण, आधा a और आधा b, रैंडम-एक्सेस मशीन के लिए 2^k−1 की आवश्यकता होती है a की अनुक्रमणिका निष्कर्ष के लिए सबसे खराब स्थिति में खोजता है; यदि इसे यादृच्छिक विकल्प बनाने की अनुमति है, तो यह लुकअप की अपेक्षित बहुपद संख्या में इस समस्या को हल कर सकता है।
अंतः स्थापित प्रणालियाँ या साइबर-भौतिक प्रणाली में संख्यात्मक गणना करने का प्राकृतिक तरीका परिणाम प्रदान करना है जो उच्च संभावना (या संभवतः लगभग सही गणना (पीएसीसी)) के साथ सही परिणाम का अनुमान लगाता है। अनुमानित और सही संगणना के बीच विसंगति हानि के मूल्यांकन से जुड़ी कठिन समस्या को यादृच्छिककरण का सहारा लेकर प्रभावी ढंग से संबोधित किया जा सकता है^[21]
संचार जटिलता में, $\log n$ यादृच्छिक प्रोटोकॉल के साथ संचार के बिट्स का उपयोग करके दो स्ट्रिंग की समानता कुछ विश्वसनीयता के लिए सत्यापित किया जा सकता है। किसी भी नियतात्मक प्रोटोकॉल की आवश्यकता $\Theta (n)$ बिट्स होती है यदि दृढ़ प्रतिद्वंद्वी के खिलाफ बचाव करते हैं।^[22]
बहुपद काल में अक्रमतः परिशुद्धता के लिए अवमुखपिंड की मात्रा का अनुमान यादृच्छिक एल्गोरिदम द्वारा लगाया जा सकता है।^[23] इमरे बैरनी और ज़ोलटन फ़्यूरेडी ने दिखाया कि कोई नियतात्मक एल्गोरिथम ऐसा नहीं कर सकता है।^[24] यह बिना शर्त के सच है, अर्थात किसी भी जटिलता-सैद्धांतिक मान्यताओं पर भरोसा किए बिना, अवमुखपिंड को केवल ब्लैक बॉक्स के रूप में माना जा सकता है।
एक जगह का अधिक जटिलता-सैद्धांतिक उदाहरण जहां यादृच्छिकता मदद करने के लिए प्रकट होती है वह वर्ग IP (जटिलता) है। IP में वे सभी भाषाएँ सम्मिलित हैं जिन्हें (उच्च संभावना के साथ) सर्व-शक्तिशाली प्रोवर और सत्यापनकर्ता के बीच बहुपद रूप से लंबी पारस्परिक प्रभाव द्वारा स्वीकार किया जा सकता है जो बीपीपी एल्गोरिथम को लागू करता है। IP = PSPACE।^[25] हालाँकि, यदि यह आवश्यक है कि सत्यापनकर्ता नियतात्मक हो, तो IP = NP (जटिलता)।
रासायनिक प्रतिक्रिया नेटवर्क में (A+B → 2C + D जैसी प्रतिक्रियाओं का सीमित सेट अणुओं की सीमित संख्या पर काम कर रहा है), प्रारंभिक अवस्था से किसी दिए गए लक्ष्य अवस्था तक कभी भी पहुंचने की क्षमता निर्णायक होती है, जबकि संभाव्यता का अनुमान भी लगाया जाता है किसी दिए गए लक्ष्य अवस्था तक पहुंचने के लिए (मानक एकाग्रता-आधारित संभावना जिसके लिए प्रतिक्रिया आगे होगी) का उपयोग करना अनिर्णीत है। अधिक विशेष रूप से, सीमित ट्यूरिंग मशीन सभी समय के लिए सही ढंग से चलने की अक्रमतः उच्च संभावना के साथ अनुरूप किया जा सकता है, केवल तभी जब यादृच्छिक रासायनिक प्रतिक्रिया नेटवर्क का उपयोग किया जाता है। एक सरल गैर-नियतात्मक रासायनिक प्रतिक्रिया नेटवर्क (आगे कोई भी संभावित प्रतिक्रिया हो सकती है) के साथ, कम्प्यूटेशनल पावर आदिम पुनरावर्ती तक सीमित है।^[26]

यह भी देखें

एल्गोरिदम का संभाव्य विश्लेषण
अटलांटिक सिटी एल्गोरिदम
मोंटे कार्लो एल्गोरिथम
लास वेगास एल्गोरिथम
बोगोसॉर्ट
स्थगित निर्णय का सिद्धांत
शून्य-योग गेम के रूप में यादृच्छिक एल्गोरिदम
संभाव्य रोडमैप
हाइपरलॉग
गिनती-मिनट स्केच
अनुमानित गिनती एल्गोरिथ्म
कार्गर का एल्गोरिदम

↑ Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Commun. ACM. 4 (7): 321–. doi:10.1145/366622.366644. ISSN 0001-0782.
↑ Kudelić, Robert (2016-04-01). "न्यूनतम प्रतिक्रिया चाप सेट समस्या के लिए मोंटे-कार्लो यादृच्छिक एल्गोरिथ्म". Applied Soft Computing. 41: 235–246. doi:10.1016/j.asoc.2015.12.018.
↑ "In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." Hal Abelson and Gerald J. Sussman (1996). Structure and Interpretation of Computer Programs. MIT Press, section 1.2.
↑ Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Communications of the ACM (in English). 4 (7): 321. doi:10.1145/366622.366644. ISSN 0001-0782.
↑ Hoare, C. A. R. (July 1961). "Algorithm 65: find". Communications of the ACM (in English). 4 (7): 321–322. doi:10.1145/366622.366647. ISSN 0001-0782.
↑ Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. (August 1973). "चयन के लिए समय सीमा". Journal of Computer and System Sciences (in English). 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.
↑ Williams, H. C.; Shallit, J. O. (1994), "Factoring integers before computers", in Gautschi, Walter (ed.), Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993, Proceedings of Symposia in Applied Mathematics, vol. 48, Amer. Math. Soc., Providence, RI, pp. 481–531, doi:10.1090/psapm/048/1314885, MR 1314885; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".
↑ Berlekamp, E. R. (1971). "बड़े परिमित क्षेत्रों पर बहुपदों का गुणनखंडन*". Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation - SYMSAC '71 (in English). Los Angeles, California, United States: ACM Press: 223. doi:10.1145/800204.806290. ISBN 9781450377867. S2CID 6464612.
↑ ^9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.5 Knuth, Donald E. (1998). The art of computer programming, volume 3: (2nd ed.) sorting and searching. USA: Addison Wesley Longman Publishing Co., Inc. pp. 536–549. ISBN 978-0-201-89685-5.
↑ Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03
↑ Konheim, Alan G.; Weiss, Benjamin (November 1966). "एक अधिभोग अनुशासन और अनुप्रयोग". SIAM Journal on Applied Mathematics. 14 (6): 1266–1274. doi:10.1137/0114101. ISSN 0036-1399.
↑ Carter, J. Lawrence; Wegman, Mark N. (1979-04-01). "हैश फ़ंक्शंस की सार्वभौमिक कक्षाएं". Journal of Computer and System Sciences (in English). 18 (2): 143–154. doi:10.1016/0022-0000(79)90044-8. ISSN 0022-0000.
↑ Bloom, Burton H. (July 1970). "Space/time trade-offs in hash coding with allowable errors". Communications of the ACM. 13 (7): 422–426. doi:10.1145/362686.362692. ISSN 0001-0782. S2CID 7931252.
↑ Aragon, C.R.; Seidel, R.G. (October 1989). "यादृच्छिक खोज पेड़". 30th Annual Symposium on Foundations of Computer Science: 540–545. doi:10.1109/SFCS.1989.63531. ISBN 0-8186-1982-1.
↑ Pugh, William (April 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.
↑ ^16.0 ^16.1 Alon, Noga (2016). संभाव्य विधि. Joel H. Spencer (Fourth ed.). Hoboken, New Jersey. ISBN 978-1-119-06195-3. OCLC 910535517.{{cite book}}: CS1 maint: location missing publisher (link)
↑ P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292--294 MR8,479d; Zentralblatt 32,192.
↑ Erdös, P. (1959). "ग्राफ सिद्धांत और संभावना". Canadian Journal of Mathematics (in English). 11: 34–38. doi:10.4153/CJM-1959-003-9. ISSN 0008-414X. S2CID 122784453.
↑ Seidel R. Backwards Analysis of Randomized Geometric Algorithms.
↑ A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.
↑ Alippi, Cesare (2014), Intelligence for Embedded Systems, Springer, ISBN 978-3-319-05278-6.
↑ Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity, Cambridge University Press, ISBN 9780521029834. For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.
↑ Dyer, M.; Frieze, A.; Kannan, R. (1991), "A random polynomial-time algorithm for approximating the volume of convex bodies" (PDF), Journal of the ACM, 38 (1): 1–17, doi:10.1145/102782.102783, S2CID 13268711
↑ Füredi, Z.; Bárány, I. (1986), "Computing the volume is difficult", Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986) (PDF), New York, NY: ACM, pp. 442–447, CiteSeerX 10.1.1.726.9448, doi:10.1145/12130.12176, ISBN 0-89791-193-8, S2CID 17867291
↑ Shamir, A. (1992), "IP = PSPACE", Journal of the ACM, 39 (4): 869–877, doi:10.1145/146585.146609, S2CID 315182
↑ Cook, Matthew; Soloveichik, David; Winfree, Erik; Bruck, Jehoshua (2009), "Programmability of chemical reaction networks", in Condon, Anne; Harel, David; Kok, Joost N.; Salomaa, Arto; Winfree, Erik (eds.), Algorithmic Bioprocesses (PDF), Natural Computing Series, Springer-Verlag, pp. 543–584, doi:10.1007/978-3-540-88869-7_27.

संदर्भ

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 1990. ISBN 0-262-03293-7. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp. 91–122.
Dirk Draheim. "Semantics of the Probabilistic Typed Lambda Calculus (Markov Chain Semantics, Termination Behavior, and Denotational Semantics)." Springer, 2017.
Jon Kleinberg and Éva Tardos. Algorithm Design. Chapter 13: "Randomized algorithms".
Fallis, D. (2000). "The reliability of randomized algorithms". The British Journal for the Philosophy of Science. 51 (2): 255–271. doi:10.1093/bjps/51.2.255.
M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (NY), 2005.
Rajeev Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York (NY), 1995.
Rajeev Motwani and P. Raghavan. Randomized Algorithms. A survey on Randomized Algorithms.
Christos Papadimitriou (1993), Computational Complexity (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7 Chapter 11: Randomized computation, pp. 241–278.
Rabin, Michael O. (1980). "Probabilistic algorithm for testing primality". Journal of Number Theory. 12: 128–138. doi:10.1016/0022-314X(80)90084-0.
A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.
"Randomized Algorithms for Scientific Computing" (RASC), OSTI.GOV (July 10th, 2021).

[1] Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Commun. ACM. 4 (7): 321–. doi:10.1145/366622.366644. ISSN 0001-0782.

[2] Kudelić, Robert (2016-04-01). "न्यूनतम प्रतिक्रिया चाप सेट समस्या के लिए मोंटे-कार्लो यादृच्छिक एल्गोरिथ्म". Applied Soft Computing. 41: 235–246. doi:10.1016/j.asoc.2015.12.018.

[3] "In testing primality of very large numbers chosen at random, the chance of stumbling upon a value that fools the Fermat test is less than the chance that cosmic radiation will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." Hal Abelson and Gerald J. Sussman (1996). Structure and Interpretation of Computer Programs. MIT Press, section 1.2.

[4] Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Communications of the ACM (in English). 4 (7): 321. doi:10.1145/366622.366644. ISSN 0001-0782.

[5] Hoare, C. A. R. (July 1961). "Algorithm 65: find". Communications of the ACM (in English). 4 (7): 321–322. doi:10.1145/366622.366647. ISSN 0001-0782.

[6] Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. (August 1973). "चयन के लिए समय सीमा". Journal of Computer and System Sciences (in English). 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.

[7] Williams, H. C.; Shallit, J. O. (1994), "Factoring integers before computers", in Gautschi, Walter (ed.), Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993, Proceedings of Symposia in Applied Mathematics, vol. 48, Amer. Math. Soc., Providence, RI, pp. 481–531, doi:10.1090/psapm/048/1314885, MR 1314885; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".

[8] Berlekamp, E. R. (1971). "बड़े परिमित क्षेत्रों पर बहुपदों का गुणनखंडन*". Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation - SYMSAC '71 (in English). Los Angeles, California, United States: ACM Press: 223. doi:10.1145/800204.806290. ISBN 9781450377867. S2CID 6464612.

[:0-9] 9.0 ^9.1 ^9.2 ^9.3 ^9.4 ^9.5 Knuth, Donald E. (1998). The art of computer programming, volume 3: (2nd ed.) sorting and searching. USA: Addison Wesley Longman Publishing Co., Inc. pp. 536–549. ISBN 978-0-201-89685-5.

[10] Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03

[11] Konheim, Alan G.; Weiss, Benjamin (November 1966). "एक अधिभोग अनुशासन और अनुप्रयोग". SIAM Journal on Applied Mathematics. 14 (6): 1266–1274. doi:10.1137/0114101. ISSN 0036-1399.

[12] Carter, J. Lawrence; Wegman, Mark N. (1979-04-01). "हैश फ़ंक्शंस की सार्वभौमिक कक्षाएं". Journal of Computer and System Sciences (in English). 18 (2): 143–154. doi:10.1016/0022-0000(79)90044-8. ISSN 0022-0000.

[13] Bloom, Burton H. (July 1970). "Space/time trade-offs in hash coding with allowable errors". Communications of the ACM. 13 (7): 422–426. doi:10.1145/362686.362692. ISSN 0001-0782. S2CID 7931252.

[14] Aragon, C.R.; Seidel, R.G. (October 1989). "यादृच्छिक खोज पेड़". 30th Annual Symposium on Foundations of Computer Science: 540–545. doi:10.1109/SFCS.1989.63531. ISBN 0-8186-1982-1.

[15] Pugh, William (April 1989). Concurrent Maintenance of Skip Lists (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.

[:1-16] 16.0 ^16.1 Alon, Noga (2016). संभाव्य विधि. Joel H. Spencer (Fourth ed.). Hoboken, New Jersey. ISBN 978-1-119-06195-3. OCLC 910535517.{{cite book}}: CS1 maint: location missing publisher (link)

[17] P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292--294 MR8,479d; Zentralblatt 32,192.

[18] Erdös, P. (1959). "ग्राफ सिद्धांत और संभावना". Canadian Journal of Mathematics (in English). 11: 34–38. doi:10.4153/CJM-1959-003-9. ISSN 0008-414X. S2CID 122784453.

[19] Seidel R. Backwards Analysis of Randomized Geometric Algorithms.

[20] A. A. Tsay, W. S. Lovejoy, David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, 24(2):383–413, 1999.

[21] Alippi, Cesare (2014), Intelligence for Embedded Systems, Springer, ISBN 978-3-319-05278-6.

[22] Kushilevitz, Eyal; Nisan, Noam (2006), Communication Complexity, Cambridge University Press, ISBN 9780521029834. For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.

[23] Dyer, M.; Frieze, A.; Kannan, R. (1991), "A random polynomial-time algorithm for approximating the volume of convex bodies" (PDF), Journal of the ACM, 38 (1): 1–17, doi:10.1145/102782.102783, S2CID 13268711

[24] Füredi, Z.; Bárány, I. (1986), "Computing the volume is difficult", Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986) (PDF), New York, NY: ACM, pp. 442–447, CiteSeerX 10.1.1.726.9448, doi:10.1145/12130.12176, ISBN 0-89791-193-8, S2CID 17867291

[25] Shamir, A. (1992), "IP = PSPACE", Journal of the ACM, 39 (4): 869–877, doi:10.1145/146585.146609, S2CID 315182

[26] Cook, Matthew; Soloveichik, David; Winfree, Erik; Bruck, Jehoshua (2009), "Programmability of chemical reaction networks", in Condon, Anne; Harel, David; Kok, Joost N.; Salomaa, Arto; Winfree, Erik (eds.), Algorithmic Bioprocesses (PDF), Natural Computing Series, Springer-Verlag, pp. 543–584, doi:10.1007/978-3-540-88869-7_27.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

@@ Line 1: / Line 1: @@
 {{short description|Algorithm that employs a degree of randomness as part of its logic or procedure}}
-{{Probabilistic}}
-{{distinguish-redirect|Randomized algorithms|Algorithmic randomness}}
-एक यादृच्छिक एल्गोरिदम एक एल्गोरिदम है जो अपने तर्क या प्रक्रिया के हिस्से के रूप में यादृच्छिकता की डिग्री को नियोजित करता है। एल्गोरिथ्म आम तौर पर यादृच्छिक बिट्स द्वारा निर्धारित यादृच्छिक के सभी संभावित विकल्पों पर औसत मामले में अच्छा प्रदर्शन प्राप्त करने की आशा में, अपने व्यवहार को निर्देशित करने के लिए एक सहायक इनपुट के रूप में [[समान वितरण (असतत)]] बिट्स का उपयोग करता है; इस प्रकार या तो चलने का समय, या आउटपुट (या दोनों) यादृच्छिक चर हैं।
-किसी को यादृच्छिक इनपुट का उपयोग करने वाले एल्गोरिदम के बीच अंतर करना होगा ताकि वे हमेशा सही उत्तर के साथ समाप्त हो जाएं, लेकिन जहां अपेक्षित चलने का समय सीमित है ([[लास वेगास [[ कलन विधि ]]]], उदाहरण के लिए [[जल्दी से सुलझाएं]]<ref>{{Cite journal|last=Hoare|first=C. A. R.|date=July 1961|title=Algorithm 64: Quicksort|journal=Commun. ACM|volume=4|issue=7|pages=321–|doi=10.1145/366622.366644|issn=0001-0782}}</ref>), और एल्गोरिदम जिनके पास गलत परिणाम उत्पन्न करने का मौका है ([[मोंटे कार्लो एल्गोरिथ्म]], उदाहरण के लिए न्यूनतम फीडबैक आर्क सेट समस्या के लिए मोंटे कार्लो एल्गोरिदम<ref>{{Cite journal|last=Kudelić|first=Robert|date=2016-04-01|title=न्यूनतम प्रतिक्रिया चाप सेट समस्या के लिए मोंटे-कार्लो यादृच्छिक एल्गोरिथ्म|journal=Applied Soft Computing|volume=41|pages=235–246|doi=10.1016/j.asoc.2015.12.018}}</ref>) या या तो विफलता का संकेत देकर या समाप्त करने में विफल होने पर परिणाम उत्पन्न करने में विफल। कुछ मामलों में, समस्या को हल करने का एकमात्र व्यावहारिक साधन संभाव्य एल्गोरिदम हैं।<ref>"In [[primality test|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>
-सामान्य अभ्यास में, यादृच्छिक बिट्स के एक सच्चे स्रोत के स्थान पर एक [[छद्म यादृच्छिक संख्या जनरेटर]] का उपयोग करके यादृच्छिक एल्गोरिदम का अनुमान लगाया जाता है; ऐसा कार्यान्वयन अपेक्षित सैद्धांतिक व्यवहार और गणितीय गारंटी से विचलित हो सकता है जो एक आदर्श वास्तविक यादृच्छिक संख्या जनरेटर के अस्तित्व पर निर्भर हो सकता है।
+'''यादृच्छिक एल्गोरिदम''' एक एल्गोरिदम है जो अपने तर्क या प्रक्रिया के भूमिका के रूप में यादृच्छिकता की कोटि को नियोजित करता है। एल्गोरिथ्म सामान्यतः यादृच्छिक बिट्स द्वारा निर्धारित यादृच्छिक के सभी संभावित विकल्पों पर "औसत मामले" में अच्छा प्रदर्शन प्राप्त करने की आशा में, अपने व्यवहार को निर्देशित करने के लिए सहायक इनपुट के रूप में [[समान वितरण (असतत)|एक समान यादृच्छिक (असतत)]] बिट्स का उपयोग करता है; इस प्रकार या तो चलने का समय, या आउटपुट (या दोनों) यादृच्छिक चर हैं।
+किसी को यादृच्छिक इनपुट का उपयोग करने वाले एल्गोरिदम के बीच अंतर करना होगा जिससे कि वे हमेशा सही उत्तर के साथ समाप्त हो जाएं, लेकिन जहां अपेक्षित चलने का समय सीमित है (लास वेगास [[ कलन विधि |कलन विधि]], उदाहरण के लिए [[जल्दी से सुलझाएं|क्विक सॉर्ट]]<ref>{{Cite journal|last=Hoare|first=C. A. R.|date=July 1961|title=Algorithm 64: Quicksort|journal=Commun. ACM|volume=4|issue=7|pages=321–|doi=10.1145/366622.366644|issn=0001-0782}}</ref>), और एल्गोरिदम जिनके पास गलत परिणाम उत्पन्न करने का मौका है ([[मोंटे कार्लो एल्गोरिथ्म]], उदाहरण के लिए न्यूनतम फीडबैक आर्क सेट समस्या के लिए मोंटे कार्लो एल्गोरिदम<ref>{{Cite journal|last=Kudelić|first=Robert|date=2016-04-01|title=न्यूनतम प्रतिक्रिया चाप सेट समस्या के लिए मोंटे-कार्लो यादृच्छिक एल्गोरिथ्म|journal=Applied Soft Computing|volume=41|pages=235–246|doi=10.1016/j.asoc.2015.12.018}}</ref>) या तो विफलता का संकेत देकर या समाप्त करने में विफल होने पर परिणाम उत्पन्न करने में विफल हैं। कुछ स्थितियों में, समस्या को हल करने का एकमात्र व्यावहारिक साधन संभाव्य एल्गोरिदम हैं।<ref>"In [[primality test|testing primality]] of very large numbers chosen at random, the chance of stumbling upon a value that fools the [[Fermat primality test|Fermat test]] is less than the chance that [[cosmic radiation]] will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." [[Hal Abelson]] and [[Gerald J. Sussman]] (1996). ''[[Structure and Interpretation of Computer Programs]]''. [[MIT Press]], [http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#footnote_Temp_80 section 1.2].</ref>
+सामान्य अभ्यास में, यादृच्छिक बिट्स के सच्चे स्रोत के स्थान पर [[छद्म यादृच्छिक संख्या जनरेटर]] का उपयोग करके यादृच्छिक एल्गोरिदम का अनुमान लगाया जाता है; ऐसा कार्यान्वयन अपेक्षित सैद्धांतिक व्यवहार और गणितीय गारंटी से विचलित हो सकता है जो एक आदर्श वास्तविक यादृच्छिक संख्या जनरेटर के अस्तित्व पर निर्भर हो सकता है।
 == प्रेरणा ==
-एक प्रेरक उदाहरण के रूप में, n तत्वों की एक [[सरणी डेटा संरचना]] में 'a' खोजने की समस्या पर विचार करें।
+प्रेरक उदाहरण के रूप में, ''n'' तत्वों की [[सरणी डेटा संरचना]] में '''a''<nowiki/>' निष्कर्ष की समस्या पर विचार करें।
-'इनपुट': n≥2 तत्वों की एक सरणी, जिसमें आधे 'ए' हैं और अन्य आधे 'बी' हैं।
+'''इनपुट''': n≥2 तत्वों की सरणी, जिसमें आधे ''a'' हैं और अन्य आधे ''b'' हैं।
-'आउटपुट': सरणी में 'ए' खोजें।
+'''आउटपुट''': सरणी में ''a'' खोजें।
 हम एल्गोरिथ्म के दो संस्करण देते हैं, एक लास वेगास एल्गोरिथम और एक मोंटे कार्लो एल्गोरिथम।
@@ Line 27: / Line 29: @@
 end
 </syntaxhighlight>
-यह एल्गोरिथ्म प्रायिकता 1 के साथ सफल होता है। पुनरावृत्तियों की संख्या भिन्न होती है और मनमाने ढंग से बड़ी हो सकती है, लेकिन पुनरावृत्तियों की अपेक्षित संख्या है
+यह एल्गोरिथ्म प्रायिकता 1 के साथ सफल होता है। पुनरावृत्तियों की संख्या भिन्न होती है और अक्रमतः बड़ी हो सकती है, लेकिन पुनरावृत्तियों की अपेक्षित संख्या है
 :<math> \lim_{n \to \infty} \sum_{i = 1}^{n} \frac{i}{2^i} = 2</math>
@@ Line 43: / Line 45: @@
 end
 </syntaxhighlight>
-यदि एक 'ए' पाया जाता है, तो एल्गोरिथम सफल होता है, अन्यथा एल्गोरिथम विफल हो जाता है। के पुनरावृत्तियों के बाद, 'ए' खोजने की संभावना है:
+यदि '<nowiki/>''a''<nowiki/>' पाया जाता है, तो एल्गोरिथम सफल होता है, अन्यथा एल्गोरिथम विफल हो जाता है। ''k'' पुनरावृत्तियों के बाद, '''a''<nowiki/>' निष्कर्ष की संभावना है:
 <div style= text-align:center; >
 <math>\Pr[\mathrm{find~a}] = 1 - (1/2)^k</math>
 </div>
-यह एल्गोरिदम सफलता की गारंटी नहीं देता है, लेकिन रन टाइम सीमित है। पुनरावृत्तियों की संख्या हमेशा k से कम या उसके बराबर होती है। K को स्थिर रखने के लिए रन टाइम (अपेक्षित और पूर्ण) है <math>\Theta(1)</math>.
+यह एल्गोरिदम सफलता की गारंटी नहीं देता है, लेकिन रन टाइम सीमित है। पुनरावृत्तियों की संख्या हमेशा k से कम या उसके बराबर होती है। k को स्थिर रखने के लिए रन टाइम (अपेक्षित और पूर्ण) <math>\Theta(1)</math> है
-रैंडमाइज्ड एल्गोरिदम विशेष रूप से उपयोगी होते हैं जब एक दुर्भावनापूर्ण विरोधी या [[हमलावर]] का सामना करना पड़ता है जो जानबूझकर एल्गोरिदम को खराब इनपुट देने की कोशिश करता है (देखें [[सबसे खराब स्थिति जटिलता]] और [[प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम)]]) जैसे कैदी की दुविधा में। यही कारण है कि [[क्रिप्टोग्राफी]] में यादृच्छिकता सर्वव्यापी है। क्रिप्टोग्राफ़िक अनुप्रयोगों में, छद्म-यादृच्छिक संख्याओं का उपयोग नहीं किया जा सकता है, क्योंकि विरोधी उन्हें भविष्यवाणी कर सकते हैं, एल्गोरिदम प्रभावी रूप से निर्धारक बनाते हैं। इसलिए, या तो वास्तव में यादृच्छिक संख्याओं का स्रोत या क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर की आवश्यकता होती है। एक अन्य क्षेत्र जिसमें यादृच्छिकता निहित है, [[ एक कंप्यूटर जितना ]] है।
+यादृच्छिक एल्गोरिदम विशेष रूप से उपयोगी होते हैं जब दुर्भावनापूर्ण विपक्षी या [[हमलावर|आक्रामक]] का सामना करना पड़ता है जो जानबूझकर एल्गोरिदम को खराब इनपुट देने की कोशिश करता है (देखें [[सबसे खराब स्थिति जटिलता|वर्स्ट-केस कम्प्लेक्सिटी]] और [[प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम)]]) जैसे बंदी की दुविधा में है। यही कारण है कि [[क्रिप्टोग्राफी]] में यादृच्छिकता सर्वव्यापी है। क्रिप्टोग्राफ़िक अनुप्रयोगों में, छद्म-यादृच्छिक संख्याओं का उपयोग नहीं किया जा सकता है, क्योंकि विरोधी उन्हें पूर्वानुमान कर सकते हैं, एल्गोरिदम प्रभावी रूप से निर्धारक बनाते हैं। इसलिए, या तो वास्तव में यादृच्छिक संख्याओं का स्रोत या क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर की आवश्यकता होती है। अन्य क्षेत्र जिसमें यादृच्छिकता निहित है, [[ एक कंप्यूटर जितना | क्वांटम कम्प्यूटिंग]] है।
-उपरोक्त उदाहरण में, लास वेगास एल्गोरिथम हमेशा सही उत्तर देता है, लेकिन इसका चलने का समय एक यादृच्छिक चर है। मोंटे कार्लो एल्गोरिथम (सिमुलेशन के लिए [[मोंटे कार्लो विधि]] से संबंधित) को उस समय की मात्रा में पूरा करने की गारंटी दी जाती है जिसे एक फ़ंक्शन द्वारा इनपुट आकार और उसके पैरामीटर k द्वारा बाध्य किया जा सकता है, लेकिन त्रुटि की एक छोटी संभावना की अनुमति देता है। ध्यान दें कि किसी भी लास वेगास एल्गोरिथम को एक मोंटे कार्लो एल्गोरिथम (मार्कोव की असमानता के माध्यम से) में परिवर्तित किया जा सकता है, यदि यह एक निर्दिष्ट समय के भीतर पूरा करने में विफल रहता है, तो यह एक मनमाना, संभवतः गलत उत्तर देता है। इसके विपरीत, यदि कोई उत्तर सही है या नहीं, यह जांचने के लिए एक कुशल सत्यापन प्रक्रिया मौजूद है, तो मोंटे कार्लो एल्गोरिथम को एक सही उत्तर प्राप्त होने तक मोंटे कार्लो एल्गोरिथम को बार-बार चलाकर लास वेगास एल्गोरिथम में परिवर्तित किया जा सकता है।
+उपरोक्त उदाहरण में, लास वेगास एल्गोरिथम हमेशा सही उत्तर देता है, लेकिन इसका चलने का समय यादृच्छिक चर है। मोंटे कार्लो एल्गोरिथम (सिमुलेशन के लिए [[मोंटे कार्लो विधि]] से संबंधित) को उस समय की मात्रा में पूरा करने की गारंटी दी जाती है जिसे फ़ंक्शन द्वारा इनपुट आकार और उसके पैरामीटर ''k'' द्वारा बाध्य किया जा सकता है, लेकिन त्रुटि की छोटी संभावना की अनुमति देता है। ध्यान दें कि किसी भी लास वेगास एल्गोरिथम को मोंटे कार्लो एल्गोरिथम (मार्कोव की असमानता के माध्यम से) में परिवर्तित किया जा सकता है, यदि यह निर्दिष्ट समय के भीतर पूरा करने में विफल रहता है, तो यह यादृच्छिक, संभवतः गलत उत्तर देता है। इसके विपरीत, यदि कोई उत्तर सही है या नहीं, यह जांचने के लिए कुशल सत्यापन प्रक्रिया सम्मिलित है, तो मोंटे कार्लो एल्गोरिथम को सही उत्तर प्राप्त होने तक मोंटे कार्लो एल्गोरिथम को बार-बार चलाकर लास वेगास एल्गोरिथम में परिवर्तित किया जा सकता है।
-== कम्प्यूटेशनल जटिलता ==
+== अभिकलनात्मक जटिलता ==
-<!-- [[Probabilistic complexity]] and  [[Probabilistic computational complexity]] redirect here -->
+[[कम्प्यूटेशनल जटिलता सिद्धांत|अभिकलनात्मक जटिलता सिद्धांत]] मॉडल यादृच्छिक एल्गोरिदम को [[संभाव्य ट्यूरिंग मशीन]] के रूप में लास वेगास एल्गोरिथ्म और मोंटे कार्लो एल्गोरिदम दोनों पर विचार किया जाता है, और कई [[जटिलता वर्ग]] का अध्ययन किया जाता है। सबसे बुनियादी यादृच्छिक जटिलता वर्ग आर[[पी (जटिलता)]] है, जो [[निर्णय समस्या]]ओं का वर्ग है जिसके लिए कुशल (बहुपद काल) यादृच्छिक एल्गोरिदम (या संभाव्य ट्यूरिंग मशीन) है जो पूर्ण निश्चितता के साथ नहीं- उदाहरण को पहचानता है और हाँ-उदाहरण को पहचानता है कम से कम 1/2 की संभावना के साथ है। RP के लिए पूरक वर्ग co-RP है। बहुपद काल औसत केस रनिंग टाइम वाले एल्गोरिदम (संभवतः गैर-समापन) वाले समस्या वर्ग जिनके आउटपुट हमेशा सही होते हैं उन्हें [[ZPP (जटिलता)|ज़ेडपीपी (जटिलता)]] में कहा जाता है।
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] मॉडल यादृच्छिक एल्गोरिदम को [[संभाव्य ट्यूरिंग मशीन]]ों के रूप में। लास वेगास एल्गोरिथ्म और मोंटे कार्लो एल्गोरिदम दोनों पर विचार किया जाता है, और कई [[जटिलता वर्ग]]ों का अध्ययन किया जाता है। सबसे बुनियादी यादृच्छिक जटिलता वर्ग [[आर[[पी (जटिलता)]]]] है, जो [[निर्णय समस्या]]ओं का वर्ग है जिसके लिए एक कुशल (बहुपद समय) यादृच्छिक एल्गोरिदम (या संभाव्य ट्यूरिंग मशीन) है जो पूर्ण निश्चितता के साथ नो-इंस्टेंस को पहचानता है और हाँ-उदाहरणों को पहचानता है कम से कम 1/2 की संभावना के साथ। आरपी के लिए पूरक वर्ग सह-आरपी है। बहुपद समय औसत केस रनिंग टाइम वाले एल्गोरिदम (संभवतः गैर-समापन) वाले समस्या वर्ग जिनके आउटपुट हमेशा सही होते हैं उन्हें [[ZPP (जटिलता)]] में कहा जाता है।
-समस्याओं का वह वर्ग जिसके लिए हाँ और नहीं दोनों उदाहरणों को कुछ त्रुटि के साथ पहचानने की अनुमति दी जाती है, [[परिबद्ध-त्रुटि संभाव्य बहुपद]] कहलाती है। यह वर्ग P (जटिलता) के यादृच्छिक समतुल्य के रूप में कार्य करता है, अर्थात BPP कुशल यादृच्छिक एल्गोरिदम के वर्ग का प्रतिनिधित्व करता है।
+समस्याओं का वह वर्ग जिसके लिए हाँ और नहीं दोनों उदाहरणों को कुछ त्रुटि के साथ पहचानने की अनुमति दी जाती है, [[परिबद्ध-त्रुटि संभाव्य बहुपद]] कहलाती है। यह वर्ग P (जटिलता) के यादृच्छिक समतुल्य के रूप में कार्य करता है, अर्थात बीपीपी कुशल यादृच्छिक एल्गोरिदम के वर्ग का प्रतिनिधित्व करता है।
 == प्रारंभिक इतिहास ==
-=== छँटाई ===
+=== सॉर्टिंग ===
-Quicksort की खोज 1959 में [[टोनी होरे]] द्वारा की गई थी, और बाद में 1961 में प्रकाशित हुई।<ref>{{Cite journal |last=Hoare |first=C. A. R. |date=July 1961 |title=Algorithm 64: Quicksort |url=https://dl.acm.org/doi/10.1145/366622.366644 |journal=Communications of the ACM |language=en |volume=4 |issue=7 |pages=321 |doi=10.1145/366622.366644 |issn=0001-0782}}</ref> उसी वर्ष, होरे ने [[तुरंत चयन]] प्रकाशित किया,<ref>{{Cite journal |last=Hoare |first=C. A. R. |date=July 1961 |title=Algorithm 65: find |url=https://dl.acm.org/doi/10.1145/366622.366647 |journal=Communications of the ACM |language=en |volume=4 |issue=7 |pages=321–322 |doi=10.1145/366622.366647 |issn=0001-0782}}</ref> जो रैखिक अपेक्षित समय में किसी सूची का मध्य तत्व पाता है। यह 1973 तक खुला रहा कि क्या नियतात्मक रैखिक-समय एल्गोरिथम मौजूद है।<ref>{{Cite journal |last1=Blum |first1=Manuel |last2=Floyd |first2=Robert W. |last3=Pratt |first3=Vaughan |last4=Rivest |first4=Ronald L. |last5=Tarjan |first5=Robert E. |date=August 1973 |title=चयन के लिए समय सीमा|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 |journal=Journal of Computer and System Sciences |language=en |volume=7 |issue=4 |pages=448–461 |doi=10.1016/S0022-0000(73)80033-9}}</ref>
+क्विक सॉर्ट की खोज 1959 में [[टोनी होरे]] द्वारा की गई थी, और बाद में 1961 में प्रकाशित हुई थी।<ref>{{Cite journal |last=Hoare |first=C. A. R. |date=July 1961 |title=Algorithm 64: Quicksort |url=https://dl.acm.org/doi/10.1145/366622.366644 |journal=Communications of the ACM |language=en |volume=4 |issue=7 |pages=321 |doi=10.1145/366622.366644 |issn=0001-0782}}</ref> उसी वर्ष, होरे ने [[तुरंत चयन|त्वरित चयन एल्गोरिथ्म]] प्रकाशित किया,<ref>{{Cite journal |last=Hoare |first=C. A. R. |date=July 1961 |title=Algorithm 65: find |url=https://dl.acm.org/doi/10.1145/366622.366647 |journal=Communications of the ACM |language=en |volume=4 |issue=7 |pages=321–322 |doi=10.1145/366622.366647 |issn=0001-0782}}</ref> जो रैखिक अपेक्षित समय में किसी सूची का मध्य तत्व पाता है। यह 1973 तक खुला रहा कि क्या नियतात्मक रैखिक-समय एल्गोरिथम सम्मिलित है।<ref>{{Cite journal |last1=Blum |first1=Manuel |last2=Floyd |first2=Robert W. |last3=Pratt |first3=Vaughan |last4=Rivest |first4=Ronald L. |last5=Tarjan |first5=Robert E. |date=August 1973 |title=चयन के लिए समय सीमा|url=https://linkinghub.elsevier.com/retrieve/pii/S0022000073800339 |journal=Journal of Computer and System Sciences |language=en |volume=7 |issue=4 |pages=448–461 |doi=10.1016/S0022-0000(73)80033-9}}</ref>
 === संख्या सिद्धांत ===
-में, [[हेनरी कैबॉर्न पॉकलिंगटन]] ने एक यादृच्छिक एल्गोरिथम पेश किया, जिसे पॉकलिंगटन के एल्गोरिथ्म के रूप में जाना जाता है, जो कुशलतापूर्वक [[वर्गमूल]] मॉड्यूलो प्राइम नंबरों को खोजने के लिए है।<ref>{{citation |last1=Williams |first1=H. C. |title=Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993 |volume=48 |pages=481–531 |year=1994 |editor-last=Gautschi |editor-first=Walter |series=Proceedings of Symposia in Applied Mathematics |contribution=Factoring integers before computers |publisher=Amer. Math. Soc., Providence, RI |doi=10.1090/psapm/048/1314885 |mr=1314885 |last2=Shallit |first2=J. O. |author1-link=Hugh C. Williams |author2-link=Jeffrey Shallit}}; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".</ref>
+में, [[हेनरी कैबॉर्न पॉकलिंगटन]] ने यादृच्छिक एल्गोरिथम पेश किया, जिसे पॉकलिंगटन के एल्गोरिथ्म के रूप में जाना जाता है, जो कुशलतापूर्वक [[वर्गमूल]] मॉड्यूलो अभाज्य संख्या को निष्कर्ष के लिए है।<ref>{{citation |last1=Williams |first1=H. C. |title=Mathematics of Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13, 1993 |volume=48 |pages=481–531 |year=1994 |editor-last=Gautschi |editor-first=Walter |series=Proceedings of Symposia in Applied Mathematics |contribution=Factoring integers before computers |publisher=Amer. Math. Soc., Providence, RI |doi=10.1090/psapm/048/1314885 |mr=1314885 |last2=Shallit |first2=J. O. |author1-link=Hugh C. Williams |author2-link=Jeffrey Shallit}}; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".</ref>1970 में, [[एल्विन बर्लेकैंप]] ने परिमित क्षेत्र पर बहुपद की वर्गमूल की कुशलता से गणना करने के लिए यादृच्छिक एल्गोरिथ्म पेश किया है।<ref>{{Cite journal |last=Berlekamp |first=E. R. |date=1971 |title=बड़े परिमित क्षेत्रों पर बहुपदों का गुणनखंडन*|url=http://portal.acm.org/citation.cfm?doid=800204.806290 |journal=Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation - SYMSAC '71 |language=en |location=Los Angeles, California, United States |publisher=ACM Press |pages=223 |doi=10.1145/800204.806290|isbn=9781450377867 |s2cid=6464612 }}</ref> 1977 में, रॉबर्ट एम. सोलोवे और [[वोल्कर स्ट्रास]] ने बहुपद-समय सोलोवे-स्ट्रैसन [[प्रारंभिक परीक्षण]] की खोज की थी (अर्थात, किसी संख्या की प्रारंभिक परीक्षा का निर्धारण)। इसके तुरंत बाद माइकल ओ. राबिन ने प्रदर्शित किया कि 1976 मिलर के प्रारंभिक परीक्षण को बहुपद-समय यादृच्छिक एल्गोरिथम में भी बदला जा सकता है। उस समय, प्रारंभिक परीक्षण के लिए कोई सिद्ध बहुपद-समय नियतात्मक एल्गोरिथम ज्ञात नहीं था।
-में, [[एल्विन बर्लेकैंप]] ने एक परिमित क्षेत्र पर एक बहुपद की जड़ों की कुशलता से गणना करने के लिए एक यादृच्छिक एल्गोरिथ्म पेश किया।<ref>{{Cite journal |last=Berlekamp |first=E. R. |date=1971 |title=बड़े परिमित क्षेत्रों पर बहुपदों का गुणनखंडन*|url=http://portal.acm.org/citation.cfm?doid=800204.806290 |journal=Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation - SYMSAC '71 |language=en |location=Los Angeles, California, United States |publisher=ACM Press |pages=223 |doi=10.1145/800204.806290|isbn=9781450377867 |s2cid=6464612 }}</ref> 1977 में, रॉबर्ट एम. सोलोवे और [[वोल्कर स्ट्रास]] ने एक बहुपद-समय सोलोवे-स्ट्रैसन [[प्रारंभिक परीक्षण]] की खोज की (अर्थात, किसी संख्या की प्रारंभिक परीक्षा का निर्धारण)। इसके तुरंत बाद माइकल ओ. राबिन ने प्रदर्शित किया कि 1976 मिलर-राबिन प्राइमैलिटी टेस्ट|मिलर के प्रिमैलिटी टेस्ट को भी एक बहुपद-समय यादृच्छिक एल्गोरिथम में बदला जा सकता है। उस समय, प्रारंभिक परीक्षण के लिए कोई सिद्ध बहुपद-समय नियतात्मक एल्गोरिथम ज्ञात नहीं था।
 === डेटा संरचनाएं ===
-जल्द से जल्द यादृच्छिक डेटा संरचनाओं में से एक [[ हैश तालिका ]] है, जिसे 1953 में [[आईबीएम]] में [[ उनका पीटर लुहान ]] द्वारा पेश किया गया था।<ref name=":0">{{Cite book |last=Knuth |first=Donald E. |url=https://dl.acm.org/doi/10.5555/280635 |title=The art of computer programming, volume 3: (2nd ed.) sorting and searching |date=1998 |publisher=Addison Wesley Longman Publishing Co., Inc. |isbn=978-0-201-89685-5 |location=USA |pages=536–549 }}</ref> Luhn की हैश टेबल ने टक्करों को हल करने के लिए चेनिंग का इस्तेमाल किया और [[ लिंक्ड सूची ]] के पहले अनुप्रयोगों में से एक था।<ref name=":0" />इसके बाद, 1954 में, [[आईबीएम रिसर्च]] के [[जीन अमदहल]], ऐलेन एम। मैकग्रा, [[नथानिएल रोचेस्टर (कंप्यूटर वैज्ञानिक)]], और [[आर्थर सैमुअल (कंप्यूटर वैज्ञानिक)]] ने [[रैखिक जांच]] शुरू की,<ref name=":0" />हालांकि 1957 में स्वतंत्र रूप से [[एंड्री एर्शोव]] का भी यही विचार था।<ref name=":0" />1962 में, [[डोनाल्ड नुथ]] ने रेखीय जांच का पहला सही विश्लेषण किया,<ref name=":0" />हालाँकि उनके विश्लेषण वाला ज्ञापन बहुत बाद तक प्रकाशित नहीं हुआ था।<ref>[[Donald Knuth|Knuth, Donald]] (1963), ''[https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html Notes on "Open" Addressing]'', archived from the original on 2016-03-03</ref> पहला प्रकाशित विश्लेषण 1966 में कोनहेम और वीस के कारण हुआ था।<ref>{{Cite journal |last1=Konheim |first1=Alan G. |last2=Weiss |first2=Benjamin |date=November 1966 |title=एक अधिभोग अनुशासन और अनुप्रयोग|url=http://dx.doi.org/10.1137/0114101 |journal=SIAM Journal on Applied Mathematics |volume=14 |issue=6 |pages=1266–1274 |doi=10.1137/0114101 |issn=0036-1399}}</ref>
+जल्द से जल्द यादृच्छिक डेटा संरचनाओं में से [[ हैश तालिका |हैश तालिका]] है, जिसे 1953 में [[आईबीएम]] में [[ उनका पीटर लुहान | हंस पीटर लुहान]] द्वारा पेश किया गया था।<ref name=":0">{{Cite book |last=Knuth |first=Donald E. |url=https://dl.acm.org/doi/10.5555/280635 |title=The art of computer programming, volume 3: (2nd ed.) sorting and searching |date=1998 |publisher=Addison Wesley Longman Publishing Co., Inc. |isbn=978-0-201-89685-5 |location=USA |pages=536–549 }}</ref> लुहान की हैश टेबल ने संघट्ट को हल करने के लिए चेनिंग का उपयोग किया और [[ लिंक्ड सूची |लिंक्ड सूची]] के पहले अनुप्रयोगों में से एक था।<ref name=":0" />इसके बाद, 1954 में, [[आईबीएम रिसर्च]] के [[जीन अमदहल]], ऐलेन एम. मैकग्रा, [[नथानिएल रोचेस्टर (कंप्यूटर वैज्ञानिक)]], और [[आर्थर सैमुअल (कंप्यूटर वैज्ञानिक)]] ने [[रैखिक जांच]] प्रारंभ की,<ref name=":0" />चूंकि 1957 में स्वतंत्र रूप से [[एंड्री एर्शोव]] का भी यही विचार था।<ref name=":0" />1962 में, [[डोनाल्ड नुथ]] ने रेखीय जांच का पहला सही विश्लेषण किया,<ref name=":0" />हालाँकि उनके विश्लेषण वाला ज्ञापन बहुत बाद तक प्रकाशित नहीं हुआ था।<ref>[[Donald Knuth|Knuth, Donald]] (1963), ''[https://web.archive.org/web/20160303225949/http://algo.inria.fr/AofA/Research/11-97.html Notes on "Open" Addressing]'', archived from the original on 2016-03-03</ref> पहला प्रकाशित विश्लेषण 1966 में कोनहेम और वीस के कारण हुआ था।<ref>{{Cite journal |last1=Konheim |first1=Alan G. |last2=Weiss |first2=Benjamin |date=November 1966 |title=एक अधिभोग अनुशासन और अनुप्रयोग|url=http://dx.doi.org/10.1137/0114101 |journal=SIAM Journal on Applied Mathematics |volume=14 |issue=6 |pages=1266–1274 |doi=10.1137/0114101 |issn=0036-1399}}</ref>
-हैश टेबल पर प्रारंभिक कार्य या तो पूरी तरह यादृच्छिक हैश फ़ंक्शन तक पहुंच मानते हैं या मानते हैं कि चाबियाँ स्वयं यादृच्छिक थीं।<ref name=":0" />1979 में, कार्टर और वेगमैन ने [[यूनिवर्सल हैशिंग]] की शुरुआत की,<ref>{{Cite journal |last1=Carter |first1=J. Lawrence |last2=Wegman |first2=Mark N. |date=1979-04-01 |title=हैश फ़ंक्शंस की सार्वभौमिक कक्षाएं|url=https://dx.doi.org/10.1016/0022-0000%2879%2990044-8 |journal=Journal of Computer and System Sciences |language=en |volume=18 |issue=2 |pages=143–154 |doi=10.1016/0022-0000(79)90044-8 |issn=0022-0000}}</ref> जो उन्होंने दिखाया कि प्रति ऑपरेशन निरंतर अपेक्षित समय के साथ जंजीर हैश टेबल को लागू करने के लिए इस्तेमाल किया जा सकता है।
-यादृच्छिक डेटा संरचनाओं पर प्रारंभिक कार्य भी हैश टेबल से आगे बढ़े। 1970 में, बर्टन हावर्ड ब्लूम ने एक अनुमानित-सदस्यता डेटा संरचना पेश की जिसे [[ब्लूम फिल्टर]] के रूप में जाना जाता है।<ref>{{Cite journal |last=Bloom |first=Burton H. |date=July 1970 |title=Space/time trade-offs in hash coding with allowable errors |url=http://dx.doi.org/10.1145/362686.362692 |journal=Communications of the ACM |volume=13 |issue=7 |pages=422–426 |doi=10.1145/362686.362692 |s2cid=7931252 |issn=0001-0782}}</ref> 1989 में, [[रायमुंड सीडेल]] और सेसिलिया आर. आरागॉन ने एक यादृच्छिक संतुलित खोज वृक्ष पेश किया जिसे [[ट्रीप]] के रूप में जाना जाता है।<ref>{{Cite journal |last1=Aragon |first1=C.R. |last2=Seidel |first2=R.G. |date=October 1989 |title=यादृच्छिक खोज पेड़|url=https://ieeexplore.ieee.org/document/63531 |journal=30th Annual Symposium on Foundations of Computer Science |pages=540–545 |doi=10.1109/SFCS.1989.63531|isbn=0-8186-1982-1 }}</ref> उसी वर्ष, [[विलियम पुघ (कंप्यूटर वैज्ञानिक)]] ने एक और यादृच्छिक खोज ट्री पेश किया जिसे स्किप सूची के रूप में जाना जाता है।<ref>[[William Pugh (computer scientist)|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>
+हैश टेबल पर प्रारंभिक कार्य या तो पूरी तरह यादृच्छिक हैश फ़ंक्शन तक पहुंच मानते हैं या मानते हैं कि कीज़ स्वयं यादृच्छिक थीं।<ref name=":0" />1979 में, कार्टर और वेगमैन ने [[यूनिवर्सल हैशिंग]] की शुरुआत की,<ref>{{Cite journal |last1=Carter |first1=J. Lawrence |last2=Wegman |first2=Mark N. |date=1979-04-01 |title=हैश फ़ंक्शंस की सार्वभौमिक कक्षाएं|url=https://dx.doi.org/10.1016/0022-0000%2879%2990044-8 |journal=Journal of Computer and System Sciences |language=en |volume=18 |issue=2 |pages=143–154 |doi=10.1016/0022-0000(79)90044-8 |issn=0022-0000}}</ref> जो उन्होंने दिखाया कि प्रति ऑपरेशन निरंतर अपेक्षित समय के साथ चेन हैश टेबल को लागू करने के लिए उपयोग किया जा सकता है।
+यादृच्छिक डेटा संरचनाओं पर प्रारंभिक कार्य भी हैश टेबल से आगे बढ़ता है। 1970 में, बर्टन हावर्ड ब्लूम ने अनुमानित-सदस्यता डेटा संरचना पेश की जिसे [[ब्लूम फिल्टर]] के रूप में जाना जाता है।<ref>{{Cite journal |last=Bloom |first=Burton H. |date=July 1970 |title=Space/time trade-offs in hash coding with allowable errors |url=http://dx.doi.org/10.1145/362686.362692 |journal=Communications of the ACM |volume=13 |issue=7 |pages=422–426 |doi=10.1145/362686.362692 |s2cid=7931252 |issn=0001-0782}}</ref> 1989 में, [[रायमुंड सीडेल]] और सेसिलिया आर. आरागॉन ने यादृच्छिक संतुलित खोज तरु पेश किया जिसे [[ट्रीप]] के रूप में जाना जाता है।<ref>{{Cite journal |last1=Aragon |first1=C.R. |last2=Seidel |first2=R.G. |date=October 1989 |title=यादृच्छिक खोज पेड़|url=https://ieeexplore.ieee.org/document/63531 |journal=30th Annual Symposium on Foundations of Computer Science |pages=540–545 |doi=10.1109/SFCS.1989.63531|isbn=0-8186-1982-1 }}</ref> उसी वर्ष, [[विलियम पुघ (कंप्यूटर वैज्ञानिक)]] ने एक और यादृच्छिक खोज तरु पेश किया जिसे स्किप सूची के रूप में जाना जाता है।<ref>[[William Pugh (computer scientist)|Pugh, William]] (April 1989). ''[http://drum.lib.umd.edu/handle/1903/542 Concurrent Maintenance of Skip Lists]'' (PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.</ref>
 === कॉम्बिनेटरिक्स में अंतर्निहित उपयोग ===
-कंप्यूटर विज्ञान में यादृच्छिक एल्गोरिदम के लोकप्रिय होने से पहले, पॉल एर्डोस ने गणितीय वस्तुओं के अस्तित्व को स्थापित करने के लिए गणितीय तकनीक के रूप में यादृच्छिक निर्माण के उपयोग को लोकप्रिय बनाया। इस तकनीक को [[संभाव्य विधि]] के रूप में जाना जाने लगा।<ref name=":1">{{Cite book |last=Alon |first=Noga |url=https://www.worldcat.org/oclc/910535517 |title=संभाव्य विधि|date=2016 |others=Joel H. Spencer |isbn=978-1-119-06195-3 |edition=Fourth |location=Hoboken, New Jersey |oclc=910535517}}</ref> पॉल एर्दोस | एर्दोस ने 1947 में संभाव्यता पद्धति का अपना पहला आवेदन दिया, जब उन्होंने रैमसे ग्राफ के अस्तित्व को स्थापित करने के लिए एक सरल यादृच्छिक निर्माण का उपयोग किया।<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> उन्होंने 1959 में उच्च परिधि और रंगीन संख्या वाले ग्राफ के अस्तित्व को स्थापित करने के लिए प्रसिद्ध रूप से एक अधिक परिष्कृत यादृच्छिक एल्गोरिथ्म का उपयोग किया।<ref>{{Cite journal |last=Erdös |first=P. |date=1959 |title=ग्राफ सिद्धांत और संभावना|url=https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graph-theory-and-probability/154EF813293BC7D0652C4CBCD9D18E84 |journal=Canadian Journal of Mathematics |language=en |volume=11 |pages=34–38 |doi=10.4153/CJM-1959-003-9 |s2cid=122784453 |issn=0008-414X}}</ref><ref name=":1" />
+कंप्यूटर विज्ञान में यादृच्छिक एल्गोरिदम के लोकप्रिय होने से पहले, पॉल एर्डोस ने गणितीय वस्तुओं के अस्तित्व को स्थापित करने के लिए गणितीय तकनीक के रूप में यादृच्छिक निर्माण के उपयोग को लोकप्रिय बनाया था। इस तकनीक को [[संभाव्य विधि]] के रूप में जाना जाने लगा।<ref name=":1">{{Cite book |last=Alon |first=Noga |url=https://www.worldcat.org/oclc/910535517 |title=संभाव्य विधि|date=2016 |others=Joel H. Spencer |isbn=978-1-119-06195-3 |edition=Fourth |location=Hoboken, New Jersey |oclc=910535517}}</ref> पॉल एर्दोस ने 1947 में संभाव्यता पद्धति का अपना पहला आवेदन दिया, जब उन्होंने रैमसे ग्राफ के अस्तित्व को स्थापित करने के लिए सरल यादृच्छिक निर्माण का उपयोग किया था।<ref>P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. '''53''' (1947), 292--294 '''MR'''8,479d; '''Zentralblatt''' 32,192.</ref> उन्होंने 1959 में उच्च परिधि और रंगीन संख्या वाले ग्राफ के अस्तित्व को स्थापित करने के लिए प्रसिद्ध रूप से अधिक परिष्कृत यादृच्छिक एल्गोरिथ्म का उपयोग किया था।<ref>{{Cite journal |last=Erdös |first=P. |date=1959 |title=ग्राफ सिद्धांत और संभावना|url=https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/graph-theory-and-probability/154EF813293BC7D0652C4CBCD9D18E84 |journal=Canadian Journal of Mathematics |language=en |volume=11 |pages=34–38 |doi=10.4153/CJM-1959-003-9 |s2cid=122784453 |issn=0008-414X}}</ref><ref name=":1" />
 == उदाहरण ==
 === क्विकसॉर्ट ===
-क्विकसॉर्ट एक परिचित, आमतौर पर इस्तेमाल किया जाने वाला एल्गोरिदम है जिसमें यादृच्छिकता उपयोगी हो सकती है। इस एल्गोरिथम के कई नियतात्मक संस्करणों के लिए [[बिग ओ नोटेशन]] की आवश्यकता होती है (एन<sup>2</sup>) कुछ अच्छी तरह से परिभाषित इनपुट वर्ग (जैसे कि पहले से ही क्रमबद्ध सरणी) के लिए n संख्याओं को सॉर्ट करने का समय, इनपुट के विशिष्ट वर्ग के साथ जो पिवट चयन के लिए प्रोटोकॉल द्वारा परिभाषित इस व्यवहार को उत्पन्न करता है। हालांकि, अगर एल्गोरिद्म पिवट तत्वों को यादृच्छिक रूप से समान रूप से चुनता है, तो इनपुट की विशेषताओं की परवाह किए बिना O(n log n) समय में समाप्त होने की संभावना काफी अधिक होती है।
+क्विकसॉर्ट एक परिचित, सामान्यतः उपयोग किया जाने वाला एल्गोरिदम है जिसमें यादृच्छिकता उपयोगी हो सकती है। इस एल्गोरिथम के कई नियतात्मक संस्करणों के लिए  [[बिग ओ नोटेशन|''O''(''n''<sup>2</sup>)]] की आवश्यकता होती है कुछ अच्छी तरह से परिभाषित इनपुट वर्ग (जैसे कि पहले से ही क्रमबद्ध सरणी) के लिए ''n'' संख्याओं को सॉर्ट करने का समय, इनपुट के विशिष्ट वर्ग के साथ जो पिवट चयन के लिए प्रोटोकॉल द्वारा परिभाषित इस व्यवहार को उत्पन्न करता है। चूंकि, यदि एल्गोरिद्म पिवट तत्वों को यादृच्छिक रूप से समान रूप से चुनता है, तो इनपुट की विशेषताओं की परवाह किए बिना ''O''(''n'' log ''n'') समय में समाप्त होने की संभावना काफी अधिक होती है।
 === ज्यामिति में [[यादृच्छिक वृद्धिशील निर्माण]] ===
-[[कम्प्यूटेशनल ज्यामिति]] में, एक उत्तल हल या डेलाउने त्रिभुज जैसी संरचना बनाने के लिए एक मानक तकनीक इनपुट बिंदुओं को यादृच्छिक रूप से क्रमबद्ध करना है और फिर उन्हें मौजूदा संरचना में एक-एक करके सम्मिलित करना है। यादृच्छिककरण यह सुनिश्चित करता है कि सम्मिलन के कारण संरचना में परिवर्तनों की अपेक्षित संख्या कम है, और इसलिए एल्गोरिथम के अपेक्षित चलने का समय ऊपर से बाध्य किया जा सकता है। इस तकनीक को यादृच्छिक वृद्धिशील निर्माण के रूप में जाना जाता है।<ref>Seidel R. [http://www.cs.berkeley.edu/~jrs/meshpapers/Seidel.ps.gz Backwards Analysis of Randomized Geometric Algorithms].</ref>
+[[कम्प्यूटेशनल ज्यामिति]] में, अवमुख हल या डेलाउने त्रिभुज जैसी संरचना बनाने के लिए मानक तकनीक इनपुट बिंदुओं को यादृच्छिक रूप से क्रमबद्ध करना है और फिर उन्हें मौजूदा संरचना में एक-एक करके सम्मिलित करना है। यादृच्छिककरण यह सुनिश्चित करता है कि सम्मिलन के कारण संरचना में परिवर्तनों की अपेक्षित संख्या कम है, और इसलिए एल्गोरिथम के अपेक्षित चलने का समय ऊपर से बाध्य किया जा सकता है। इस तकनीक को यादृच्छिक वृद्धिशील निर्माण के रूप में जाना जाता है।<ref>Seidel R. [http://www.cs.berkeley.edu/~jrs/meshpapers/Seidel.ps.gz Backwards Analysis of Randomized Geometric Algorithms].</ref>
+===न्यूनतम कट===
+{{Main|कार्गर का एल्गोरिदम}}
+इनपुट: [[ग्राफ सिद्धांत]] ''G''(''V'',''E'')
-===न्यूनतम कट===
+आउटपुट: [[ कट (ग्राफ सिद्धांत) |कट (ग्राफ सिद्धांत)]] ''L'' और ''R'' में कोने को विभाजित करता है, जिसमें ''L'' और ''R'' के बीच किनारों की न्यूनतम संख्या होती है।
-{{Main|Karger's algorithm}}
-इनपुट: एक [[ग्राफ सिद्धांत]] ''जी''(''वी'',''ई'')
+याद रखें कि एक (बहु-) ग्राफ़ में दो नोड्स, ''u'' और ''v'' के किनारे का संकुचन, किनारों के साथ नया नोड ''u''' देता है, जो ''u'' या ''v'' पर किनारों की घटना का संघ है, किसी भी किनारे को छोड़कर ''u'' और ''v'' को जोड़ता है। चित्र 1 शीर्ष ''A'' और ''B'' के संकुचन का उदाहरण देता है।
-आउटपुट: एक [[ कट (ग्राफ सिद्धांत) ]] ''L'' और ''R'' में कोने को विभाजित करता है, जिसमें ''L'' और ''R'' के बीच किनारों की न्यूनतम संख्या होती है।
+संकुचन के बाद, परिणामी ग्राफ़ में समानांतर किनार हो सकते हैं, लेकिन इसमें कोई सेल्फ लूप नहीं होता है।
-याद रखें कि एक (बहु-) ग्राफ़ में दो नोड्स, ''यू'' और ''वी'' के किनारे का संकुचन, किनारों के साथ एक नया नोड ''यू'' देता है, जो दोनों किनारों पर घटना के किनारों का मिलन है। ''यू'' और ''वी'' को जोड़ने वाले किसी भी किनारे को छोड़कर ''यू'' या ''वी''। चित्र 1 वर्टेक्स ''ए'' और ''बी'' के संकुचन का एक उदाहरण देता है।
+चित्र 2: 10-शीर्ष ग्राफ़ पर कार्गर के एल्गोरिथम का सफल संचालन। न्यूनतम कट का आकार 3 है और इसे शीर्ष रंगों द्वारा दर्शाया गया है।
-संकुचन के बाद, परिणामी ग्राफ़ में समानांतर किनार हो सकते हैं, लेकिन इसमें कोई सेल्फ लूप नहीं होता है।
-फ़ाइल: कार्गर का एकल रन 's Mincut algorithm.svg|thumb|340px|चित्र 2: 10-शीर्ष ग्राफ़ पर कार्गर के एल्गोरिथम का सफल संचालन। न्यूनतम कट का आकार 3 है और इसे शीर्ष रंगों द्वारा दर्शाया गया है।
 [[File:Contraction vertices.jpg|300px|thumb|center|चित्र 1: शीर्ष A और B का संकुचन]]कार्गर का<ref>A. A. Tsay, W. S. Lovejoy, David R. Karger, ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.215.794&rep=rep1&type=pdf Random Sampling in Cut, Flow, and Network Design Problems]'', Mathematics of Operations Research, 24(2):383–413, 1999.</ref> बुनियादी एल्गोरिथ्म:
-  शुरू
+     '''begin'''
-     मैं = 1
-      दोहराना
+  i = 1
-          दोहराना
+      '''repeat'''
-              जी में एक यादृच्छिक किनारा (यू, वी) ∈ ई लें
+          '''repeat'''
-              u और v को संकुचन u' से बदलें
+              Take a random edge (u,v) ∈ E in G
-          जब तक केवल 2 नोड शेष रहें
+              replace u and v with the contraction u'
-          संबंधित कट परिणाम सी प्राप्त करें<sub>i</sub>
+          '''until''' only 2 nodes remain
-मैं = मैं + 1
+          obtain the corresponding cut result C<sub>i</sub>
-      जब तक मैं = एम
+         i = i + 1
-      सी के बीच न्यूनतम कटौती का उत्पादन करें<sub>1</sub>, सी<sub>2</sub>, ..., सी<sub>m</sub>.
+      '''until''' i = m
-  अंत
+      output the minimum cut among C<sub>1</sub>, C<sub>2</sub>, ..., C<sub>m</sub>.
-बाहरी लूप के प्रत्येक निष्पादन में, एल्गोरिथ्म आंतरिक लूप को तब तक दोहराता है जब तक कि केवल 2 नोड शेष न रह जाएं, संबंधित कट प्राप्त हो जाता है। एक निष्पादन का रन टाइम है <math>O(n)</math>, और n शीर्षों की संख्या को दर्शाता है।
+  '''end'''
-बाहरी लूप के m बार निष्पादन के बाद, हम सभी परिणामों के बीच न्यूनतम कट का उत्पादन करते हैं। चित्र 2 एक देता है
+बाहरी लूप के प्रत्येक निष्पादन में, एल्गोरिथ्म आंतरिक लूप को तब तक दोहराता है जब तक कि केवल 2 नोड शेष न रह जाएं, संबंधित कट प्राप्त हो जाता है। एक निष्पादन का रन टाइम है <math>O(n)</math>, और n शीर्षों की संख्या को दर्शाता है। बाहरी लूप के ''m'' बार निष्पादन के बाद, हम सभी परिणामों के बीच न्यूनतम कट का उत्पादन करते हैं। चित्र 2 एल्गोरिथ्म के एक निष्पादन का उदाहरण देता है। निष्पादन के बाद, हमें आकार 3 में कट मिलती है।
-एल्गोरिथ्म के एक निष्पादन का उदाहरण। निष्पादन के बाद, हमें आकार 3 में कटौती मिलती है।
 {{math theorem|name=Lemma 1|1=Let ''k'' be the min cut size, and let {{math|1=''C'' = {{mset|''e''<sub>1</sub>, ''e''<sub>2</sub>, ..., ''e''<sub>''k''</sub>}}}} be the min cut. If, during iteration ''i'', no edge {{math|''e'' ∈  ''C''}} is selected for contraction, then {{math|1=''C''<sub>''i''</sub> = ''C''}}.}}
@@ Line 133: / Line 127: @@
 \prod_{i=1}^m \Pr(C_i\neq C)=\prod_{i=1}^m(1-\Pr(C_i=C)).
 </math>
-लेम्मा 1 द्वारा, संभावना है कि {{math|1=''C''<sub>''i''</sub> = ''C''}} संभावना है कि पुनरावृत्ति i के दौरान C का कोई किनारा नहीं चुना गया है। आंतरिक पाश पर विचार करें और जाने दें {{math|''G''<sub>''j''</sub>}} j किनारे के संकुचन के बाद ग्राफ़ को निरूपित करें, जहाँ {{math|1=''j'' ∈ {{mset|0, 1, …, ''n'' − 3}}}}. {{math|''G''<sub>''j''</sub>}} है {{math|1=''n'' − ''j''}} शिखर। हम [[सशर्त संभाव्यता]] के श्रृंखला नियम का उपयोग करते हैं।
+लेम्मा 1 द्वारा, संभावना है कि {{math|1=''C''<sub>''i''</sub> = ''C''}} संभावना है कि पुनरावृत्ति ''i'' के दौरान C का कोई किनारा नहीं चुना गया है। आंतरिक पाश पर विचार करें और मान लीजिये {{math|''G''<sub>''j''</sub>}}, j किनारे के संकुचन के बाद ग्राफ़ को निरूपित करता है, जहाँ {{math|1=''j'' ∈ {{mset|0, 1, …, ''n'' − 3}}}}, {{math|''G''<sub>''j''</sub>}} में {{math|1=''n'' − ''j''}} शीर्ष हैं। हम [[सशर्त संभाव्यता]] के श्रृंखला नियम का उपयोग करते हैं। संभावना है कि पुनरावृत्ति j पर चुना गया किनारा C में नहीं है, यह देखते हुए कि C का कोई किनारा पहले नहीं चुना गया है <math>1-\frac{k}{|E(G_j)|}</math> ध्यान दें कि {{math|''G''<sub>''j''</sub>}} अभी भी आकार ''k'' का न्यूनतम कट है, इसलिए लेम्मा 2 के अनुसार, यह अभी भी कम से कम  <math>\frac{(n-j)k}{2}</math> किनारा है।
-संभावना है कि पुनरावृत्ति j पर चुना गया किनारा C में नहीं है, यह देखते हुए कि C का कोई किनारा पहले नहीं चुना गया है <math>1-\frac{k}{|E(G_j)|}</math>. ध्यान दें कि {{math|''G''<sub>''j''</sub>}} अभी भी आकार k का न्यूनतम कट है, इसलिए लेम्मा 2 के अनुसार, यह अभी भी कम से कम है <math>\frac{(n-j)k}{2}</math> किनारों।
 इस प्रकार, <math>1-\frac{k}{|E(G_j)|}\geq 1-\frac{2}{n-j}=\frac{n-j-2}{n-j}</math>.
-तो चेन नियम से, न्यूनतम कट सी खोजने की संभावना है
+तो चेन नियम से, न्यूनतम कट ''C'' निष्कर्ष की संभावना है
 <math display="block">
   \Pr[C_i=C] \geq \left(\frac{n-2}{n}\right)\left(\frac{n-3}{n-1}\right)\left(\frac{n-4}{n-2}\right)\ldots\left(\frac{3}{5}\right)\left(\frac{2}{4}\right)\left(\frac{1}{3}\right).
 </math>
-निरस्तीकरण देता है <math>\Pr[C_i=C] \geq \frac{2}{n(n-1)}</math>. इस प्रकार एल्गोरिथ्म के सफल होने की संभावना कम से कम है <math>1- \left(1-\frac{2}{n(n-1)}\right)^m</math>. के लिए <math>m = \frac{n(n-1)}{2}\ln n</math>, यह इसके बराबर है <math>1-\frac{1}{n}</math>. एल्गोरिथ्म संभाव्यता के साथ न्यूनतम कटौती पाता है <math>1 - \frac{1}{n}</math>, समय के भीतर <math>O(mn) = O(n^3 \log n)</math>.
+निरस्तीकरण देता है <math>\Pr[C_i=C] \geq \frac{2}{n(n-1)}</math>, इस प्रकार एल्गोरिथ्म के सफल होने की संभावना कम से कम है<math>1- \left(1-\frac{2}{n(n-1)}\right)^m</math>है  <math>m = \frac{n(n-1)}{2}\ln n</math>, के लिए यह <math>1-\frac{1}{n}</math> के बराबर है एल्गोरिथ्म संभाव्यता के साथ न्यूनतम कट <math>1 - \frac{1}{n}</math>, समय के भीतर <math>O(mn) = O(n^3 \log n)</math> पाता है।
 == डेरेंडोमाइजेशन ==
-यादृच्छिकता को अंतरिक्ष और समय जैसे संसाधन के रूप में देखा जा सकता है। Derandomization तब यादृच्छिकता को हटाने की प्रक्रिया है (या जितना संभव हो उतना कम उपयोग करना)। यह वर्तमान में ज्ञात नहीं है कि क्या सभी एल्गोरिदम को उनके चलने के समय में उल्लेखनीय वृद्धि किए बिना डीरैंडमाइज किया जा सकता है। उदाहरण के लिए, एल्गोरिदम के विश्लेषण में, यह अज्ञात है कि क्या पी (जटिलता) = परिबद्ध-त्रुटि संभाव्य बहुपद, यानी, हम नहीं जानते कि क्या हम एक मनमाना यादृच्छिक एल्गोरिदम ले सकते हैं जो एक छोटी त्रुटि संभावना के साथ बहुपद समय में चलता है और इसे डीरैंडमाइज करता है। यादृच्छिकता का उपयोग किए बिना बहुपद समय में चलाने के लिए।
+यादृच्छिकता को समष्टि और समय जैसे संसाधन के रूप में देखा जा सकता है। डेरेंडोमाइजेशन यादृच्छिकता को हटाने की प्रक्रिया है (या जितना संभव हो उतना कम उपयोग करना)। यह वर्तमान में ज्ञात नहीं है कि क्या सभी एल्गोरिदम को उनके चलने के समय में उल्लेखनीय वृद्धि किए बिना डीरैंडमाइज किया जाता है। उदाहरण के लिए, अभिकलनात्मक जटिलता में, यह अज्ञात है कि P = BPP अर्थात, हम नहीं जानते कि क्या यादृच्छिक एल्गोरिदम ले सकते हैं जो छोटी त्रुटि संभावना के साथ बहुपद काल में चलता है और इसे डीरैंडमाइज करता है। यादृच्छिकता का उपयोग किए बिना बहुपद काल में चलाने के लिए इसे यादृच्छिक बनाता है।
 ऐसे विशिष्ट तरीके हैं जिन्हें विशेष यादृच्छिक एल्गोरिदम को यादृच्छिक बनाने के लिए नियोजित किया जा सकता है:
 * [[सशर्त संभावनाओं की विधि]], और इसका सामान्यीकरण, [[निराशावादी अनुमानक]]
 * [[विसंगति सिद्धांत]] (जिसका उपयोग ज्यामितीय एल्गोरिदम को अलग करने के लिए किया जाता है)
-* एल्गोरिथ्म द्वारा उपयोग किए जाने वाले यादृच्छिक चर में सीमित स्वतंत्रता का शोषण, जैसे कि सार्वभौमिक हैशिंग में उपयोग की जाने वाली [[जोड़ीदार स्वतंत्रता]]
+* एल्गोरिथ्म द्वारा उपयोग किए जाने वाले यादृच्छिक चर में सीमित स्वतंत्रता का समुपयोजन, जैसे कि सार्वभौमिक हैशिंग में उपयोग की जाने वाली  [[जोड़ीदार स्वतंत्रता|युग्‍मानूसार स्वतंत्रता]]
-* प्रारंभिक यादृच्छिकता की सीमित मात्रा को बढ़ाने के लिए [[विस्तारक ग्राफ]] (या सामान्य रूप से [[फैलाने]] वाले) का उपयोग (यह अंतिम दृष्टिकोण एक यादृच्छिक स्रोत से छद्म यादृच्छिक बिट्स उत्पन्न करने के रूप में भी जाना जाता है, और छद्म यादृच्छिकता के संबंधित विषय की ओर जाता है)
+* प्रारंभिक यादृच्छिकता की सीमित मात्रा को बढ़ाने के लिए [[विस्तारक ग्राफ]] (या सामान्य रूप से [[फैलाने]] वाले) का उपयोग (यह अंतिम दृष्टिकोण यादृच्छिक स्रोत से छद्म यादृच्छिक बिट्स उत्पन्न करने के रूप में भी जाना जाता है, और छद्म यादृच्छिकता के संबंधित विषय की ओर जाता है)
-* एल्गोरिथम के कार्यों के लिए यादृच्छिकता के स्रोत के रूप में [[हैश फंकशन]] का उपयोग करने के लिए यादृच्छिक एल्गोरिथ्म को बदलना, और फिर हैश फ़ंक्शन के सभी संभावित मापदंडों (बीजों) को [[ क्रूर-बल खोज ]] | ब्रूट-फोर्सिंग द्वारा एल्गोरिथ्म को अलग करना। इस तकनीक का प्रयोग आम तौर पर नमूना स्थान को व्यापक रूप से खोजने और एल्गोरिदम को नियतात्मक बनाने के लिए किया जाता है (उदाहरण के लिए यादृच्छिक ग्राफ एल्गोरिदम)
+* एल्गोरिथम के कार्यों के लिए यादृच्छिकता के स्रोत के रूप में [[हैश फंकशन]] का उपयोग करने के लिए यादृच्छिक एल्गोरिथ्म को बदलना, और फिर हैश फ़ंक्शन के सभी संभावित मापदंडों (बीजों) को [[ क्रूर-बल खोज | मनमानी बल]] द्वारा एल्गोरिथ्म को अलग करना। इस तकनीक का प्रयोग सामान्यतः नमूना स्थान को व्यापक रूप से निष्कर्ष और एल्गोरिदम को नियतात्मक बनाने के लिए किया जाता है (उदाहरण के लिए यादृच्छिक ग्राफ एल्गोरिदम)
 == जहां यादृच्छिकता मदद करती है ==
-जब संगणना का मॉडल [[ट्यूरिंग मशीन]]ों तक ही सीमित है, तो यह वर्तमान में एक खुला प्रश्न है कि क्या यादृच्छिक विकल्प बनाने की क्षमता बहुपद समय में कुछ समस्याओं को हल करने की अनुमति देती है जिसे इस क्षमता के बिना बहुपद समय में हल नहीं किया जा सकता है; यह सवाल है कि क्या पी = बीपीपी। हालाँकि, अन्य संदर्भों में, समस्याओं के विशिष्ट उदाहरण हैं जहाँ यादृच्छिककरण से सख्त सुधार होते हैं।
+जब संगणना का मॉडल [[ट्यूरिंग मशीन]] तक ही सीमित है, तो यह वर्तमान में खुला प्रश्न है कि क्या यादृच्छिक विकल्प बनाने की क्षमता बहुपद काल में कुछ समस्याओं को हल करने की अनुमति देती है जिसे इस क्षमता के बिना बहुपद काल में हल नहीं किया जा सकता है; यह सवाल है कि P = BPP। हालाँकि, अन्य संदर्भों में, समस्याओं के विशिष्ट उदाहरण हैं जहाँ यादृच्छिककरण से सख्त सुधार होते हैं।
-* प्रारंभिक प्रेरक उदाहरण के आधार पर: 2 की एक घातीय रूप से लंबी स्ट्रिंग दी गई है<sup>k</sup> वर्ण, आधा a और आधा b, एक [[रैंडम-एक्सेस मशीन]] के लिए 2 की आवश्यकता होती है<sup>k−1</sup> a की अनुक्रमणिका खोजने के लिए सबसे खराब स्थिति में खोजता है; अगर इसे यादृच्छिक विकल्प बनाने की अनुमति है, तो यह लुकअप की अपेक्षित बहुपद संख्या में इस समस्या को हल कर सकता है। <!-- Does the randomized lookup still have the same worst-case performance? Yes. -->
+* प्रारंभिक प्रेरक उदाहरण के आधार पर: 2<sup>''k''</sup> की घातीय रूप से लंबी स्ट्रिंग दी गई है वर्ण, आधा a और आधा b, [[रैंडम-एक्सेस मशीन]] के लिए  2<sup>''k''−1</sup> की आवश्यकता होती है a की अनुक्रमणिका निष्कर्ष के लिए सबसे खराब स्थिति में खोजता है; यदि इसे यादृच्छिक विकल्प बनाने की अनुमति है, तो यह लुकअप की अपेक्षित बहुपद संख्या में इस समस्या को हल कर सकता है।
-* [[ अंतः स्थापित प्रणालियाँ ]] या [[साइबर-भौतिक प्रणाली]] में एक संख्यात्मक गणना करने का प्राकृतिक तरीका एक परिणाम प्रदान करना है जो उच्च संभावना (या संभवतः लगभग सही गणना (PACC)) के साथ सही परिणाम का अनुमान लगाता है। अनुमानित और सही संगणना के बीच विसंगति हानि के मूल्यांकन से जुड़ी कठिन समस्या को यादृच्छिककरण का सहारा लेकर प्रभावी ढंग से संबोधित किया जा सकता है<ref>{{citation|title=Intelligence for Embedded Systems|first1=Cesare|last1=Alippi|publisher=Springer|year=2014|isbn=978-3-319-05278-6}}.</ref>
+* [[ अंतः स्थापित प्रणालियाँ ]] या [[साइबर-भौतिक प्रणाली]] में संख्यात्मक गणना करने का प्राकृतिक तरीका परिणाम प्रदान करना है जो उच्च संभावना (या संभवतः लगभग सही गणना (पीएसीसी)) के साथ सही परिणाम का अनुमान लगाता है। अनुमानित और सही संगणना के बीच विसंगति हानि के मूल्यांकन से जुड़ी कठिन समस्या को यादृच्छिककरण का सहारा लेकर प्रभावी ढंग से संबोधित किया जा सकता है<ref>{{citation|title=Intelligence for Embedded Systems|first1=Cesare|last1=Alippi|publisher=Springer|year=2014|isbn=978-3-319-05278-6}}.</ref>
-* [[संचार जटिलता]] में, दो तारों की समानता का उपयोग करके कुछ विश्वसनीयता के लिए सत्यापित किया जा सकता है <math>\log n</math> एक यादृच्छिक प्रोटोकॉल के साथ संचार के बिट्स। किसी भी नियतात्मक प्रोटोकॉल की आवश्यकता होती है <math>\Theta(n)</math> बिट्स अगर एक मजबूत प्रतिद्वंद्वी के खिलाफ बचाव करते हैं।<ref>{{citation|title=Communication Complexity|first1=Eyal|last1=Kushilevitz|first2=Noam|last2=Nisan|publisher=Cambridge University Press|year=2006|isbn=9780521029834}}. For the deterministic lower bound see p.&nbsp;11; for the logarithmic randomized upper bound see pp.&nbsp;31–32.</ref>
+* [[संचार जटिलता]] में, <math>\log n</math> यादृच्छिक प्रोटोकॉल के साथ संचार के बिट्स का उपयोग करके दो स्ट्रिंग की समानता कुछ विश्वसनीयता के लिए सत्यापित किया जा सकता है। किसी भी नियतात्मक प्रोटोकॉल की आवश्यकता <math>\Theta(n)</math> बिट्स होती है यदि दृढ़ प्रतिद्वंद्वी के खिलाफ बचाव करते हैं।<ref>{{citation|title=Communication Complexity|first1=Eyal|last1=Kushilevitz|first2=Noam|last2=Nisan|publisher=Cambridge University Press|year=2006|isbn=9780521029834}}. For the deterministic lower bound see p.&nbsp;11; for the logarithmic randomized upper bound see pp.&nbsp;31–32.</ref>
-* बहुपद समय में मनमाने ढंग से परिशुद्धता के लिए एक उत्तल शरीर की मात्रा का अनुमान एक यादृच्छिक एल्गोरिदम द्वारा लगाया जा सकता है।<ref>{{citation|last1=Dyer|first1=M.|last2=Frieze|first2=A.|last3=Kannan|first3=R.|title=A random polynomial-time algorithm for approximating the volume of convex bodies|journal=[[Journal of the ACM]]|volume=38|issue=1|year=1991|pages=1–17|doi=10.1145/102782.102783|s2cid=13268711|url=http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf}}</ref> इमरे बैरनी | बैरनी और ज़ोलटन फ़्यूरेडी | फ़्यूरेडी ने दिखाया कि कोई नियतात्मक एल्गोरिथम ऐसा नहीं कर सकता है।<ref>{{citation|last1=Füredi|first1=Z.|author1-link=Zoltán Füredi|last2=Bárány|first2=I.|year=1986|contribution=Computing the volume is difficult|title=Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986)|publisher=ACM|location=New York, NY|pages=442–447|doi=10.1145/12130.12176|citeseerx=10.1.1.726.9448|isbn=0-89791-193-8 |s2cid=17867291|url=https://ecommons.cornell.edu/bitstream/1813/8572/1/TR000688.pdf}}</ref> यह बिना शर्त के सच है, यानी किसी भी जटिलता-सैद्धांतिक मान्यताओं पर भरोसा किए बिना, उत्तल शरीर को केवल एक ब्लैक बॉक्स के रूप में माना जा सकता है।
+* बहुपद काल में अक्रमतः परिशुद्धता के लिए अवमुखपिंड की मात्रा का अनुमान यादृच्छिक एल्गोरिदम द्वारा लगाया जा सकता है।<ref>{{citation|last1=Dyer|first1=M.|last2=Frieze|first2=A.|last3=Kannan|first3=R.|title=A random polynomial-time algorithm for approximating the volume of convex bodies|journal=[[Journal of the ACM]]|volume=38|issue=1|year=1991|pages=1–17|doi=10.1145/102782.102783|s2cid=13268711|url=http://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf}}</ref> इमरे बैरनी और ज़ोलटन फ़्यूरेडी ने दिखाया कि कोई नियतात्मक एल्गोरिथम ऐसा नहीं कर सकता है।<ref>{{citation|last1=Füredi|first1=Z.|author1-link=Zoltán Füredi|last2=Bárány|first2=I.|year=1986|contribution=Computing the volume is difficult|title=Proc. 18th ACM Symposium on Theory of Computing (Berkeley, California, May 28–30, 1986)|publisher=ACM|location=New York, NY|pages=442–447|doi=10.1145/12130.12176|citeseerx=10.1.1.726.9448|isbn=0-89791-193-8 |s2cid=17867291|url=https://ecommons.cornell.edu/bitstream/1813/8572/1/TR000688.pdf}}</ref> यह बिना शर्त के सच है, अर्थात किसी भी जटिलता-सैद्धांतिक मान्यताओं पर भरोसा किए बिना, अवमुखपिंड को केवल ब्लैक बॉक्स के रूप में माना जा सकता है।
-* एक जगह का अधिक जटिलता-सैद्धांतिक उदाहरण जहां यादृच्छिकता मदद करने के लिए प्रकट होती है वह वर्ग आईपी (जटिलता) है। IP में वे सभी भाषाएँ शामिल हैं जिन्हें (उच्च संभावना के साथ) एक सर्व-शक्तिशाली प्रोवर और एक सत्यापनकर्ता के बीच बहुपद रूप से लंबी बातचीत द्वारा स्वीकार किया जा सकता है जो BPP एल्गोरिथम को लागू करता है। आईपी \u003d [[पीएसपीएसीई]]।<ref>{{citation|last=Shamir|first=A.|author-link=Adi Shamir|title=IP = PSPACE|journal=Journal of the ACM|volume=39|issue=4|year=1992|pages=869–877|doi=10.1145/146585.146609|s2cid=315182}}</ref> हालाँकि, यदि यह आवश्यक है कि सत्यापनकर्ता नियतात्मक हो, तो IP = NP (जटिलता)।
+* एक जगह का अधिक जटिलता-सैद्धांतिक उदाहरण जहां यादृच्छिकता मदद करने के लिए प्रकट होती है वह वर्ग IP (जटिलता) है। IP में वे सभी भाषाएँ सम्मिलित हैं जिन्हें (उच्च संभावना के साथ) सर्व-शक्तिशाली प्रोवर और सत्यापनकर्ता के बीच बहुपद रूप से लंबी पारस्परिक प्रभाव द्वारा स्वीकार किया जा सकता है जो बीपीपी एल्गोरिथम को लागू करता है। [[पीएसपीएसीई|IP = PSPACE]]।<ref>{{citation|last=Shamir|first=A.|author-link=Adi Shamir|title=IP = PSPACE|journal=Journal of the ACM|volume=39|issue=4|year=1992|pages=869–877|doi=10.1145/146585.146609|s2cid=315182}}</ref> हालाँकि, यदि यह आवश्यक है कि सत्यापनकर्ता नियतात्मक हो, तो IP = NP (जटिलता)।
-* एक [[रासायनिक प्रतिक्रिया नेटवर्क]] में (ए + बी → 2 सी + डी जैसी प्रतिक्रियाओं का एक सीमित सेट अणुओं की एक सीमित संख्या पर काम कर रहा है), प्रारंभिक अवस्था से किसी दिए गए लक्ष्य राज्य तक कभी भी पहुंचने की क्षमता निर्णायक होती है, जबकि संभाव्यता का अनुमान भी लगाया जाता है किसी दिए गए लक्ष्य राज्य तक पहुंचने के लिए (मानक एकाग्रता-आधारित संभावना जिसके लिए प्रतिक्रिया आगे होगी) का उपयोग करना अनिर्णीत है। अधिक विशेष रूप से, एक सीमित ट्यूरिंग मशीन <!-- the Turing machine has infinite tape --> सभी समय के लिए सही ढंग से चलने की मनमाने ढंग से उच्च संभावना के साथ सिम्युलेटेड किया जा सकता है, केवल तभी जब एक यादृच्छिक रासायनिक प्रतिक्रिया नेटवर्क का उपयोग किया जाता है। एक सरल गैर-नियतात्मक रासायनिक प्रतिक्रिया नेटवर्क (आगे कोई भी संभावित प्रतिक्रिया हो सकती है) के साथ, कम्प्यूटेशनल शक्ति [[आदिम पुनरावर्ती]] तक सीमित है।<ref>{{citation
+* [[रासायनिक प्रतिक्रिया नेटवर्क]] में (A+B → 2C + D जैसी प्रतिक्रियाओं का सीमित सेट अणुओं की सीमित संख्या पर काम कर रहा है), प्रारंभिक अवस्था से किसी दिए गए लक्ष्य अवस्था तक कभी भी पहुंचने की क्षमता निर्णायक होती है, जबकि संभाव्यता का अनुमान भी लगाया जाता है किसी दिए गए लक्ष्य अवस्था तक पहुंचने के लिए (मानक एकाग्रता-आधारित संभावना जिसके लिए प्रतिक्रिया आगे होगी) का उपयोग करना अनिर्णीत है। अधिक विशेष रूप से, सीमित ट्यूरिंग मशीन सभी समय के लिए सही ढंग से चलने की अक्रमतः उच्च संभावना के साथ अनुरूप किया जा सकता है, केवल तभी जब यादृच्छिक रासायनिक प्रतिक्रिया नेटवर्क का उपयोग किया जाता है। एक सरल गैर-नियतात्मक रासायनिक प्रतिक्रिया नेटवर्क (आगे कोई भी संभावित प्रतिक्रिया हो सकती है) के साथ, कम्प्यूटेशनल पावर [[आदिम पुनरावर्ती]] तक सीमित है।<ref>{{citation
   | last1 = Cook | first1 = Matthew | author1-link = Matthew Cook
   | last2 = Soloveichik | first2 = David
@@ Line 178: / Line 171: @@
   | title = Algorithmic Bioprocesses
   | year = 2009| url = https://authors.library.caltech.edu/26121/1/etr090.pdf }}.</ref>
 == यह भी देखें ==
 * [[एल्गोरिदम का संभाव्य विश्लेषण]]
@@ Line 211: / Line 202: @@
 * [https://www.osti.gov/biblio/1807223 "Randomized Algorithms for Scientific Computing" (RASC), OSTI.GOV (July 10th, 2021).]
-{{DEFAULTSORT:Randomized Algorithm}}[[Category: यादृच्छिक एल्गोरिदम | यादृच्छिक एल्गोरिदम ]] [[Category: एल्गोरिदम का विश्लेषण]]
+{{DEFAULTSORT:Randomized Algorithm}}
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Randomized Algorithm]]
-[[Category:Created On 31/05/2023]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Created On 31/05/2023|Randomized Algorithm]]
+[[Category:Lua-based templates|Randomized Algorithm]]
+[[Category:Machine Translated Page|Randomized Algorithm]]
+[[Category:Pages with script errors|Randomized Algorithm]]
+[[Category:Short description with empty Wikidata description|Randomized Algorithm]]
+[[Category:Templates Vigyan Ready|Randomized Algorithm]]
+[[Category:Templates that add a tracking category|Randomized Algorithm]]
+[[Category:Templates that generate short descriptions|Randomized Algorithm]]
+[[Category:Templates using TemplateData|Randomized Algorithm]]
+[[Category:एल्गोरिदम का विश्लेषण|Randomized Algorithm]]
+[[Category:यादृच्छिक एल्गोरिदम| यादृच्छिक एल्गोरिदम ]]

Anonymous

Search

यादृच्छिक एल्गोरिथ्म: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 14:50, 24 August 2023

Contents

प्रेरणा

अभिकलनात्मक जटिलता

प्रारंभिक इतिहास

सॉर्टिंग

संख्या सिद्धांत

डेटा संरचनाएं

कॉम्बिनेटरिक्स में अंतर्निहित उपयोग

उदाहरण

क्विकसॉर्ट

ज्यामिति में यादृच्छिक वृद्धिशील निर्माण

न्यूनतम कट

एल्गोरिदम का विश्लेषण

डेरेंडोमाइजेशन

जहां यादृच्छिकता मदद करती है

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

यादृच्छिक एल्गोरिथ्म: Difference between revisions

Latest revision as of 14:50, 24 August 2023

प्रेरणा

अभिकलनात्मक जटिलता

प्रारंभिक इतिहास

सॉर्टिंग

संख्या सिद्धांत

डेटा संरचनाएं

कॉम्बिनेटरिक्स में अंतर्निहित उपयोग

उदाहरण

क्विकसॉर्ट

ज्यामिति में यादृच्छिक वृद्धिशील निर्माण

न्यूनतम कट

एल्गोरिदम का विश्लेषण

डेरेंडोमाइजेशन

जहां यादृच्छिकता मदद करती है

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories