नियतात्मक एल्गोरिथ्म: Difference between revisions

From Vigyanwiki
No edit summary
Line 1: Line 1:
{{Short description|Type of algorithm in computer science}}
{{Short description|Type of algorithm in computer science}}
[[ कंप्यूटर विज्ञान ]] में, नियतात्मक [[ कलन विधि ]] एक एल्गोरिथम है, जो एक विशेष इनपुट दिए जाने पर, हमेशा एक ही आउटपुट का उत्पादन करेगा, जिसमें अंतर्निहित मशीन हमेशा राज्यों के समान अनुक्रम से गुजरती है। नियतात्मक एल्गोरिदम अब तक सबसे अधिक अध्ययन और परिचित प्रकार के एल्गोरिदम हैं, साथ ही सबसे व्यावहारिक में से एक हैं, क्योंकि उन्हें वास्तविक मशीनों पर कुशलता से चलाया जा सकता है।
[[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, नियतात्मक एल्गोरिथम ([[ कलन विधि |कलन विधि]]) एक एल्गोरिथम है, जो एक विशेष इनपुट दिए जाने पर, हमेशा एक ही आउटपुट का उत्पादन करेगा, जिसमें अंतर्निहित मशीन हमेशा राज्यों के समान अनुक्रम से गुजरती है। नियतात्मक एल्गोरिदम अब तक सबसे अधिक अध्ययन और परिचित प्रकार के एल्गोरिदम हैं, साथ ही साथ सबसे व्यावहारिक में से एक हैं क्योंकि उन्हें वास्तविक मशीनों पर कुशलता से चलाया जा सकता है।


औपचारिक रूप से, नियतात्मक एल्गोरिथ्म एक फ़ंक्शन (गणित) की गणना करता है; एक फ़ंक्शन का अपने [[ समारोह डोमेन ]] में किसी भी इनपुट के लिए एक अद्वितीय मान होता है, और एल्गोरिथम एक प्रक्रिया है जो आउटपुट के रूप में इस विशेष मान का उत्पादन करती है।
औपचारिक रूप से, नियतात्मक एल्गोरिथम एक गणितीय फलन की गणना करता है; एक फ़ंक्शन का अपने डोमेन में किसी भी इनपुट के लिए एक अद्वितीय मान होता है, और एल्गोरिथम एक ऐसी प्रक्रिया है जो इस विशेष मान को आउटपुट के रूप में उत्पन्न करती है।


== औपचारिक परिभाषा ==
== औपचारिक परिभाषा ==


नियतात्मक एल्गोरिदम को एक [[ राज्य मशीन ]] के संदर्भ में परिभाषित किया जा सकता है: एक राज्य वर्णन करता है कि एक मशीन किसी विशेष समय पर क्या कर रही है। राज्य मशीनें एक राज्य से दूसरे राज्य में असतत तरीके से गुजरती हैं। जैसे ही हम इनपुट दर्ज करते हैं, मशीन अपनी प्रारंभिक अवस्था या प्रारंभ अवस्था में होती है। यदि मशीन नियतात्मक है, तो इसका मतलब है कि इस बिंदु से, इसकी वर्तमान स्थिति निर्धारित करती है कि इसकी अगली स्थिति क्या होगी; राज्यों के सेट के माध्यम से इसका पाठ्यक्रम पूर्व निर्धारित है। ध्यान दें कि एक मशीन नियतात्मक हो सकती है और फिर भी कभी रुकती या समाप्त नहीं होती है, और इसलिए परिणाम देने में विफल रहती है।
नियतात्मक एल्गोरिदम को स्टेट मशीन के संदर्भ में परिभाषित किया जा सकता है: एक राज्य वर्णन करता है कि एक समय में एक विशेष समय पर एक मशीन क्या कर रही है। राज्य मशीनें एक राज्य से दूसरे राज्य में असतत तरीके से गुजरती हैं। जैसे ही हम इनपुट दर्ज करते हैं, मशीन अपनी प्रारंभिक अवस्था या प्रारंभ अवस्था में होती है। यदि मशीन नियतात्मक है, तो इसका मतलब है कि इस बिंदु से, इसकी वर्तमान स्थिति निर्धारित करती है कि इसकी अगली स्थिति क्या होगी; राज्यों के सेट के माध्यम से इसका पाठ्यक्रम पूर्व निर्धारित है। ध्यान दें कि एक मशीन नियतात्मक हो सकती है और फिर भी कभी रुकती या समाप्त नहीं होती है, और इसलिए परिणाम देने में विफल रहती है।


विशेष [[ अमूर्त मशीन ]]ों के उदाहरण जो नियतात्मक हैं, उनमें [[ नियतात्मक ट्यूरिंग मशीन ]] और नियतात्मक परिमित ऑटोमेटन शामिल हैं।
विशेष अमूर्त मशीनों के उदाहरण जो नियतात्मक हैं, उनमें [[ नियतात्मक ट्यूरिंग मशीन |नियतात्मक ट्यूरिंग मशीन]] और नियतात्मक परिमित ऑटोमेटन शामिल हैं।


== गैर-नियतात्मक एल्गोरिदम ==
== गैर-नियतात्मक एल्गोरिदम ==


विभिन्न प्रकार के कारक एक एल्गोरिथ्म को इस तरह से व्यवहार करने का कारण बना सकते हैं जो नियतात्मक या गैर-नियतात्मक नहीं है:
विभिन्न प्रकार के कारक एक एल्गोरिथम को इस तरह से व्यवहार करने का कारण बन सकते हैं जो नियतात्मक या गैर-नियतात्मक नहीं है:
* यदि यह इनपुट के अलावा किसी बाहरी स्थिति का उपयोग करता है, जैसे कि उपयोगकर्ता इनपुट, एक [[ वैश्विक चर ]], एक हार्डवेयर टाइमर मान, एक यादृच्छिकता मान या संग्रहीत डिस्क डेटा।
* यदि यह समय के प्रति संवेदनशील तरीके से संचालित होता है, उदाहरण के लिए, यदि इसके पास एक ही समय में एक ही डेटा पर लिखने वाले कई प्रोसेसर हैं। इस मामले में, सटीक क्रम जिसमें प्रत्येक प्रोसेसर अपना डेटा लिखता है, परिणाम को प्रभावित करेगा।
* यदि कोई हार्डवेयर त्रुटि इसकी स्थिति को अप्रत्याशित तरीके से बदलने का कारण बनती है।


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


[[ मल्टी-कोर प्रोसेसर ]] के प्रसार के परिणामस्वरूप समानांतर प्रोग्रामिंग में नियतत्ववाद में रुचि बढ़ी है और गैर-निर्धारणा की चुनौतियों को अच्छी तरह से प्रलेखित किया गया है।<ref>{{cite web | author = Edward A. Lee | url = http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf | access-date = 2009-05-29 | title = थ्रेड्स के साथ समस्या}}</ref><ref>{{cite conference |first1=Robert L. |last1=Bocchino Jr. |first2=Vikram S. |last2=Adve |first3=Sarita V. |last3=Adve |first4=Marc |last4=Snir |title=समानांतर प्रोग्रामिंग डिफ़ॉल्ट रूप से निश्चित होनी चाहिए|conference=[[USENIX]] Workshop on Hot Topics in Parallelism |year=2009 |url=https://www.usenix.org/legacy/event/hotpar09/tech/full_papers/bocchino/bocchino_html/}}</ref> चुनौतियों से निपटने में मदद के लिए कई उपकरण प्रस्तावित किए गए हैं<ref>{{cite web | url = http://software.intel.com/en-us/videos/intel-parallel-inspector-thread-checker/ | access-date = 2009-05-29 | title = इंटेल पैरेलल इंस्पेक्टर थ्रेड चेकर}}</ref><ref>{{cite web | author = Yuan Lin | url = http://developers.sun.com/sunstudio/documentation/product/sd_west_threadAnalyzer.pdf | title = सन स्टूडियो थ्रेड एनालाइज़र के साथ डेटा रेस और डेडलॉक डिटेक्शन| access-date = 2009-05-29}}</ref><ref>{{cite web | author = Intel | url = http://software.intel.com/en-us/intel-parallel-inspector | access-date = 2009-05-29 | title = इंटेल पैरेलल इंस्पेक्टर}}</ref><ref>{{cite web | url = http://sdtimes.com/link/33497 | title = इंटेल समानांतर स्टूडियो के साथ विकास जीवन चक्र को संबोधित करता है| author = David Worthington | access-date = 2009-05-26 | archive-url = https://web.archive.org/web/20090528030044/http://www.sdtimes.com/link/33497 | archive-date = 2009-05-28 | url-status = dead }}</ref> [[ गतिरोध ]] और [[ दौड़ की स्थिति ]] से निपटने के लिए।
हालांकि वास्तविक कार्यक्रम शायद ही कभी विशुद्ध रूप से नियतात्मक होते हैं, लेकिन मनुष्यों के साथ-साथ अन्य कार्यक्रमों के लिए भी ऐसे कार्यक्रमों के बारे में तर्क करना आसान होता है। इस कारण से, अधिकांश [[ प्रोग्रामिंग भाषा |प्रोग्रामिंग भाषाएं]] (प्रोग्रामिंग लैंग्वेज) और विशेष रूप से [[ कार्यात्मक प्रोग्रामिंग |फंक्शनल प्रोग्रामिंग]] भाषाएं उपरोक्त घटनाओं को नियंत्रित स्थितियों के अलावा होने से रोकने का प्रयास करती हैं।
 
[[ मल्टी-कोर प्रोसेसर |मल्टी-कोर प्रोसेसर]] के प्रसार के परिणामस्वरूप समानांतर प्रोग्रामिंग में नियतत्ववाद में रुचि बढ़ी है और गैर-नियतत्ववाद की चुनौतियों का अच्छी तरह से दस्तावेजीकरण किया गया है।<ref>{{cite web | author = Edward A. Lee | url = http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf | access-date = 2009-05-29 | title = थ्रेड्स के साथ समस्या}}</ref><ref>{{cite conference |first1=Robert L. |last1=Bocchino Jr. |first2=Vikram S. |last2=Adve |first3=Sarita V. |last3=Adve |first4=Marc |last4=Snir |title=समानांतर प्रोग्रामिंग डिफ़ॉल्ट रूप से निश्चित होनी चाहिए|conference=[[USENIX]] Workshop on Hot Topics in Parallelism |year=2009 |url=https://www.usenix.org/legacy/event/hotpar09/tech/full_papers/bocchino/bocchino_html/}}</ref> गतिरोध और दौड़ की स्थिति से निपटने के लिए चुनौतियों से निपटने में मदद के लिए कई उपकरण प्रस्तावित किए गए हैं <ref>{{cite web | url = http://software.intel.com/en-us/videos/intel-parallel-inspector-thread-checker/ | access-date = 2009-05-29 | title = इंटेल पैरेलल इंस्पेक्टर थ्रेड चेकर}}</ref><ref>{{cite web | author = Yuan Lin | url = http://developers.sun.com/sunstudio/documentation/product/sd_west_threadAnalyzer.pdf | title = सन स्टूडियो थ्रेड एनालाइज़र के साथ डेटा रेस और डेडलॉक डिटेक्शन| access-date = 2009-05-29}}</ref><ref>{{cite web | author = Intel | url = http://software.intel.com/en-us/intel-parallel-inspector | access-date = 2009-05-29 | title = इंटेल पैरेलल इंस्पेक्टर}}</ref><ref>{{cite web | url = http://sdtimes.com/link/33497 | title = इंटेल समानांतर स्टूडियो के साथ विकास जीवन चक्र को संबोधित करता है| author = David Worthington | access-date = 2009-05-26 | archive-url = https://web.archive.org/web/20090528030044/http://www.sdtimes.com/link/33497 | archive-date = 2009-05-28 | url-status = dead }}</ref>


== निश्चयवाद के नुकसान ==
== निश्चयवाद के नुकसान ==


कुछ मामलों में, एक कार्यक्रम के लिए गैर-नियतात्मक व्यवहार प्रदर्शित करना फायदेमंद होता है। उदाहरण के लिए, लाठी के खेल में उपयोग किए जाने वाले कार्ड शफलिंग प्रोग्राम का व्यवहार, खिलाड़ियों द्वारा अनुमानित नहीं होना चाहिए - भले ही प्रोग्राम का स्रोत कोड दिखाई दे रहा हो। छद्म आयामी संख्या जनरेटर का उपयोग अक्सर यह सुनिश्चित करने के लिए पर्याप्त नहीं होता है कि खिलाड़ी फेरबदल के परिणाम की भविष्यवाणी करने में असमर्थ हैं। एक चतुर जुआरी ठीक-ठीक अनुमान लगा सकता है कि जनरेटर कितनी संख्याओं का चयन करेगा और इसलिए समय से पहले डेक की संपूर्ण सामग्री का निर्धारण कर सकता है, जिससे उसे धोखा देने की अनुमति मिलती है; उदाहरण के लिए, रिलायबल सॉफ्टवेयर टेक्नोलॉजीज में सॉफ्टवेयर सुरक्षा समूह एएसएफ सॉफ्टवेयर, इंक द्वारा वितरित टेक्सास होल्डम पोकर के कार्यान्वयन के लिए ऐसा करने में सक्षम था, जिससे उन्हें समय से पहले हाथों के परिणाम की लगातार भविष्यवाणी करने की अनुमति मिलती है।<ref>{{cite web |author-link1=Gary McGraw |first1=Gary |last1=McGraw |author-link2=John Viega |first2=John |last2=Viega |title=अपने सॉफ़्टवेयर को व्यवहार में लाएँ: नंबर बजाना: ऑनलाइन जुए में कैसे धोखा देना है।|url=http://www.ibm.com/developerworks/library/s-playing/#h4 |url-status=dead |access-date=2007-07-02 |archive-date=2008-03-13 |archive-url=https://web.archive.org/web/20080313043638/http://www.ibm.com/developerworks/library/s-playing/#h4 }}</ref> क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर के उपयोग के माध्यम से, इन समस्याओं से बचा जा सकता है, लेकिन जनरेटर को आरंभ करने के लिए एक अप्रत्याशित यादृच्छिक बीज का उपयोग करना अभी भी आवश्यक है। इस प्रयोजन के लिए, अनिर्धारणवाद के स्रोत की आवश्यकता होती है, जैसे कि एक [[ हार्डवेयर यादृच्छिक संख्या जनरेटर ]] द्वारा प्रदान किया गया।
कुछ मामलों में, एक कार्यक्रम के लिए गैर-नियतात्मक व्यवहार प्रदर्शित करना फायदेमंद होता है। उदाहरण के लिए, लाठी के खेल में उपयोग किए जाने वाले कार्ड शफलिंग प्रोग्राम का व्यवहार, खिलाड़ियों द्वारा अनुमानित नहीं होना चाहिए - भले ही प्रोग्राम का स्रोत कोड दिखाई दे रहा हो। छद्म आयामी संख्या जनरेटर का उपयोग अक्सर यह सुनिश्चित करने के लिए पर्याप्त नहीं होता है कि खिलाड़ी फेरबदल के परिणाम की भविष्यवाणी करने में असमर्थ हैं। एक चतुर जुआरी ठीक-ठीक अनुमान लगा सकता है कि जनरेटर कितनी संख्याओं का चयन करेगा और इसलिए समय से पहले डेक की संपूर्ण सामग्री का निर्धारण कर सकता है, जिससे उसे धोखा देने की अनुमति मिलती है; उदाहरण के लिए, रिलायबल सॉफ्टवेयर टेक्नोलॉजीज में सॉफ्टवेयर सुरक्षा समूह टेक्सास होल्डम पोकर के कार्यान्वयन के लिए ऐसा करने में सक्षम था जो एएसएफ सॉफ्टवेयर, इंक द्वारा वितरित किया जाता है, जिससे उन्हें समय से पहले हाथ के परिणाम की लगातार भविष्यवाणी करने की अनुमति मिलती है।<ref>{{cite web |author-link1=Gary McGraw |first1=Gary |last1=McGraw |author-link2=John Viega |first2=John |last2=Viega |title=अपने सॉफ़्टवेयर को व्यवहार में लाएँ: नंबर बजाना: ऑनलाइन जुए में कैसे धोखा देना है।|url=http://www.ibm.com/developerworks/library/s-playing/#h4 |url-status=dead |access-date=2007-07-02 |archive-date=2008-03-13 |archive-url=https://web.archive.org/web/20080313043638/http://www.ibm.com/developerworks/library/s-playing/#h4 }}</ref> क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर के उपयोग के माध्यम से, इन समस्याओं से बचा जा सकता है, लेकिन जनरेटर को प्रारंभ करने के लिए अप्रत्याशित यादृच्छिक बीज का उपयोग करना अभी भी आवश्यक है। इस उद्देश्य के लिए, गैर-नियतत्ववाद के स्रोत की आवश्यकता होती है, जैसे कि [[ हार्डवेयर यादृच्छिक संख्या जनरेटर |हार्डवेयर रैंडम नंबर जेनरेटर]] द्वारा प्रदान किया गया।
 
ध्यान दें कि पी = एनपी समस्या का एक नकारात्मक उत्तर यह नहीं दर्शाता है कि गैर-नियतात्मक आउटपुट वाले कार्यक्रम सैद्धांतिक रूप से नियतात्मक आउटपुट वाले कार्यक्रमों की तुलना में अधिक शक्तिशाली हैं। जटिलता वर्ग [[ एनपी (जटिलता) ]] को एनपी (जटिलता) | सत्यापनकर्ता-आधारित परिभाषा का उपयोग करके गैर-निर्धारणवाद के किसी भी संदर्भ के बिना परिभाषित किया जा सकता है।
 
== भाषाओं में नियतत्ववाद श्रेणियां ==


=== बुध ===
ध्यान दें कि पी = एनपी समस्या का एक नकारात्मक उत्तर यह नहीं दर्शाता है कि गैर-नियतात्मक आउटपुट वाले कार्यक्रम सैद्धांतिक रूप से नियतात्मक आउटपुट वाले लोगों की तुलना में अधिक शक्तिशाली हैं। सत्यापनकर्ता-आधारित परिभाषा का उपयोग करते हुए जटिलता वर्ग [[ एनपी (जटिलता) |एनपी (जटिलता)]] को बिना किसी संदर्भ के परिभाषित किया जा सकता है।
मरकरी (प्रोग्रामिंग लैंग्वेज) लॉजिक-फंक्शनल प्रोग्रामिंग लैंग्वेज प्रेडिकेट मोड्स के लिए अलग-अलग नियतत्ववाद श्रेणियों को स्थापित करती है जैसा कि संदर्भ में बताया गया है।<ref>{{Cite web |url=http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Determinism-categories.html |title=बुध प्रोग्रामिंग भाषा में नियतत्ववाद श्रेणियां|access-date=2013-02-23 |archive-url=https://web.archive.org/web/20120703001434/http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Determinism-categories.html#Determinism-categories |archive-date=2012-07-03 |url-status=dead }}</ref><ref>{{Cite web |url=http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Predicate-and-function-mode-declarations.html |title=बुध विधेय मोड|access-date=2013-02-25 |archive-url=https://web.archive.org/web/20120703001411/http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Predicate-and-function-mode-declarations.html#Predicate-and-function-mode-declarations |archive-date=2012-07-03 |url-status=dead }}</ref>
 
 
=== [[ हास्केल ]] ===
हास्केल कई तंत्र प्रदान करता है:
* गैर-निर्धारणा या असफल होने की धारणा
** हो सकता है और कोई भी प्रकार परिणाम में सफलता की धारणा को शामिल करता है।
** मोनाड वर्ग की असफल विधि, अपवाद के रूप में विफल होने का संकेत देने के लिए इस्तेमाल की जा सकती है।
** शायद [[ मोनाड (कार्यात्मक प्रोग्रामिंग) ]] और मेबेट मोनाड ट्रांसफार्मर विफल संगणनाओं के लिए प्रदान करते हैं (गणना अनुक्रम को रोकें और कुछ भी वापस न करें)<ref>{{cite web|url=http://www.haskell.org/haskellwiki/Monad#Common_monads |title=हो सकता है मोनाड का उपयोग करके विफलता का प्रतिनिधित्व करना}}</ref>
* कई समाधानों के साथ नेटरमिनिज्म/नॉन-डिटेक्ट
** आप एक मोनाडप्लस मोनाड (कार्यात्मक प्रोग्रामिंग) में इसके परिणाम प्रकार को लपेटकर, एक से अधिक परिणाम संगणना के सभी संभावित परिणामों को पुनः प्राप्त कर सकते हैं। (इसकी विधि mzero एक परिणाम को विफल कर देती है और mplus सफल परिणाम एकत्र करता है)।<ref name="monad-plus">{{cite web|url=http://www.haskell.org/haskellwiki/MonadPlus |title=क्लास मोनाडप्लस}}</ref>


== भाषाओं में निर्धारणा श्रेणियां ==


=== मरकरी ===
मरकरी लॉजिक-फंक्शनल प्रोग्रामिंग भाषा विधेय मोड के लिए विभिन्न नियतात्मक श्रेणियों की स्थापना करती है जैसा कि संदर्भ में समझाया गया है।<ref>{{Cite web |url=http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Determinism-categories.html |title=बुध प्रोग्रामिंग भाषा में नियतत्ववाद श्रेणियां|access-date=2013-02-23 |archive-url=https://web.archive.org/web/20120703001434/http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Determinism-categories.html#Determinism-categories |archive-date=2012-07-03 |url-status=dead }}</ref><ref>{{Cite web |url=http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Predicate-and-function-mode-declarations.html |title=बुध विधेय मोड|access-date=2013-02-25 |archive-url=https://web.archive.org/web/20120703001411/http://www.mercury.csse.unimelb.edu.au/information/doc-release/mercury_ref/Predicate-and-function-mode-declarations.html#Predicate-and-function-mode-declarations |archive-date=2012-07-03 |url-status=dead }}</ref>
=== [[ हास्केल |हास्केल]] ===
हास्केल कई तंत्र उपलब्ध कराता है:
* गैर नियतत्ववाद या विफलता धारणा
** शायद और कोई भी प्रकार परिणाम में सफलता की धारणा को शामिल करता है।
** अपवाद के रूप में विफल होने के संकेत के लिए मोनाड वर्ग की असफल विधि का उपयोग किया जा सकता है।
** हो सकता है [[ मोनाड (कार्यात्मक प्रोग्रामिंग) |मोनाड]] और होबीट मोनाड ट्रांसफॉर्मर विफल संगणनाओं के लिए प्रदान करते हैं (गणना अनुक्रम रोकें और कुछ भी वापस न करें)। <ref>{{cite web|url=http://www.haskell.org/haskellwiki/Monad#Common_monads |title=हो सकता है मोनाड का उपयोग करके विफलता का प्रतिनिधित्व करना}}</ref>
* कई समाधानों के साथ नियतत्ववाद/गैर-पता लगाना
** आप मोनाडप्लस मोनाड में इसके परिणाम प्रकार को लपेटकर, बहु-परिणाम संगणनाओं के सभी संभावित परिणामों को पुनः प्राप्त कर सकते हैं। (इसकी विधि एमजीरो एक परिणाम को असफल बनाती है और एमप्लस सफल परिणाम एकत्र करता है)।<ref name="monad-plus">{{cite web|url=http://www.haskell.org/haskellwiki/MonadPlus |title=क्लास मोनाडप्लस}}</ref>
=== एमएल परिवार और व्युत्पन्न भाषाएँ ===
=== एमएल परिवार और व्युत्पन्न भाषाएँ ===


जैसा कि [[ Standard ML ]], [[ OCaml ]] और Scala (प्रोग्रामिंग भाषा) में देखा गया है
जैसा कि स्टैंडर्ड एमएल ([[ Standard ML |Standard ML]]), ओकैमल ([[ OCaml |OCaml]]) और स्काला में देखा गया है
* विकल्प प्रकार में सफलता की धारणा शामिल है।
* विकल्प प्रकार में सफलता की धारणा शामिल होती है।


=== जावा ===
=== जावा ===
[[ जावा (प्रोग्रामिंग भाषा) ]] में, शून्य संदर्भ मान एक असफल (आउट-ऑफ़-डोमेन) परिणाम का प्रतिनिधित्व कर सकता है।
[[ जावा (प्रोग्रामिंग भाषा) | जावा]] में, शून्य संदर्भ मान एक असफल (आउट-ऑफ़-डोमेन) परिणाम का प्रतिनिधित्व कर सकता है।


== यह भी देखें ==
== यह भी देखें ==
* [[ यादृच्छिक एल्गोरिदम ]]
* [[ यादृच्छिक एल्गोरिदम |रैंडमाइज्ड एल्गोरिथम]]
 


*
*
Line 59: Line 55:


<references />
<references />
[[श्रेणी: एल्गोरिदम का विश्लेषण]]


[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 01/01/2023]]
[[Category:Created On 01/01/2023]]

Revision as of 14:27, 13 January 2023

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

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

औपचारिक परिभाषा

नियतात्मक एल्गोरिदम को स्टेट मशीन के संदर्भ में परिभाषित किया जा सकता है: एक राज्य वर्णन करता है कि एक समय में एक विशेष समय पर एक मशीन क्या कर रही है। राज्य मशीनें एक राज्य से दूसरे राज्य में असतत तरीके से गुजरती हैं। जैसे ही हम इनपुट दर्ज करते हैं, मशीन अपनी प्रारंभिक अवस्था या प्रारंभ अवस्था में होती है। यदि मशीन नियतात्मक है, तो इसका मतलब है कि इस बिंदु से, इसकी वर्तमान स्थिति निर्धारित करती है कि इसकी अगली स्थिति क्या होगी; राज्यों के सेट के माध्यम से इसका पाठ्यक्रम पूर्व निर्धारित है। ध्यान दें कि एक मशीन नियतात्मक हो सकती है और फिर भी कभी रुकती या समाप्त नहीं होती है, और इसलिए परिणाम देने में विफल रहती है।

विशेष अमूर्त मशीनों के उदाहरण जो नियतात्मक हैं, उनमें नियतात्मक ट्यूरिंग मशीन और नियतात्मक परिमित ऑटोमेटन शामिल हैं।

गैर-नियतात्मक एल्गोरिदम

विभिन्न प्रकार के कारक एक एल्गोरिथम को इस तरह से व्यवहार करने का कारण बन सकते हैं जो नियतात्मक या गैर-नियतात्मक नहीं है:

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

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

मल्टी-कोर प्रोसेसर के प्रसार के परिणामस्वरूप समानांतर प्रोग्रामिंग में नियतत्ववाद में रुचि बढ़ी है और गैर-नियतत्ववाद की चुनौतियों का अच्छी तरह से दस्तावेजीकरण किया गया है।[1][2] गतिरोध और दौड़ की स्थिति से निपटने के लिए चुनौतियों से निपटने में मदद के लिए कई उपकरण प्रस्तावित किए गए हैं [3][4][5][6]

निश्चयवाद के नुकसान

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

ध्यान दें कि पी = एनपी समस्या का एक नकारात्मक उत्तर यह नहीं दर्शाता है कि गैर-नियतात्मक आउटपुट वाले कार्यक्रम सैद्धांतिक रूप से नियतात्मक आउटपुट वाले लोगों की तुलना में अधिक शक्तिशाली हैं। सत्यापनकर्ता-आधारित परिभाषा का उपयोग करते हुए जटिलता वर्ग एनपी (जटिलता) को बिना किसी संदर्भ के परिभाषित किया जा सकता है।

भाषाओं में निर्धारणा श्रेणियां

मरकरी

मरकरी लॉजिक-फंक्शनल प्रोग्रामिंग भाषा विधेय मोड के लिए विभिन्न नियतात्मक श्रेणियों की स्थापना करती है जैसा कि संदर्भ में समझाया गया है।[8][9]

हास्केल

हास्केल कई तंत्र उपलब्ध कराता है:

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

एमएल परिवार और व्युत्पन्न भाषाएँ

जैसा कि स्टैंडर्ड एमएल (Standard ML), ओकैमल (OCaml) और स्काला में देखा गया है

  • विकल्प प्रकार में सफलता की धारणा शामिल होती है।

जावा

जावा में, शून्य संदर्भ मान एक असफल (आउट-ऑफ़-डोमेन) परिणाम का प्रतिनिधित्व कर सकता है।

यह भी देखें

संदर्भ

  1. Edward A. Lee. "थ्रेड्स के साथ समस्या" (PDF). Retrieved 2009-05-29.
  2. Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). समानांतर प्रोग्रामिंग डिफ़ॉल्ट रूप से निश्चित होनी चाहिए. USENIX Workshop on Hot Topics in Parallelism.
  3. "इंटेल पैरेलल इंस्पेक्टर थ्रेड चेकर". Retrieved 2009-05-29.
  4. Yuan Lin. "सन स्टूडियो थ्रेड एनालाइज़र के साथ डेटा रेस और डेडलॉक डिटेक्शन" (PDF). Retrieved 2009-05-29.
  5. Intel. "इंटेल पैरेलल इंस्पेक्टर". Retrieved 2009-05-29.
  6. David Worthington. "इंटेल समानांतर स्टूडियो के साथ विकास जीवन चक्र को संबोधित करता है". Archived from the original on 2009-05-28. Retrieved 2009-05-26.
  7. McGraw, Gary; Viega, John. "अपने सॉफ़्टवेयर को व्यवहार में लाएँ: नंबर बजाना: ऑनलाइन जुए में कैसे धोखा देना है।". Archived from the original on 2008-03-13. Retrieved 2007-07-02.
  8. "बुध प्रोग्रामिंग भाषा में नियतत्ववाद श्रेणियां". Archived from the original on 2012-07-03. Retrieved 2013-02-23.
  9. "बुध विधेय मोड". Archived from the original on 2012-07-03. Retrieved 2013-02-25.
  10. "हो सकता है मोनाड का उपयोग करके विफलता का प्रतिनिधित्व करना".
  11. "क्लास मोनाडप्लस".