नियतात्मक एल्गोरिथ्म: Difference between revisions
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{Short description|Type of algorithm in computer science}} | {{Short description|Type of algorithm in computer science}} | ||
[[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, नियतात्मक एल्गोरिथम ([[ कलन विधि |कलन विधि]]) एक एल्गोरिथम है, जो | [[ कंप्यूटर विज्ञान |कंप्यूटर विज्ञान]] में, '''नियतात्मक एल्गोरिथम''' ([[ कलन विधि |कलन विधि]]) एक एल्गोरिथम है, जो विशेष इनपुट दिए जाने पर, हमेशा एक ही आउटपुट का उत्पादन करेगा, जिसमें अंतर्निहित मशीन हमेशा राज्यों के समान अनुक्रम से गुजरती है। नियतात्मक एल्गोरिदम अब तक सबसे अधिक अध्ययन और परिचित प्रकार के एल्गोरिदम हैं, साथ ही साथ सबसे व्यावहारिक में से एक हैं क्योंकि उन्हें वास्तविक मशीनों पर कुशलता से चलाया जा सकता है। | ||
औपचारिक रूप से, नियतात्मक एल्गोरिथम | औपचारिक रूप से, नियतात्मक एल्गोरिथम गणितीय फलन की गणना करता है; फ़ंक्शन का अपने डोमेन में किसी भी इनपुट के लिए एक अद्वितीय मान होता है, और एल्गोरिथम एक ऐसी प्रक्रिया है जो इस विशेष मान को आउटपुट के रूप में उत्पन्न करती है। | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
नियतात्मक एल्गोरिदम को स्टेट मशीन के संदर्भ में परिभाषित किया जा सकता है: | नियतात्मक एल्गोरिदम को स्टेट मशीन के संदर्भ में परिभाषित किया जा सकता है: राज्य वर्णन करता है कि एक समय में विशेष समय पर मशीन क्या कर रही है। राज्य मशीनें राज्य से दूसरे राज्य में असतत तरीके से गुजरती हैं। जैसे ही हम इनपुट दर्ज करते हैं, मशीन अपनी प्रारंभिक अवस्था या प्रारंभ अवस्था में होती है। यदि मशीन नियतात्मक है, तो इसका मतलब है कि इस बिंदु से, इसकी वर्तमान स्थिति निर्धारित करती है कि इसकी अगली स्थिति क्या होगी; राज्यों के सेट के माध्यम से इसका पाठ्यक्रम पूर्व निर्धारित है। ध्यान दें कि मशीन नियतात्मक हो सकती है और फिर भी कभी रुकती या समाप्त नहीं होती है, और इसलिए परिणाम देने में विफल रहती है। | ||
विशेष अमूर्त मशीनों के उदाहरण जो नियतात्मक हैं, उनमें [[ नियतात्मक ट्यूरिंग मशीन |नियतात्मक ट्यूरिंग मशीन]] और नियतात्मक परिमित ऑटोमेटन | विशेष अमूर्त मशीनों के उदाहरण जो नियतात्मक हैं, उनमें [[ नियतात्मक ट्यूरिंग मशीन |नियतात्मक ट्यूरिंग मशीन]] और नियतात्मक परिमित ऑटोमेटन सम्मिलित हैं। | ||
== गैर-नियतात्मक एल्गोरिदम == | == गैर-नियतात्मक एल्गोरिदम == | ||
विभिन्न प्रकार के कारक | विभिन्न प्रकार के कारक एल्गोरिथम को इस तरह से व्यवहार करने का कारण बन सकते हैं जो नियतात्मक या गैर-नियतात्मक नहीं है: | ||
* यदि यह इनपुट के अलावा किसी बाहरी स्थिति का उपयोग करता है, जैसे उपयोगकर्ता इनपुट, वैश्विक चर, हार्डवेयर टाइमर मान, यादृच्छिक मान या संग्रहीत डिस्क डेटा। | * यदि यह इनपुट के अलावा किसी बाहरी स्थिति का उपयोग करता है, जैसे उपयोगकर्ता इनपुट, वैश्विक चर, हार्डवेयर टाइमर मान, यादृच्छिक मान या संग्रहीत डिस्क डेटा। | ||
* यदि यह समय के प्रति संवेदनशील तरीके से संचालित होता है, उदाहरण के लिए, यदि इसमें एक ही समय में | * यदि यह समय के प्रति संवेदनशील तरीके से संचालित होता है, उदाहरण के लिए, यदि इसमें एक ही समय में ही डेटा पर कई प्रोसेसर लिख रहे हैं। इस स्थिति में, सटीक क्रम जिसमें प्रत्येक प्रोसेसर अपना डेटा लिखता है, परिणाम को प्रभावित करेगा। | ||
* यदि हार्डवेयर त्रुटि के कारण इसकी स्थिति अप्रत्याशित रूप से बदल जाती है। | * यदि हार्डवेयर त्रुटि के कारण इसकी स्थिति अप्रत्याशित रूप से बदल जाती है। | ||
| Line 24: | Line 24: | ||
== निश्चयवाद के नुकसान == | == निश्चयवाद के नुकसान == | ||
कुछ मामलों में, एक कार्यक्रम के लिए गैर-नियतात्मक व्यवहार प्रदर्शित करना फायदेमंद होता है। उदाहरण के लिए, लाठी के खेल में उपयोग किए जाने वाले कार्ड शफलिंग प्रोग्राम का व्यवहार, खिलाड़ियों द्वारा अनुमानित नहीं होना चाहिए - भले ही प्रोग्राम का स्रोत कोड दिखाई दे रहा हो। छद्म आयामी संख्या जनरेटर का उपयोग | कुछ मामलों में, एक कार्यक्रम के लिए गैर-नियतात्मक व्यवहार प्रदर्शित करना फायदेमंद होता है। उदाहरण के लिए, लाठी के खेल में उपयोग किए जाने वाले कार्ड शफलिंग प्रोग्राम का व्यवहार, खिलाड़ियों द्वारा अनुमानित नहीं होना चाहिए - भले ही प्रोग्राम का स्रोत कोड दिखाई दे रहा हो। छद्म आयामी संख्या जनरेटर का उपयोग प्रायः यह सुनिश्चित करने के लिए पर्याप्त नहीं होता है कि खिलाड़ी फेरबदल के परिणाम की भविष्यवाणी करने में असमर्थ हैं। चतुर जुआरी ठीक-ठीक अनुमान लगा सकता है कि जनरेटर कितनी संख्याओं का चयन करेगा और इसलिए समय से पहले डेक की संपूर्ण सामग्री का निर्धारण कर सकता है, जिससे उसे धोखा देने की अनुमति मिलती है; उदाहरण के लिए, रिलायबल सॉफ्टवेयर टेक्नोलॉजीज में सॉफ्टवेयर सुरक्षा समूह टेक्सास होल्डम पोकर के कार्यान्वयन के लिए ऐसा करने में सक्षम था जो एएसएफ सॉफ्टवेयर, इंक द्वारा वितरित किया जाता है, जिससे उन्हें समय से पहले हाथ के परिणाम की लगातार भविष्यवाणी करने की अनुमति मिलती है।<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> क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर के उपयोग के माध्यम से, इन समस्याओं से बचा जा सकता है, लेकिन जनरेटर को प्रारंभ करने के लिए अप्रत्याशित यादृच्छिक बीज का उपयोग करना अभी भी आवश्यक है। इस उद्देश्य के लिए, गैर-नियतत्ववाद के स्रोत की आवश्यकता होती है, जैसे कि [[ हार्डवेयर यादृच्छिक संख्या जनरेटर |हार्डवेयर रैंडम नंबर जेनरेटर]] द्वारा प्रदान किया गया। | ||
ध्यान दें कि पी = एनपी समस्या का एक | ध्यान दें कि पी = एनपी समस्या का एक ऋणात्मक उत्तर यह नहीं दर्शाता है कि गैर-नियतात्मक आउटपुट वाले कार्यक्रम सैद्धांतिक रूप से नियतात्मक आउटपुट वाले लोगों की तुलना में अधिक शक्तिशाली हैं। सत्यापनकर्ता-आधारित परिभाषा का उपयोग करते हुए जटिलता वर्ग [[ एनपी (जटिलता) |एनपी (जटिलता)]] को बिना किसी संदर्भ के परिभाषित किया जा सकता है। | ||
== भाषाओं में निर्धारणा श्रेणियां == | == भाषाओं में निर्धारणा श्रेणियां == | ||
| Line 35: | Line 35: | ||
हास्केल कई तंत्र उपलब्ध कराता है: | हास्केल कई तंत्र उपलब्ध कराता है: | ||
* गैर नियतत्ववाद या विफलता धारणा | * गैर नियतत्ववाद या विफलता धारणा | ||
** शायद और कोई भी प्रकार परिणाम में सफलता की धारणा को | ** शायद और कोई भी प्रकार परिणाम में सफलता की धारणा को सम्मिलित करता है। | ||
** अपवाद के रूप में विफल होने के संकेत के लिए मोनाड वर्ग की असफल विधि का उपयोग किया जा सकता है। | ** अपवाद के रूप में विफल होने के संकेत के लिए मोनाड वर्ग की असफल विधि का उपयोग किया जा सकता है। | ||
** हो सकता है [[ मोनाड (कार्यात्मक प्रोग्रामिंग) |मोनाड]] और होबीट मोनाड ट्रांसफॉर्मर विफल संगणनाओं के लिए प्रदान करते हैं (गणना अनुक्रम रोकें और कुछ भी वापस न करें)। <ref>{{cite web|url=http://www.haskell.org/haskellwiki/Monad#Common_monads |title=हो सकता है मोनाड का उपयोग करके विफलता का प्रतिनिधित्व करना}}</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 |Standard ML]]), ओकैमल ([[ OCaml |OCaml]]) और स्काला में देखा गया है | जैसा कि स्टैंडर्ड एमएल ([[ Standard ML |Standard ML]]), ओकैमल ([[ OCaml |OCaml]]) और स्काला में देखा गया है | ||
* विकल्प प्रकार में सफलता की धारणा | * विकल्प प्रकार में सफलता की धारणा सम्मिलित होती है। | ||
=== जावा === | === जावा === | ||
[[ जावा (प्रोग्रामिंग भाषा) | जावा]] में, शून्य संदर्भ मान | [[ जावा (प्रोग्रामिंग भाषा) | जावा]] में, शून्य संदर्भ मान असफल (आउट-ऑफ़-डोमेन) परिणाम का प्रतिनिधित्व कर सकता है। | ||
== यह भी देखें == | == यह भी देखें == | ||
| Line 56: | Line 56: | ||
<references /> | <references /> | ||
[[Category:Created On 01/01/2023]] | [[Category:Created On 01/01/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
Latest revision as of 15:08, 4 September 2023
कंप्यूटर विज्ञान में, नियतात्मक एल्गोरिथम (कलन विधि) एक एल्गोरिथम है, जो विशेष इनपुट दिए जाने पर, हमेशा एक ही आउटपुट का उत्पादन करेगा, जिसमें अंतर्निहित मशीन हमेशा राज्यों के समान अनुक्रम से गुजरती है। नियतात्मक एल्गोरिदम अब तक सबसे अधिक अध्ययन और परिचित प्रकार के एल्गोरिदम हैं, साथ ही साथ सबसे व्यावहारिक में से एक हैं क्योंकि उन्हें वास्तविक मशीनों पर कुशलता से चलाया जा सकता है।
औपचारिक रूप से, नियतात्मक एल्गोरिथम गणितीय फलन की गणना करता है; फ़ंक्शन का अपने डोमेन में किसी भी इनपुट के लिए एक अद्वितीय मान होता है, और एल्गोरिथम एक ऐसी प्रक्रिया है जो इस विशेष मान को आउटपुट के रूप में उत्पन्न करती है।
औपचारिक परिभाषा
नियतात्मक एल्गोरिदम को स्टेट मशीन के संदर्भ में परिभाषित किया जा सकता है: राज्य वर्णन करता है कि एक समय में विशेष समय पर मशीन क्या कर रही है। राज्य मशीनें राज्य से दूसरे राज्य में असतत तरीके से गुजरती हैं। जैसे ही हम इनपुट दर्ज करते हैं, मशीन अपनी प्रारंभिक अवस्था या प्रारंभ अवस्था में होती है। यदि मशीन नियतात्मक है, तो इसका मतलब है कि इस बिंदु से, इसकी वर्तमान स्थिति निर्धारित करती है कि इसकी अगली स्थिति क्या होगी; राज्यों के सेट के माध्यम से इसका पाठ्यक्रम पूर्व निर्धारित है। ध्यान दें कि मशीन नियतात्मक हो सकती है और फिर भी कभी रुकती या समाप्त नहीं होती है, और इसलिए परिणाम देने में विफल रहती है।
विशेष अमूर्त मशीनों के उदाहरण जो नियतात्मक हैं, उनमें नियतात्मक ट्यूरिंग मशीन और नियतात्मक परिमित ऑटोमेटन सम्मिलित हैं।
गैर-नियतात्मक एल्गोरिदम
विभिन्न प्रकार के कारक एल्गोरिथम को इस तरह से व्यवहार करने का कारण बन सकते हैं जो नियतात्मक या गैर-नियतात्मक नहीं है:
- यदि यह इनपुट के अलावा किसी बाहरी स्थिति का उपयोग करता है, जैसे उपयोगकर्ता इनपुट, वैश्विक चर, हार्डवेयर टाइमर मान, यादृच्छिक मान या संग्रहीत डिस्क डेटा।
- यदि यह समय के प्रति संवेदनशील तरीके से संचालित होता है, उदाहरण के लिए, यदि इसमें एक ही समय में ही डेटा पर कई प्रोसेसर लिख रहे हैं। इस स्थिति में, सटीक क्रम जिसमें प्रत्येक प्रोसेसर अपना डेटा लिखता है, परिणाम को प्रभावित करेगा।
- यदि हार्डवेयर त्रुटि के कारण इसकी स्थिति अप्रत्याशित रूप से बदल जाती है।
हालांकि वास्तविक कार्यक्रम शायद ही कभी विशुद्ध रूप से नियतात्मक होते हैं, लेकिन मनुष्यों के साथ-साथ अन्य कार्यक्रमों के लिए भी ऐसे कार्यक्रमों के बारे में तर्क करना आसान होता है। इस कारण से, अधिकांश प्रोग्रामिंग भाषाएं (प्रोग्रामिंग लैंग्वेज) और विशेष रूप से फंक्शनल प्रोग्रामिंग भाषाएं उपरोक्त घटनाओं को नियंत्रित स्थितियों के अलावा होने से रोकने का प्रयास करती हैं।
मल्टी-कोर प्रोसेसर के प्रसार के परिणामस्वरूप समानांतर प्रोग्रामिंग में नियतत्ववाद में रुचि बढ़ी है और गैर-नियतत्ववाद की चुनौतियों का अच्छी तरह से दस्तावेजीकरण किया गया है।[1][2] गतिरोध और दौड़ की स्थिति से निपटने के लिए चुनौतियों से निपटने में मदद के लिए कई उपकरण प्रस्तावित किए गए हैं [3][4][5][6]।
निश्चयवाद के नुकसान
कुछ मामलों में, एक कार्यक्रम के लिए गैर-नियतात्मक व्यवहार प्रदर्शित करना फायदेमंद होता है। उदाहरण के लिए, लाठी के खेल में उपयोग किए जाने वाले कार्ड शफलिंग प्रोग्राम का व्यवहार, खिलाड़ियों द्वारा अनुमानित नहीं होना चाहिए - भले ही प्रोग्राम का स्रोत कोड दिखाई दे रहा हो। छद्म आयामी संख्या जनरेटर का उपयोग प्रायः यह सुनिश्चित करने के लिए पर्याप्त नहीं होता है कि खिलाड़ी फेरबदल के परिणाम की भविष्यवाणी करने में असमर्थ हैं। चतुर जुआरी ठीक-ठीक अनुमान लगा सकता है कि जनरेटर कितनी संख्याओं का चयन करेगा और इसलिए समय से पहले डेक की संपूर्ण सामग्री का निर्धारण कर सकता है, जिससे उसे धोखा देने की अनुमति मिलती है; उदाहरण के लिए, रिलायबल सॉफ्टवेयर टेक्नोलॉजीज में सॉफ्टवेयर सुरक्षा समूह टेक्सास होल्डम पोकर के कार्यान्वयन के लिए ऐसा करने में सक्षम था जो एएसएफ सॉफ्टवेयर, इंक द्वारा वितरित किया जाता है, जिससे उन्हें समय से पहले हाथ के परिणाम की लगातार भविष्यवाणी करने की अनुमति मिलती है।[7] क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म-यादृच्छिक संख्या जनरेटर के उपयोग के माध्यम से, इन समस्याओं से बचा जा सकता है, लेकिन जनरेटर को प्रारंभ करने के लिए अप्रत्याशित यादृच्छिक बीज का उपयोग करना अभी भी आवश्यक है। इस उद्देश्य के लिए, गैर-नियतत्ववाद के स्रोत की आवश्यकता होती है, जैसे कि हार्डवेयर रैंडम नंबर जेनरेटर द्वारा प्रदान किया गया।
ध्यान दें कि पी = एनपी समस्या का एक ऋणात्मक उत्तर यह नहीं दर्शाता है कि गैर-नियतात्मक आउटपुट वाले कार्यक्रम सैद्धांतिक रूप से नियतात्मक आउटपुट वाले लोगों की तुलना में अधिक शक्तिशाली हैं। सत्यापनकर्ता-आधारित परिभाषा का उपयोग करते हुए जटिलता वर्ग एनपी (जटिलता) को बिना किसी संदर्भ के परिभाषित किया जा सकता है।
भाषाओं में निर्धारणा श्रेणियां
मरकरी
मरकरी लॉजिक-फंक्शनल प्रोग्रामिंग भाषा विधेय मोड के लिए विभिन्न नियतात्मक श्रेणियों की स्थापना करती है जैसा कि संदर्भ में समझाया गया है।[8][9]
हास्केल
हास्केल कई तंत्र उपलब्ध कराता है:
- गैर नियतत्ववाद या विफलता धारणा
- कई समाधानों के साथ नियतत्ववाद/गैर-पता लगाना
- आप मोनाडप्लस मोनाड में इसके परिणाम प्रकार को लपेटकर, बहु-परिणाम संगणनाओं के सभी संभावित परिणामों को पुनः प्राप्त कर सकते हैं। (इसकी विधि एमजीरो परिणाम को असफल बनाती है और एमप्लस सफल परिणाम एकत्र करता है)।[11]
एमएल परिवार और व्युत्पन्न भाषाएँ
जैसा कि स्टैंडर्ड एमएल (Standard ML), ओकैमल (OCaml) और स्काला में देखा गया है
- विकल्प प्रकार में सफलता की धारणा सम्मिलित होती है।
जावा
जावा में, शून्य संदर्भ मान असफल (आउट-ऑफ़-डोमेन) परिणाम का प्रतिनिधित्व कर सकता है।
यह भी देखें
संदर्भ
- ↑ Edward A. Lee. "थ्रेड्स के साथ समस्या" (PDF). Retrieved 2009-05-29.
- ↑ Bocchino Jr., Robert L.; Adve, Vikram S.; Adve, Sarita V.; Snir, Marc (2009). समानांतर प्रोग्रामिंग डिफ़ॉल्ट रूप से निश्चित होनी चाहिए. USENIX Workshop on Hot Topics in Parallelism.
- ↑ "इंटेल पैरेलल इंस्पेक्टर थ्रेड चेकर". Retrieved 2009-05-29.
- ↑ Yuan Lin. "सन स्टूडियो थ्रेड एनालाइज़र के साथ डेटा रेस और डेडलॉक डिटेक्शन" (PDF). Retrieved 2009-05-29.
- ↑ Intel. "इंटेल पैरेलल इंस्पेक्टर". Retrieved 2009-05-29.
- ↑ David Worthington. "इंटेल समानांतर स्टूडियो के साथ विकास जीवन चक्र को संबोधित करता है". Archived from the original on 2009-05-28. Retrieved 2009-05-26.
- ↑ McGraw, Gary; Viega, John. "अपने सॉफ़्टवेयर को व्यवहार में लाएँ: नंबर बजाना: ऑनलाइन जुए में कैसे धोखा देना है।". Archived from the original on 2008-03-13. Retrieved 2007-07-02.
- ↑ "बुध प्रोग्रामिंग भाषा में नियतत्ववाद श्रेणियां". Archived from the original on 2012-07-03. Retrieved 2013-02-23.
- ↑ "बुध विधेय मोड". Archived from the original on 2012-07-03. Retrieved 2013-02-25.
- ↑ "हो सकता है मोनाड का उपयोग करके विफलता का प्रतिनिधित्व करना".
- ↑ "क्लास मोनाडप्लस".
