गणित और कंप्यूटर विज्ञान में, एक एल्गोरिदम AL-gə-ridh-əm) समस्याओं की एक वर्ग को हल करने का एक स्पष्ट विनिर्देश है। एल्गोरिदम गणना, डेटा प्रोसेसिंग और स्वचालित तर्क कार्यों को कर सकते हैं।

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

एल्गोरिदम की अवधारणा सदियों से अस्तित्व में है और अवधारणा के उपयोग को ग्रीक गणितज्ञों के रूप में वर्णित किया जा सकता है, उदाहरण के लिए एराटोस्टेनेस और यूक्लिड के एल्गोरिदम की चलनी; शब्द एल्गोरिदम स्वयं 9वीं शताब्दी के गणितज्ञ मुहम्मद इब्न मुसा अल’ख्वार्ज़्मी, लैटिनलाइज्ड ‘एल्गोरिटमी’ से निकला है। एल्गोरिदम की आधुनिक धारणा बनने का आंशिक औपचारिकरण 1 9 28 में डेविड हिल्बर्ट द्वारा उत्पन्न एंट्सचिडंग्सप्रोबलेम (“निर्णय समस्या”) को हल करने के प्रयासों के साथ शुरू हुआ। बाद में औपचारिकताओं को “प्रभावी गणना” या “प्रभावी विधि” को परिभाषित करने के प्रयासों के रूप में तैयार किया गया था। ; उन औपचारिकताओं में 1 9 30, 1 9 34 और 1 9 35 के गोडेल-हेब्रब्रांड-क्लेन रिकर्सिव फ़ंक्शंस, 1 9 36 का एलोनोजो चर्च का लैम्ब्डा कैलकुलेशन, 1 9 36 का एमिल पोस्ट का फॉर्मूलेशन 1 और 1 936-7 और 1 9 3 9 की एलन ट्यूरिंग की ट्यूरिंग मशीन शामिल थी।

शब्द-साधन
‘एल्गोरिदम’ शब्द की जड़ें मुहम्मद इब्न मुसा अल-ख्वारिज्मी के नाम को एल्गोरिज्म के पहले चरण में लैटिन करने में हैं। अल-ख्वारिजमी (फारसी: خوارزمی, सी। 780-850) एक फारसी गणितज्ञ, खगोलविद, भूगोलकार, और बगदाद में बुद्धि के सदन में विद्वान था, जिसका नाम ‘खवेयरज़म का मूल’ है, जो एक क्षेत्र था ग्रेटर ईरान और अब उजबेकिस्तान में है।

लगभग 825, अल-ख्वारिज्मी ने हिंदू-अरबी संख्या प्रणाली पर एक अरबी भाषा ग्रंथ लिखा, जिसका अनुवाद 12 वीं शताब्दी के दौरान लैटिन में अल्गोरिटमी डी न्यूमेरो इंडोरम शीर्षक के तहत किया गया था। इस शीर्षक का अर्थ है “भारतीयों की संख्या पर एल्गोरिटमी”, जहां “एल्गोरिटमी” अनुवादक का अल-ख्वारिज्मी के नाम का लैटिनलाइजेशन था। अल-ख्वारिज्मी मध्य युग के अंत में यूरोप में सबसे व्यापक रूप से पढ़ा गया गणितज्ञ था, मुख्य रूप से अपनी दूसरी किताबों, बीजगणित के माध्यम से। मध्ययुगीन लैटिन में, एल्गोरिज्म, अंग्रेजी ‘एल्गोरिज्म’, उनके नाम का भ्रष्टाचार, बस “दशमलव संख्या प्रणाली” का अर्थ था। 15 वीं शताब्दी में, ग्रीक शब्द ἀριθμός ‘संख्या’ (सीएफ ‘अंकगणित’) के प्रभाव में, लैटिन शब्द को एल्गोरिदमस में बदल दिया गया था, और संबंधित अंग्रेजी शब्द ‘एल्गोरिदम’ पहली बार 17 वीं शताब्दी में प्रमाणित किया गया था; आधुनिक ज्ञान 1 9वीं शताब्दी में पेश किया गया था।

अंग्रेजी में, इसका इस्तेमाल पहली बार 1230 में किया गया था और फिर 13 9 1 में चौसर द्वारा किया गया था। अंग्रेजी ने फ्रांसीसी शब्द अपनाया था, लेकिन 1 9वीं शताब्दी के उत्तरार्ध तक यह नहीं था कि “एल्गोरिदम” ने आधुनिक अंग्रेजी में इसका अर्थ लिया था।

इस शब्द का एक और प्रारंभिक उपयोग 1240 से है, जो कि अलेक्जेंड्रे डी विल्डियू द्वारा रचित कारमेन डी एल्गोरिज्मो नामक मैनुअल में है। यह इस प्रकार शुरू होता है:

हाइक एल्गोरिस्मस ने कहा कि क्वा / तालिबस इन्डोरम फ्यूमूर बिस क्विंक मूर्तियों में।

जो इस प्रकार अनुवाद करता है:

एल्गोरिज्म वह कला है जिसके द्वारा वर्तमान में हम उन भारतीय आंकड़ों का उपयोग करते हैं, जो संख्या दो गुना पांच है।

कविता कुछ सौ लाइन लंबी है और भारतीय पासा, या तालिबस इन्डोरम, या हिंदू अंकों की नई शैली के साथ गणना की कला को सारांशित करती है।

अनौपचारिक परिभाषा
“एल्गोरिदम” की परिभाषा पर विभिन्न दृष्टिकोणों की एक विस्तृत प्रस्तुति के लिए, एल्गोरिदम विशेषताएं देखें।
एक अनौपचारिक परिभाषा “नियमों का एक सेट हो सकता है जो निश्चित रूप से संचालन के अनुक्रम को परिभाषित करता है।” जिसमें सभी कंप्यूटर प्रोग्राम शामिल होंगे, जिनमें प्रोग्राम शामिल हैं जो संख्यात्मक गणना नहीं करते हैं। आम तौर पर, एक कार्यक्रम केवल एक एल्गोरिदम होता है यदि यह अंततः बंद हो जाता है।

एक एल्गोरिदम का प्रोटोटाइप उदाहरण यूक्लिडियन एल्गोरिदम है जो दो पूर्णांक के अधिकतम सामान्य विभाजक को निर्धारित करता है; एक उदाहरण (अन्य हैं) ऊपर फ्लोचार्ट द्वारा वर्णित है और बाद के खंड में एक उदाहरण के रूप में वर्णित है।

बूलोस, जेफरी और 1 9 74, 1 999 निम्नलिखित उद्धरण में शब्द का अनौपचारिक अर्थ प्रदान करते हैं:

कोई भी व्यक्ति पर्याप्त तेज़, या लंबे समय तक पर्याप्त नहीं लिख सकता है, या पर्याप्त छोटा † († “बिना सीमा के छोटे और छोटे … आप अणुओं पर, परमाणुओं पर, इलेक्ट्रॉनों पर लिखने की कोशिश करेंगे”) के सभी सदस्यों को सूचीबद्ध करने के लिए कुछ नोटेशन में, एक दूसरे के बाद, उनके नाम लिखकर अनगिनत रूप से अनंत सेट। लेकिन मनुष्य कुछ समान रूप से उपयोगी सेट कर सकते हैं, कुछ निश्चित रूप से अनंत सेट के मामले में: वे सेट के एनएच सदस्य को मनमाने ढंग से सीमित एन के लिए निर्धारित निर्देश दे सकते हैं। इस तरह के निर्देशों को स्पष्ट रूप से एक रूप में दिया जाना चाहिए, जिसमें एक कंप्यूटिंग मशीन, या एक ऐसे व्यक्ति द्वारा किया जा सकता है जो प्रतीकों पर केवल बहुत ही प्राथमिक संचालन करने में सक्षम है।

एक “अनगिनत अनंत सेट” वह व्यक्ति है जिसके तत्वों को पूर्णांक के साथ एक-एक-एक पत्राचार में रखा जा सकता है। इस प्रकार, बूलोस और जेफरी कह रहे हैं कि एक एल्गोरिदम एक ऐसी प्रक्रिया के लिए निर्देशों का तात्पर्य है जो “इनपुट” पूर्णांक या पूर्णांक से आउटपुट पूर्णांक बनाता है, सिद्धांत रूप में, मनमाने ढंग से बड़ा हो सकता है। इस प्रकार एक एल्गोरिदम एक बीजगणितीय समीकरण हो सकता है जैसे वाई = एम + एन – दो मनमाने ढंग से “इनपुट चर” एम और एन जो आउटपुट वाई उत्पन्न करते हैं। लेकिन विभिन्न लेखकों के विचार को परिभाषित करने के प्रयासों से संकेत मिलता है कि शब्द इस से अधिक मायने रखता है, कुछ के क्रम में (उदाहरण के लिए):

सटीक निर्देश (“कंप्यूटर” द्वारा समझा जाने वाली भाषा में) एक तेज़, कुशल, “अच्छी” प्रक्रिया के लिए जो “कंप्यूटर” (मशीन या मानव, आवश्यक आंतरिक रूप से निहित जानकारी और क्षमताओं से सुसज्जित) के “चाल” को निर्दिष्ट करता है , डीकोड, और उसके बाद मनमानी इनपुट पूर्णांक / प्रतीकों एम और एन, प्रतीकों + और = … और “प्रभावी” उत्पादन, “उचित” समय में, एक निर्दिष्ट स्थान पर और निर्दिष्ट प्रारूप में आउटपुट-पूर्णांक वाई उत्पन्न करते हैं।
एल्गोरिदम की अवधारणा का उपयोग निर्णायकता की धारणा को परिभाषित करने के लिए भी किया जाता है। यह धारणा यह समझाने के लिए केंद्रीय है कि कैसे औपचारिक प्रणाली सिद्धांतों और नियमों के एक छोटे से सेट से शुरू हो रही है। तर्क में, जिस समय एल्गोरिदम को पूरा करने की आवश्यकता होती है उसे माप नहीं किया जा सकता है, क्योंकि यह स्पष्ट रूप से हमारे पारंपरिक भौतिक आयाम से संबंधित नहीं है। ऐसी अनिश्चितताओं से, जो चल रहे काम को दर्शाता है, एल्गोरिदम की परिभाषा की अनुपलब्धता उत्पन्न करता है जो दोनों ठोस (कुछ अर्थों में) और शब्द के अमूर्त उपयोग के अनुरूप है।

औपचारिक
कंप्यूटर प्रक्रिया डेटा के तरीके के लिए एल्गोरिदम आवश्यक हैं। कई कंप्यूटर प्रोग्रामों में एल्गोरिदम होते हैं जो निर्दिष्ट कार्य करने के लिए कंप्यूटर को (विशिष्ट क्रम में) विशिष्ट निर्देशों का विवरण देते हैं, जैसे कर्मचारियों के पेचेक की गणना करना या छात्रों के रिपोर्ट कार्ड प्रिंट करना। इस प्रकार, एक एल्गोरिदम को संचालन का कोई अनुक्रम माना जा सकता है जिसे ट्यूरिंग-पूर्ण प्रणाली द्वारा अनुकरण किया जा सकता है। लेखकों ने इस थीसिस में जोर दिया मिन्स्की (1 9 67), सैवेज (1 9 87) और गुरेविच (2000):

मिन्स्की: “लेकिन हम ट्यूरिंग के साथ भी बनाए रखेंगे … कि किसी भी प्रक्रिया को” स्वाभाविक रूप से “प्रभावी कहा जा सकता है, वास्तव में एक (सरल) मशीन द्वारा महसूस किया जा सकता है। हालांकि यह चरम प्रतीत हो सकता है, तर्क … इसका पक्ष अस्वीकार करना मुश्किल है “।

गुरेविच: “… ट्यूरिंग की अनौपचारिक तर्क उनके सिद्धांत के पक्ष में एक मजबूत थीसिस को औचित्य देता है: प्रत्येक एल्गोरिदम को ट्यूरिंग मशीन द्वारा अनुकरण किया जा सकता है … Savage [1987] के अनुसार, एक एल्गोरिदम एक ट्यूरिंग मशीन द्वारा परिभाषित एक कम्प्यूटेशनल प्रक्रिया है” ।

आम तौर पर, जब एक एल्गोरिदम प्रोसेसिंग जानकारी से जुड़ा होता है, तो डेटा को आउटपुट डिवाइस से लिखे गए इनपुट स्रोत से पढ़ा जा सकता है और आगे की प्रोसेसिंग के लिए संग्रहीत किया जा सकता है। संग्रहीत डेटा को एल्गोरिदम प्रदर्शन करने वाली इकाई की आंतरिक स्थिति का हिस्सा माना जाता है। अभ्यास में, राज्य एक या अधिक डेटा संरचनाओं में संग्रहीत होता है।

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

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

अब तक, एल्गोरिदम के औपचारिकरण की इस चर्चा ने अनिवार्य प्रोग्रामिंग के परिसर को माना है। यह सबसे आम धारणा है, और यह अलग-अलग “यांत्रिक” साधनों में एक कार्य का वर्णन करने का प्रयास करती है। औपचारिक एल्गोरिदम की इस अवधारणा के लिए अद्वितीय असाइनमेंट ऑपरेशन है, एक चर के मान को सेट करना। यह एक स्क्रैचपैड के रूप में “स्मृति” के अंतर्ज्ञान से निकला है। इस तरह के असाइनमेंट के नीचे एक उदाहरण है।

एल्गोरिदम का गठन करने वाली कुछ वैकल्पिक धारणाओं के लिए कार्यात्मक प्रोग्रामिंग और तर्क प्रोग्रामिंग देखें।

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

विभिन्न प्रकार के प्रतिनिधित्व संभव हैं और कोई भी मशीन टेबल के अनुक्रम के रूप में दिए गए ट्यूरिंग मशीन प्रोग्राम को व्यक्त कर सकता है (परिमित-राज्य मशीन, राज्य संक्रमण तालिका और नियंत्रण तालिका पर और देखें), फ़्लोचार्ट्स और ड्रैकन-चार्ट के रूप में (अधिक देखें राज्य आरेख), या प्राथमिक मशीन कोड या असेंबली कोड के रूप में “चौगुनी के सेट” नामक एक रूप के रूप में (ट्यूरिंग मशीन पर और देखें)।

एल्गोरिदम के प्रतिनिधियों को ट्यूरिंग मशीन विवरण के तीन स्वीकृत स्तरों में वर्गीकृत किया जा सकता है:

1 उच्च स्तरीय विवरण
“… कार्यान्वयन के विवरण को अनदेखा करते हुए एक एल्गोरिदम का वर्णन करने के लिए गद्य। इस स्तर पर हमें यह उल्लेख करने की आवश्यकता नहीं है कि मशीन अपने टेप या सिर का प्रबंधन कैसे करती है।”
2 कार्यान्वयन विवरण
“… गद्य ट्यूरिंग मशीन अपने सिर का उपयोग करने के तरीके और जिस तरह से यह अपने टेप पर डेटा स्टोर करता है उसे परिभाषित करने के लिए प्रयोग किया जाता है। इस स्तर पर हम राज्यों या संक्रमण समारोह का विवरण नहीं देते हैं।”
3 औपचारिक विवरण
सबसे विस्तृत, “निम्नतम स्तर”, ट्यूरिंग मशीन की “स्टेट टेबल” देता है।
सभी तीन स्तरों में वर्णित सरल एल्गोरिदम “एम + एन जोड़ें” के उदाहरण के लिए, एल्गोरिदम # उदाहरण देखें।

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

कंप्यूटर एल्गोरिदम
कंप्यूटर सिस्टम में, एक एल्गोरिदम मूल रूप से सॉफ़्टवेयर डेवलपर्स द्वारा सॉफ़्टवेयर में लिखे गए तर्क का एक उदाहरण है जो लक्षित “लक्ष्य” कंप्यूटर (ओं) के लिए प्रभावी (संभवतः शून्य) इनपुट से आउटपुट उत्पन्न करने के लिए प्रभावी होता है। एक इष्टतम एल्गोरिदम, यहां तक ​​कि पुराने हार्डवेयर में भी चल रहा है, उसी उद्देश्य के लिए गैर-इष्टतम (उच्च समय जटिलता) एल्गोरिदम की तुलना में तेज़ परिणाम देगा, जो अधिक कुशल हार्डवेयर में चल रहा है; यही कारण है कि कंप्यूटर हार्डवेयर की तरह एल्गोरिदम, प्रौद्योगिकी माना जाता है।

“सुरुचिपूर्ण” (कॉम्पैक्ट) कार्यक्रम, “अच्छा” (तेज़) कार्यक्रम: “सादगी और लालित्य” की धारणा अनौपचारिक रूप से Knuth में दिखाई देती है और ठीक है चैतन में:

Knuth: “हम कुछ कम परिभाषित सौंदर्य भावना में अच्छा एल्गोरिदम चाहते हैं। एक मानदंड … एल्गोरिदम करने के लिए समय की लंबाई है .. अन्य मानदंड कंप्यूटर, इसकी सादगी और लालित्य के लिए एल्गोरिदम की अनुकूलता है , आदि”
चैतन: “एक कार्यक्रम ‘सुरुचिपूर्ण’ है, जिसके द्वारा मेरा मतलब है कि आउटपुट के उत्पादन के लिए यह सबसे छोटा संभव कार्यक्रम है जो”
चैतन ने अपनी परिभाषा को इसके साथ पूर्ववत किया: “मैं दिखाऊंगा कि आप यह साबित नहीं कर सकते कि एक कार्यक्रम ‘सुरुचिपूर्ण’ है – – इस तरह का सबूत हलिंग समस्या (ibid) को हल करेगा।

Related Post

एल्गोरिदम बनाम फ़ंक्शन एक एल्गोरिदम द्वारा गणना योग्य: किसी दिए गए फ़ंक्शन के लिए एकाधिक एल्गोरिदम मौजूद हो सकते हैं। प्रोग्रामर को उपलब्ध उपलब्ध निर्देश सेट का विस्तार किए बिना भी यह सच है। रोजर्स ने कहा कि “एल्गोरिदम की धारणा, यानी प्रक्रिया और एल्गोरिदम द्वारा संकलित फ़ंक्शन की धारणा के बीच अंतर करना महत्वपूर्ण है, यानी प्रक्रिया द्वारा उत्पन्न मैपिंग। एक ही कार्य में कई अलग-अलग एल्गोरिदम हो सकते हैं”।

दुर्भाग्यवश भलाई (गति) और लालित्य (कॉम्पैक्टनेस) के बीच एक व्यापार हो सकता है – एक सुरुचिपूर्ण कार्यक्रम एक कम सुरुचिपूर्ण से गणना को पूरा करने के लिए और अधिक कदम उठा सकता है। यूक्लिड के एल्गोरिदम का उपयोग करने वाला एक उदाहरण नीचे दिखाई देता है।

कंप्यूटर्स (और कंप्यूटर्स), गणना के मॉडल: एक कंप्यूटर (या मानव “कंप्यूटोर”) एक प्रतिबंधित प्रकार की मशीन है, एक “अलग निर्धारणात्मक यांत्रिक उपकरण” जो अंधाधुंध इसके निर्देशों का पालन करता है। मेलज़क और लैमबेक के आदिम मॉडल ने इस धारणा को चार तत्वों में कम कर दिया: (i) अलग, अलग-अलग स्थानों, (ii) अलग, अलग-अलग काउंटर (iii) एजेंट, और (iv) निर्देशों की एक सूची जो क्षमता की क्षमता से संबंधित प्रभावी हैं एजेंट।

एक एल्गोरिदम का सिमुलेशन: कंप्यूटर (कम्प्यूटर) भाषा: Knuth पाठक को सलाह देता है कि “एल्गोरिदम सीखने का सबसे अच्छा तरीका यह है कि इसे आजमाएं … तुरंत पेन और पेपर लें और उदाहरण के माध्यम से काम करें”। लेकिन वास्तविक चीज़ के सिमुलेशन या निष्पादन के बारे में क्या? प्रोग्रामर को एल्गोरिदम को उस भाषा में अनुवाद करना चाहिए जो सिम्युलेटर / कंप्यूटर / कंप्यूटर्स प्रभावी ढंग से निष्पादित कर सकता है। पत्थर इसका एक उदाहरण देता है: एक वर्गबद्ध समीकरण की जड़ों की गणना करते समय कंप्यूटर्स को पता होना चाहिए कि स्क्वायर रूट कैसे लेना है। यदि वे नहीं करते हैं, तो एल्गोरिदम प्रभावी होने के लिए, वर्ग रूट निकालने के लिए नियमों का एक सेट प्रदान करना होगा।

इसका मतलब है कि प्रोग्रामर को “भाषा” जाननी चाहिए जो लक्षित कंप्यूटिंग एजेंट (कंप्यूटर / कंप्यूटर्स) से संबंधित प्रभावी है।

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

औपचारिक बनाम औपचारिक
एल्गोरिदम का विश्लेषण और अध्ययन कंप्यूटर विज्ञान का एक अनुशासन है, और अक्सर एक विशिष्ट प्रोग्रामिंग भाषा या कार्यान्वयन के उपयोग के बिना संक्षेप में अभ्यास किया जाता है। इस अर्थ में, एल्गोरिदम विश्लेषण अन्य गणितीय विषयों जैसा दिखता है जिसमें यह एल्गोरिदम के अंतर्निहित गुणों पर केंद्रित है और किसी विशेष कार्यान्वयन के विनिर्देशों पर नहीं। आम तौर पर छद्म कोड का विश्लेषण विश्लेषण के लिए किया जाता है क्योंकि यह सबसे सरल और सबसे सामान्य प्रतिनिधित्व है। हालांकि, अंततः, अधिकांश एल्गोरिदम आमतौर पर विशेष हार्डवेयर / सॉफ्टवेयर प्लेटफॉर्म पर लागू होते हैं और अंततः उनके एल्गोरिदमिक दक्षता को वास्तविक कोड का उपयोग करके परीक्षण में डाल दिया जाता है। “एक बंद” समस्या के समाधान के लिए, किसी विशेष एल्गोरिदम की दक्षता के महत्वपूर्ण परिणाम नहीं हो सकते हैं (जब तक कि एन बहुत बड़ा न हो) लेकिन तेजी से संवादात्मक, वाणिज्यिक या लंबे जीवन के वैज्ञानिक उपयोग के लिए डिज़ाइन किए गए एल्गोरिदम के लिए यह महत्वपूर्ण हो सकता है। छोटे एन से बड़े एन तक स्केलिंग अक्सर अक्षम एल्गोरिदम का खुलासा करता है जो अन्यथा सौम्य होते हैं।

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

वर्गीकरण
एल्गोरिदम वर्गीकृत करने के कई तरीके हैं, प्रत्येक अपनी योग्यता के साथ।

कार्यान्वयन के द्वारा
एल्गोरिदम वर्गीकृत करने का एक तरीका कार्यान्वयन का मतलब है।

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

तार्किक
एक एल्गोरिदम को नियंत्रित तार्किक कटौती के रूप में देखा जा सकता है। इस धारणा को व्यक्त किया जा सकता है: एल्गोरिदम = तर्क + नियंत्रण। तर्क घटक सिद्धांतों को व्यक्त करता है जिनका उपयोग गणना में किया जा सकता है और नियंत्रण घटक निर्धारित करता है कि किस तरह से कटौती सिद्धांतों पर लागू होती है। यह तर्क प्रोग्रामिंग प्रतिमान के लिए आधार है। शुद्ध तर्क प्रोग्रामिंग भाषाओं में नियंत्रण घटक तय किया जाता है और केवल तर्क घटक की आपूर्ति करके एल्गोरिदम निर्दिष्ट किए जाते हैं। इस दृष्टिकोण की अपील सुरुचिपूर्ण अर्थशास्त्र है: सिद्धांतों में परिवर्तन एल्गोरिदम में एक अच्छी तरह से परिभाषित परिवर्तन है।

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

निर्धारक या गैर निर्धारिती
निर्धारक एल्गोरिदम एल्गोरिदम के प्रत्येक चरण में सटीक निर्णय के साथ समस्या का समाधान करते हैं जबकि गैर-निर्धारिती एल्गोरिदम अनुमान लगाने के माध्यम से समस्याओं को हल करते हैं हालांकि सामान्य अनुमानों को हेरिस्टिक्स के उपयोग के माध्यम से अधिक सटीक बनाया जाता है।

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

क्वांटम एल्गोरिदम
वे क्वांटम गणना के यथार्थवादी मॉडल पर चलते हैं। शब्द आमतौर पर उन एल्गोरिदम के लिए उपयोग किया जाता है जो स्वाभाविक रूप से क्वांटम लगते हैं, या क्वांटम कंप्यूशन जैसे क्वांटम सुपरपोजिशन या क्वांटम उलझन की कुछ आवश्यक विशेषता का उपयोग करते हैं।

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

ब्रूट-बल या संपूर्ण खोज
यह देखने के लिए हर संभव समाधान की कोशिश करने का बेवकूफ तरीका है कि कौन सा सर्वोत्तम है।

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

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

जटिलता में कमी
इस तकनीक में इसे एक बेहतर समस्या को हल करने में एक कठिन समस्या को हल करना शामिल है जिसके लिए हमारे पास (उम्मीद है) asymptotically इष्टतम एल्गोरिदम है। लक्ष्य एक कम करने वाले एल्गोरिदम को ढूंढना है जिसका जटिलता परिणामस्वरूप कम एल्गोरिदम का प्रभुत्व नहीं है। उदाहरण के लिए, एक अनुरक्षित सूची में औसत खोजने के लिए एक चयन एल्गोरिदम में सबसे पहले सूची (महंगी भाग) को क्रमबद्ध करना और फिर क्रमबद्ध सूची (सस्ता भाग) में मध्य तत्व को खींचना शामिल है। इस तकनीक को ट्रांसफॉर्म और जीत के रूप में भी जाना जाता है।

अनुकूलन की समस्याएं
अनुकूलन समस्याओं के लिए एल्गोरिदम का एक और विशिष्ट वर्गीकरण है; ऐसी समस्याओं के लिए एक एल्गोरिदम ऊपर वर्णित सामान्य श्रेणियों में से एक या अधिक में निम्नानुसार हो सकता है:

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

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

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

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

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

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

जटिलता से
एल्गोरिदम को उनके इनपुट आकार की तुलना में पूरा करने की आवश्यकता के समय तक वर्गीकृत किया जा सकता है:

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

निरंतर एल्गोरिदम
“एल्गोरिदम” शब्द पर लागू होने पर विशेषण “निरंतर” का अर्थ हो सकता है:

डेटा पर चलने वाला एक एल्गोरिदम जो निरंतर मात्रा का प्रतिनिधित्व करता है, भले ही यह डेटा अलग-अलग अनुमानों द्वारा दर्शाया गया हो – ऐसे एल्गोरिदम का अध्ययन संख्यात्मक विश्लेषण में किया जाता है; या
एक एल्गोरिदम एक विभेदक समीकरण के रूप में जो डेटा पर लगातार चल रहा है, एनालॉग कंप्यूटर पर चल रहा है।

Share