एल्गोरिथम गणित

एल्गोरिथ्म, व्यवस्थित प्रक्रिया जो एक सीमित संख्या में चरणों का उत्पादन करती है - एक प्रश्न का उत्तर या किसी समस्या का समाधान। यह नाम 9 वीं शताब्दी के मुस्लिम गणितज्ञ अल-ख्वारिज़मी के अंकगणितीय ग्रंथ "अल-ख़्वारिज़मी कॉन्करिंग द हिंदू आर्ट ऑफ़ रेकनिंग" के लैटिन अनुवाद, अल्गोरिटमी डी सुमेरो इंडोरम से निकला है।

कंप्यूटर विज्ञान: एल्गोरिदम और जटिलता

एक एल्गोरिथ्म एक अच्छी तरह से परिभाषित कम्प्यूटेशनल समस्या को हल करने के लिए एक विशिष्ट प्रक्रिया है। एल्गोरिदम का विकास और विश्लेषण मौलिक है

।

प्रश्नों या समस्याओं के लिए केवल मामलों या मूल्यों के एक सीमित सेट के साथ एक एल्गोरिथ्म हमेशा मौजूद होता है (कम से कम सिद्धांत रूप में); इसमें उत्तरों के मानों की तालिका होती है। सामान्य तौर पर, प्रश्नों या समस्याओं का जवाब देने के लिए ऐसी कोई तुच्छ प्रक्रिया नहीं है, जिसमें विचार करने के लिए अनंत संख्या में मामले या मान हों, जैसे "क्या प्राकृतिक संख्या (1, 2, 3,।) एक अभाज्य है?" या "प्राकृतिक संख्याओं a और b का सबसे बड़ा सामान्य विभाजक क्या है?" इन सवालों में से पहला एक वर्ग के अंतर्गत आता है जिसे निर्णायक कहा जाता है; एक एल्गोरिथ्म जो हाँ या कोई जवाब नहीं देता है उसे निर्णय प्रक्रिया कहा जाता है। दूसरा प्रश्न एक वर्ग से संबंधित है जिसे कम्प्यूटेबल कहा जाता है; एक एल्गोरिथ्म जो एक विशिष्ट संख्या के उत्तर की ओर जाता है, एक संगणना प्रक्रिया कहलाती है।

ऐसे कई अनंत प्रश्नों के लिए एल्गोरिदम मौजूद हैं; यूक्लिड के तत्वों को 300 बीसी के बारे में प्रकाशित किया गया था, जिसमें दो प्राकृतिक संख्याओं का सबसे बड़ा सामान्य भाजक खोजने के लिए एक था। प्रत्येक प्राथमिक विद्यालय के छात्र को लंबे समय तक विभाजन में ड्रिल किया जाता है, जो प्रश्न के लिए एक एल्गोरिथ्म है "एक प्राकृतिक संख्या को एक अन्य प्राकृतिक संख्या बी द्वारा विभाजित करने पर, भागफल और शेष क्या हैं?" इस कम्प्यूटेशनल प्रक्रिया का उपयोग निर्णायक प्रश्न के उत्तर की ओर जाता है "क्या बी विभाजन करता है?" (उत्तर हाँ है यदि शेष शून्य है)। इन एल्गोरिदम का बार-बार आवेदन अंततः निर्णायक सवाल "एक प्रधानमंत्री है?" (जवाब है अगर कोई 1 के अलावा किसी भी छोटी प्राकृतिक संख्या से विभाज्य है तो कोई बात नहीं)।

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