नियतात्मक एल्गोरिथ्म

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

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

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

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

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

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

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

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

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

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

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

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

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

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

मरकरी

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

हास्केल

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

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

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

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

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

जावा

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

यह भी देखें

• रैंडमाइज्ड एल्गोरिथम