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

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

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

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

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

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

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

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

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

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

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

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

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

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

भाषाओं में नियतत्ववाद श्रेणियां

बुध

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

हास्केल

हास्केल कई तंत्र प्रदान करता है:

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

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

जैसा कि Standard ML , OCaml और Scala (प्रोग्रामिंग भाषा) में देखा गया है

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

जावा

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

यह भी देखें

• यादृच्छिक एल्गोरिदम