कलन विधि

"कलन विधि (एल्गोरिथ्म)" redirects here. For कंप्यूटर विज्ञान का उपक्षेत्र, see कलन विधि (एल्गोरिथ्म) का विश्लेषण.

For other uses, see कलन विधि (disambiguation).

एक कलन विधि (एल्गोरिथ्म) (यूक्लिड कलन विधि (एल्गोरिथ्म)) का फ्लोचार्ट ए और बी नाम के स्थानों में दो नंबरों ए और बी के सबसे बड़े सामान्य भाजक (जी.सी.डी.) की गणना के लिए कलन विधि (एल्गोरिथ्म) दो छोरों में क्रमिक घटाव द्वारा आगे बढ़ता है: यदि परीक्षण बी yes ए पैदावार हां या सही है(अधिक सटीक रूप से, स्थान B में संख्या B स्थान A में संख्या A से अधिक या बराबर है A) तब, कलन विधि (एल्गोरिथ्म) B ← B - A को निर्दिष्ट करता है (जिसका अर्थ है संख्या B - A पुराने B को प्रतिस्थापित करता है)।इसी तरह, यदि a> b, तो a - a - B. प्रक्रिया समाप्त हो जाती है जब (b की सामग्री) 0 है, g.c.d.ए में (कलन विधि (एल्गोरिथ्म) स्कॉट 2009: 13 से प्राप्त कलन विधि (एल्गोरिथ्म); प्रतीकों और ड्राइंग शैली से तौसवोरथे 1977 से)।

नोट जी से एडा लवलेस का आरेख, पहला प्रकाशित कंप्यूटर कलन विधि (एल्गोरिथ्म)

गणित और कंप्यूटर विज्ञान में, कलन विधि (एल्गोरिथ्म) (/ˈælɡərɪðəm/ (listen)) परिशुद्ध निर्देशों का एक सीमित क्रम है, इसका उपयोग विशिष्ट समस्याओं को हल करने या गणना करने के लिए किया जाता है। गणना और डाटा का विश्लेषण करने के लिए कलन विधि (एल्गोरिदम) का उपयोग विनिर्देशों के रूप में किया जाता है। अच्छी तरह तैयार की गई कलन विधि (एल्गोरिथ्म) स्वचालित कटौती कर सकती हैं (स्वचालित तर्क के रूप में संदर्भित) और हम विभिन्न मार्गों (स्वचालित निर्णय लेने के रूप में संदर्भित) के माध्यम से कोड निष्पादन की प्रक्रिया को आसानी से हल करने के लिए गणितीय और तार्किक परीक्षणों का उपयोग करते हैं। मशीनों के वर्णनकर्ता के रूप में मानवीय विशेषताओं का उपयोग अलंकारिक तरीकों से पहले से ही एलन ट्यूरिंग द्वारा शब्दों के साथ किया जा चुका था जैसे "स्मृति", "खोज" और "प्रोत्साहन"।

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

एक प्रभावी विधि के रूप में, एक कलन विधि (एल्गोरिथ्म) को सीमित स्थान और समय के भीतर, और किसी फ़ंक्शन की गणना करने के लिए औपचारिक भाषा के रूप में अच्छी तरह से परिभाषित किया जा सकता है।

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

इतिहास

कलन विधि (एल्गोरिथ्म) की अवधारणा प्राचीन काल से मौजूद है। अंकगणितीय कलन विधि (एल्गोरिथ्म), जैसे कि एक विभाजन कलन विधि (एल्गोरिथ्म), का उपयोग प्राचीन बेबीलोन के गणितज्ञों द्वारा c. 2500 ईसा पूर्व और मिस्र के गणितज्ञों द्वारा c. 1550 ई.पू में किया गया था। ग्रीक गणितज्ञों ने बाद में 240 ईसा पूर्व में एराटोस्थनीज की छलनी में अभाज्य संख्याओं को खोजने के लिए कलन विधि (एल्गोरिथ्म) का इस्तेमाल किया, और यूक्लिडियन एल्गोरिथम ने दो संख्याओं में सबसे बड़ा सामान्य भाजक खोजने के लिए कलन विधि (एल्गोरिथ्म) का इस्तेमाल किया। 9वीं शताब्दी में अल-किंडी जैसे अरबी गणितज्ञों ने आवृत्ति विश्लेषण के आधार पर कोड-ब्रेकिंग के लिए क्रिप्टोग्राफ़िक कलन विधि (एल्गोरिथ्म) का उपयोग किया।

एल्गोरिथम शब्द 9वीं शताब्दी के फारसी गणितज्ञ मुहम्मद इब्न मूसा अल-ख्वारिज्मी (Muḥammad ibn Mūsā al-Khwārizmī) के नाम से लिया गया है। जिसका निस्बा (nisba) (ख़्वारज़्म (Khwarazm) से उसकी पहचान) को अल्गोरितमी (अरबी फ़ारसी (Arabized Persian) الخوارزمی c. 780-850) के रूप में लैटिनकृत किया गया था। मुहम्मद इब्न मूसा अल-ख्वारिज्मी एक गणितज्ञ, खगोलशास्त्री, भूगोलवेत्ता और बगदाद में हाउस ऑफ विजडम के विद्वान थे। जिनके नाम का अर्थ है 'ख़्वारज़्म का मूल निवासी', एक ऐसा क्षेत्र जो ग्रेटर ईरान का हिस्सा था और अब उज़्बेकिस्तान में है।

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

भारतीय गणित मुख्यतः एल्गोरिथम था। कलन विधि (एल्गोरिथ्म) जो भारतीय गणितीय परंपरा के प्रतिनिधि हैं, प्राचीन शुलबसूत्रों से लेकर केरल स्कूल के मध्यकालीन ग्रंथों तक हैं।

अंग्रेजी में कलन विधि (एल्गोरिथम) शब्द का प्रयोग सबसे पहले लगभग 1230 में और फिर चौसर ने 1391 में किया था। अंग्रेजी ने फ्रांसीसी शब्द को अपनाया, लेकिन 19वीं शताब्दी के अंत तक "कलन विधि (एल्गोरिथ्म)" का अर्थ आधुनिक अंग्रेजी में नहीं था।

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

"इस एल्गोरिथम को वर्तमान कला कहा जाता है, जिसमें / हम ऐसे भारतीयों का आनंद लेते हैं जिनके पास दो बार पांच अंक हैं।"

जो अनुवाद करता है:

कलन विधि (एल्गोरिथम) वह कला है जिसके द्वारा वर्तमान में हम उन भारतीय आकृतियों का उपयोग करते हैं, जिनकी संख्या दो गुणा पांच है।

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

कलन विधि (एल्गोरिथम) की आधुनिक अवधारणा का आंशिक औपचारिककरण 1928 में डेविड हिल्बर्ट द्वारा प्रस्तुत निर्णय समस्या को हल करने के प्रयासों के साथ शुरू हुआ। बाद में औपचारिकताओं को "प्रभावी गणना" या "प्रभावी विधि" को परिभाषित करने के प्रयासों के रूप में तैयार किया गया था। उन औपचारिकताओं में 1930, 1934 और 1935 के गोडेल हेरब्रांड क्लेन पुनरावर्ती कार्य, 1936 का अलोंजो चर्च का लैम्ब्डा कैलकुलस, 1936 का एमिल पोस्ट का फॉर्म्युलेशन 1, और 1936-37 और 1939 की एलन ट्यूरिंग की ट्यूरिंग मशीनें शामिल थीं।

अनौपचारिक परिभाषा

अनौपचारिक परिभाषा कुछ इस प्रकार हो सकती है- "नियमों का एक सेट जो संचालन के अनुक्रम को सटीक रूप से परिभाषित करता है", जिसमें सभी कंप्यूटर प्रोग्राम शामिल होंगे (कार्यक्रमों सहित जो संख्यात्मक गणना नहीं करते हैं), और (उदाहरण के लिए) कोई निर्धारित नौकरशाही प्रक्रिया या कुक बुक रेसिपी इसके एक उदाहरण हो सकते हैं।

सामान्य तौर पर, एक प्रोग्राम केवल एक एल्गोरिथम होता है यदि यह अंततः बंद हो जाता है।

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

बूलोस, जेफरी और 1974, 1999 (Boolos, Jeffrey & 1974, 1999) निम्नलिखित उद्धरण में "कलन विधि (एल्गोरिथ्म)" शब्द का अनौपचारिक अर्थ प्रदान करते हैं: निम्नलिखित उद्धरण में शब्द कलन विधि (एल्गोरिथ्म) का एक अनौपचारिक अर्थ प्रदान करें:

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

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

जैसे कि y = m + n (यानी, दो मनमाना "इनपुट चर (वैरिएबल)" m और n जो आउटपुट y उत्पन्न करते हैं)

लेकिन इस धारणा को परिभाषित करने के लिए विभिन्न लेखकों के प्रयासों से संकेत मिलता है कि इस शब्द का अर्थ इससे कहीं अधिक है, कुछ के क्रम में (अतिरिक्त उदाहरण के लिए):

एक तेज़, कुशल, "अच्छी" प्रक्रिया के लिए सटीक निर्देश ("कंप्यूटर" द्वारा समझी जाने वाली भाषा में) जो "कंप्यूटर" की "चाल" (मशीन या मानव, आवश्यक आंतरिक रूप से निहित जानकारी और क्षमताओं से लैस) को खोजने, डिकोड करने के लिए निर्दिष्ट करता है,और फिर अपनी तरह इनपुट पूर्णांक/प्रतीक m और n, प्रतीकों + और = ... और "प्रभावी रूप से" उत्पादन, "उचित" समय में, आउटपुट-पूर्णांक y को एक निर्दिष्ट स्थान पर और एक निर्दिष्ट प्रारूप में संसाधित करता हैं।

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

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

औपचारिककरण

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

मिन्स्की: "लेकिन हम ट्यूरिंग के साथ भी बनाए रखेंगे" कि कोई भी प्रक्रिया जिसे "स्वाभाविक रूप से" प्रभावी कहा जा सकता है, वास्तव में एक (सरल) मशीन द्वारा महसूस की जा सकती है। हालांकि यह अतिवादी लग सकता है, इसके पक्ष में तर्कों का खंडन करना कठिन है"। गुरेविच: "... ट्यूरिंग की थीसिस के पक्ष में अनौपचारिक तर्क एक मजबूत थीसिस को सही ठहराता है: सैवेज [1987] के अनुसार प्रत्येक कलन विधि (एल्गोरिथ्म) को ट्यूरिंग मशीन द्वारा अनुकरण किया जा सकता है, एक कलन विधि (एल्गोरिथ्म) एक ट्यूरिंग मशीन द्वारा परिभाषित एक कम्प्यूटेशनल प्रक्रिया है।"

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

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

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

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

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

कलन विधि (एल्गोरिथ्म) क्या होता है, इसकी कुछ वैकल्पिक अवधारणाओं के लिए, कार्यात्मक प्रोग्रामिंग और तर्क प्रोग्रामिंग देखें।

कलन विधि (एल्गोरिथ्म) व्यक्त करना

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

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

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

1 उच्च-स्तरीय विवरण

"... एक कलन विधि (एल्गोरिथ्म) का वर्णन करने के लिए गद्य, कार्यान्वयन विवरण की अनदेखी। इस स्तर पर, हमें यह उल्लेख करने की आवश्यकता नहीं है कि मशीन अपने टेप या सिर का प्रबंधन कैसे करती है।"

2 कार्यान्वयन विवरण

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

3 औपचारिक विवरण

सबसे विस्तृत, "निम्नतम स्तर", ट्यूरिंग मशीन की "स्टेट टेबल" देता है। तीनों स्तरों में वर्णित सरल एल्गोरिथम "एम+एन जोड़ें (m+n) " के उदाहरण के लिए, उदाहरण देखें।

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

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

कलन विधि (एल्गोरिथ्म) के विकास में विशिष्ट कदम:

1. समस्या की परिभाषा
2. एक मॉडल का विकास
3. कलन विधि (एल्गोरिथ्म) का विनिर्देशन
4. एक कलन विधि (एल्गोरिथ्म) डिजाइन करना
5. कलन विधि (एल्गोरिथ्म) की शुद्धता की जाँच करना
6. कलन विधि (एल्गोरिथ्म) का विश्लेषण
7. कलन विधि (एल्गोरिथ्म) का कार्यान्वयन
8. कार्यक्रम परीक्षण
9. प्रलेखन तैयारी

कंप्यूटर कलन विधि (एल्गोरिथ्म)

7400 चिप

कैनोनिकल बोहम-जैकोपिनी संरचनाओं के फ्लोचार्ट उदाहरण: अनुक्रम (पृष्ठ को नीचे उतरने वाले आयताकार), जबकि-डू और इफ-तब-एल्स।तीन संरचनाएं आदिम सशर्त गोटो से बनी हैं (IF test THEN GOTO step xxx, हीरे के रूप में दिखाया गया है), बिना शर्त गोटो (आयत), विभिन्न असाइनमेंट ऑपरेटर (आयत), और पड़ाव (आयत)।असाइनमेंट-ब्लॉक के अंदर इन संरचनाओं के घोंसले के कारण जटिल आरेख (सीऍफ़ (cf) टॉउसवर्थ (Tausworthe) 1977: 100, 114) होते हैं।

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

नुथ: "... हम कुछ शिथिल परिभाषित सौंदर्य बोध में अच्छे कलन विधि (एल्गोरिथ्म) चाहते हैं। एक मानदंड ... एल्गोरिथम को निष्पादित करने में लगने वाले समय की लंबाई है ....अन्य मानदंड कंप्यूटर के लिए कलन विधि (एल्गोरिथ्म) की अनुकूलन क्षमता, इसकी सादगी और लालित्य, आदि हैं।"

चैतिन: "... एक कार्यक्रम 'सुरुचिपूर्ण' है, जिसके द्वारा मेरा मतलब है कि यह आउटपुट के उत्पादन के लिए सबसे छोटा संभव कार्यक्रम है जो यह करता है"

चैतिन ने अपनी परिभाषा इस प्रकार प्रस्तुत की:

"मैं दिखाऊंगा कि आप यह साबित नहीं कर सकते कि एक कार्यक्रम 'सुरुचिपूर्ण' है" ऐसा प्रमाण हॉल्टिंग समस्या (आईबिड ibid) को हल करेगा।

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

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

कंप्यूटर (और कंप्यूटर), गणना के मॉडल:

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

मिंस्की ने अपने "वेरी सिंपल बेसेस फॉर कम्प्यूटेबिलिटी" में लैंबेक के "एबेकस" प्रारूप (मॉडल) की अधिक अनुकूल भिन्नता का वर्णन किया है। मिंस्की की मशीन क्रमिक रूप से अपने पांच (या छह, यह निर्भर करता है कि कोई कैसे गिनता है) निर्देशों के माध्यम से आगे बढ़ता है जब तक कि कोई सशर्त यदि तब गोटो या बिना शर्त गोटो क्रम से प्रोग्राम प्रवाह को बदलता है। हाल्ट के अलावा, मिंस्की की मशीन में तीन असाइनमेंट (प्रतिस्थापन, प्रतिस्थापन) संचालन शामिल हैं: जीरो (जैसे 0: L ← 0 द्वारा प्रतिस्थापित स्थान की सामग्री), उत्तराधिकारी (जैसे L ← L+1), और घटते क्रम में (जैसे L ← L − 1 ) शायद ही किसी प्रोग्रामर को इतने सीमित निर्देश सेट के साथ "कोड" लिखना चाहिए। लेकिन मिन्स्की दिखाता है (जैसा कि मेल्ज़ाक और लैंबेक करते हैं) कि उसकी मशीन ट्यूरिंग केवल चार सामान्य प्रकार के निर्देशों के साथ पूर्ण है: सशर्त गोटो, बिना शर्त गोटो, असाइनमेंट/प्रतिस्थापन/प्रतिस्थापन, और पड़ाव। हालांकि, ट्यूरिंग-पूर्णता के लिए कुछ अलग असाइनमेंट निर्देश (जैसे डिक्रीमेंट, इंक्रीमेंट, और मिन्स्की मशीन के लिए शून्य/साफ/खाली) भी आवश्यक हैं; उनका सटीक विनिर्देश कुछ हद तक डिजाइनर पर निर्भर है। बिना शर्त गोटो एक सुविधा है; इसे एक समर्पित स्थान को शून्य पर प्रारंभ करके बनाया जा सकता है जैसे निर्देश " Z 0 "; उसके बाद निर्देश If Z=0(IF Z=0) तब गोटू एक्सएक्सएक्स (xxx) बिना शर्त है।

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

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

संरचित प्रोग्रामिंग, विहित संरचनाएं: चर्च-ट्यूरिंग थीसिस के अनुसार, किसी भी कलन विधि (एल्गोरिथ्म) की गणना एक मॉडल द्वारा की जा सकती है जिसे ट्यूरिंग पूर्ण कहा जाता है, और मिन्स्की के प्रदर्शनों के अनुसार, ट्यूरिंग पूर्णता के लिए केवल चार निर्देश प्रकारों की आवश्यकता होती है-सशर्त गोटो, बिना शर्त गोटो, असाइनमेंट, एचएएलटी। केमेनी और कर्ट्ज़ ने देखा कि, बिना शर्त (गो टू) GOTO और सशर्त (इफ-देन गो टू) IF-THEN GOTO के "अनुशासनहीन" उपयोग के परिणामस्वरूप "स्पेगेटी कोड" हो सकता है, एक प्रोग्रामर केवल इन निर्देशों का उपयोग करके संरचित प्रोग्राम लिख सकता है; दूसरी ओर "एक संरचित भाषा में बुरी तरह से संरचित कार्यक्रमों को लिखना भी संभव है, और बहुत कठिन नहीं है"। टॉसवर्थ ने तीन बोहम-जैकोपिनी विहित संरचनाओं को बढ़ाया: सिक्वेंस (SEQUENCE), इफ-देन-एल्स (IF-THEN-ELSE), और वाइल-डू (WHILE-DO), दो और के साथ: डू-वाइल (DO-WHILE) और केस (CASE)। एक संरचित कार्यक्रम का एक अतिरिक्त लाभ यह है कि यह गणितीय प्रेरण का उपयोग करके शुद्धता के प्रमाण के लिए खुद को उधार देता है।

विहित फ़्लोचार्ट (कैनोनिकल फ्लोचार्ट) प्रतीक: फ़्लोचार्ट नामक ग्राफिकल सहयोगी, एक कलन विधि (एल्गोरिथ्म) (और एक का एक कंप्यूटर प्रोग्राम) का वर्णन और दस्तावेज करने का एक तरीका प्रदान करता है। मिन्स्की मशीन के प्रोग्राम फ़्लो की तरह, फ़्लोचार्ट हमेशा एक पृष्ठ के शीर्ष पर शुरू होता है और नीचे की ओर बढ़ता है। इसके प्राथमिक प्रतीक केवल चार हैं: निर्देशित तीर प्रोग्राम प्रवाह दिखा रहा है, आयत (अनुक्रम, GOTO), Diamond IF-THEN-ELSE, और Dot (और OR-टाई)। बोहम जैकोपिनी विहित संरचनाएं (कैनोनिकल फ्लोचार्ट) इन आदिम आकृतियों से बनी हैं। उप संरचनाएं आयतों में "घोंसला" कर सकती हैं, लेकिन केवल तभी जब अधिरचना से एकल निकास होता है। विहित संरचनाओं (कैनोनिकल फ्लोचार्ट) के निर्माण के लिए प्रतीकों और उनके उपयोग को आरेख में दिखाया गया है।

उदाहरण

कलन विधि (एल्गोरिथ्म) उदाहरण

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

उच्च स्तरीय विवरण:

1. यदि समुच्चय में कोई संख्या नहीं है तो कोई उच्चतम संख्या नहीं है।
2. मान लें कि सेट में पहली संख्या सेट में सबसे बड़ी संख्या है।
3. सेट में प्रत्येक शेष संख्या के लिए:
4. यदि यह संख्या वर्तमान सबसे बड़ी संख्या से बड़ी है, तो इस संख्या को समुच्चय की सबसे बड़ी संख्या मानें।
5. जब पुनरावृति के लिए सेट में कोई संख्या नहीं बची है, तो वर्तमान सबसे बड़ी संख्या को सेट की सबसे बड़ी संख्या मानें।

(अर्ध-) औपचारिक विवरण: गद्य में लिखा गया लेकिन कंप्यूटर प्रोग्राम की उच्च स्तरीय भाषा के बहुत करीब, स्यूडोकोड या पिजिन कोड में एल्गोरिथम की अधिक औपचारिक कोडिंग निम्नलिखित है:

Algorithm Largest Number

Input: संख्याओं की एक सूची L

Output: सूची में सबसे बड़ी संख्या L.

If L.size = 0 return null largest ← L[0] for each item in L, do If item > largest, then largest ← item return largest

• "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
• "return" terminates the algorithm and outputs the following value.

यूक्लिड की कलन विधि (एल्गोरिथ्म)

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

टी.एल. से यूक्लिड के कलन विधि (एल्गोरिथ्म) का उदाहरण-माप।हीथ (1908), अधिक विस्तार के साथ।यूक्लिड एक तीसरे माप से परे नहीं जाता है और कोई संख्यात्मक उदाहरण नहीं देता है।निकोमैचस 49 और 21 का उदाहरण देता है: मैं अधिक से कम घटाता हूं;28 छोड़ दिया गया है;तो फिर से मैं इसे उसी 21 से घटाता हूं (इसके लिए संभव है);7 बचा है;मैं इसे 21 से घटाता हूं, 14 छोड़ दिया जाता है;जिसमें से मैं फिर से 7 घटाना (इसके लिए संभव है);7 को छोड़ दिया गया है, लेकिन 7 को 7. से घटाया नहीं जा सकता है। हीथ टिप्पणियाँ कि अंतिम वाक्यांश उत्सुक है, लेकिन इसका अर्थ स्पष्ट रूप से पर्याप्त है, साथ ही 'एक और एक ही संख्या पर' समाप्त होने के बारे में वाक्यांश का अर्थ भी।(हीथ 1908: 300)।

यूक्लिड ने इस समस्या को इस प्रकार प्रस्तुत किया: "दिए गए दो संख्याएँ जो एक दूसरे के लिए अभाज्य नहीं हैं, उनका सबसे बड़ा सामान्य उपाय खोजने के लिए"। वह परिभाषित करता है "एक संख्या [होने के लिए] इकाइयों से बना एक भीड़": एक गिनती संख्या, एक सकारात्मक पूर्णांक जिसमें शून्य शामिल नहीं है। "माप" करने के लिए एक छोटी माप लंबाई s क्रमिक रूप से (q गुना) लंबी लंबाई l के साथ रखना है जब तक कि शेष भाग r छोटी लंबाई s से कम न हो। आधुनिक शब्दों में, शेष r = l - q×s, q भागफल है, या शेष r "मापांक" है, विभाजन के बाद बचा हुआ पूर्णांक भिन्नात्मक भाग है।

यूक्लिड की विधि के सफल होने के लिए, प्रारंभिक लंबाई को दो आवश्यकताओं को पूरा करना चाहिए: (i) लंबाई शून्य नहीं होनी चाहिए, और (ii) घटाव "उचित" होना चाहिए; यानी, एक परीक्षण की गारंटी होनी चाहिए कि दो संख्याओं में से छोटी संख्या को बड़े से घटाया जाता है (या दोनों बराबर हो सकते हैं ताकि उनका घटाव शून्य हो)।

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

1599 और 650 के लिए सबसे बड़ी आम भाजक को खोजने के लिए यूक्लिड के कलन विधि (एल्गोरिथ्म) की एक चित्रमय अभिव्यक्ति।<syntaxhighighlight lang = पाठ हाइलाइट = 1,5> 1599 = 650 × 2 + 299 650 = 299 × 2 + 52 299 = 52 × 5 + 39 52 = 39 × 1 + 13 39 = 13 × 3 + 0 </syntaxhighlight>

यूक्लिड के कलन विधि (एल्गोरिथ्म) के लिए कंप्यूटर भाषा

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

• किसी स्थान को अपर केस अक्षर (अक्षरों) द्वारा दर्शाया जाता है, जैसे S, A, आदि।
• किसी स्थान में अलग-अलग मात्रा (संख्या) लोअर केस अक्षरों में लिखी जाती है और (आमतौर पर) स्थान के नाम से जुड़ी होती है। उदाहरण के लिए, प्रारंभ में स्थान L में संख्या l = 3009 हो सकती है।

"यूक्लिड के कलन विधि (एल्गोरिथ्म) के लिए एक सुरुचिपूर्ण कार्यक्रम "

IneLegant एक घटाव-आधारित शेष-लूप के साथ कलन विधि (एल्गोरिथ्म) के Knuth के संस्करण का अनुवाद है, जो विभाजन के अपने उपयोग (या एक मापांक निर्देश) के उपयोग की जगह लेता है।नुथ 1973 से व्युत्पन्न: 2-4।दो नंबरों के आधार पर inelegant G.C.D की गणना कर सकता है।सुरुचिपूर्ण से कम चरणों में।

"सुरुचिपूर्ण" कलन विधि (एल्गोरिथ्म) के नुथ के संस्करण का एक अनुवाद है जिसमें एक घटाव आधारित शेष लूप है जो उसके विभाजन (या "मॉड्यूलस" निर्देश) के उपयोग की जगह लेता है। नुथ 1973: 2-4 से व्युत्पन्न। दो संख्याओं के आधार पर "सुरुचिपूर्ण" जी. सी. डी. (g.c.d.) की गणना कर सकता है। "सुरुचिपूर्ण" से कम चरणों में निम्नलिखित कलन विधि (एल्गोरिथ्म) को नुथ के यूक्लिड और निकोमाचस के चार चरण संस्करण के रूप में तैयार किया गया है, लेकिन शेष को खोजने के लिए विभाजन का उपयोग करने के बजाय, यह शेष लंबाई r से छोटी लंबाई s के क्रमिक घटाव का उपयोग करता है जब तक कि r s से कम न हो। बोल्डफेस में दिखाया गया उच्च-स्तरीय विवरण, नुथ 1973: 2–4 से अनुकूलित है:

INPUT:

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:                  R ← L1

E0: [Ensure r ≥ s.]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
IF R > S THEN
the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
GOTO step 7
ELSE
swap the contents of R and S.
4 L ← R (this first step is redundant, but is useful for later discussion).
5 R ← S                                                          6 S ← L

E1: [Find remainder]: जब तक R में शेष लंबाई r, S में छोटी लंबाई s से कम न हो, बार-बार S में माप संख्या s को R में शेष लंबाई r से घटाएं।

7 IF S > R THEN
done measuring so
GOTO 10
ELSE
measure again,
8 R ← R − S
9 [Remainder-loop]:                                                           GOTO 7.

E2: [Is the remainder zero?]: या तो (i) अंतिम उपाय सटीक था, R में शेषफल शून्य है, और प्रोग्राम रुक सकता है, या (ii) एल्गोरिथम जारी रहना चाहिए: अंतिम माप ने R में शेषफल S में मापने की संख्या से कम छोड़ दिया।

10 IF R = 0 THEN
done so
GOTO step 15
ELSE                                                                     CONTINUE TO step 11,

E3: [Interchange s and r]: यूक्लिड के कलन विधि (एल्गोरिथ्म) का नट। शेष r का उपयोग यह मापने के लिए करें कि पहले छोटी संख्या s क्या थी; एल एक अस्थायी स्थान के रूप में कार्य करता है।

11 L ← R
12 R ← S
13 S ← L
14 [Repeat the measuring process]:                                           GOTO 7

OUTPUT:

15 [Done. S contains the greatest common divisor]:                          PRINT S

DONE:

16 HALT, END, STOP.

यूक्लिड के कलन विधि (एल्गोरिथ्म) के लिए एक सुरुचिपूर्ण कार्यक्रम

यूक्लिड के एल्गोरिथम के निम्नलिखित संस्करण के लिए केवल छह मुख्य निर्देशों की आवश्यकता है जो "इनलेगेंट" द्वारा तेरह को करने के लिए आवश्यक हैं; इससे भी बदतर, "सुरुचिपूर्ण" के लिए अधिक प्रकार के निर्देशों की आवश्यकता होती है। "सुरुचिपूर्ण" का फ़्लोचार्ट इस लेख के शीर्ष पर पाया जा सकता है। (असंरचित) मूल भाषा में, चरणों को क्रमांकित किया जाता है, और निर्देश LET [ ] = [ ] असाइनमेंट निर्देश का प्रतीक है। <syntaxhighighlight lang = cbmbas>

   5 REM Euclid's algorithm for greatest common divisor                                                  6 PRINT "Type two integers greater than 0"
  10 INPUT A,B
  20 IF B=0 THEN GOTO 80
  30 IF A > B THEN GOTO 60
  40 LET B=B-A
  50 GOTO 20
  60 LET A=A-B
  70 GOTO 20
  80 PRINT A                                                                          90 END

"एलिगेंट" कैसे काम करता है: बाहरी "यूक्लिड लूप" के स्थान पर, "एलिगेंट" दो "को-लूप" के बीच आगे और पीछे शिफ्ट हो जाता है, A> B लूप जो A ← A - B, और A B ≤ A लूप की गणना करता है और जो B ← B - A की गणना करता है। यह एक साथ काम करता है क्योंकि, जब अंत में मिन्यूएंड M सबट्रेंड S से कम या उसके बराबर होता है (अंतर = मिन्यूएंड - सबट्रेंड), तो ऐसी स्थिति में मिन्यूएंड s बन सकता है (नई माप लंबाई) और सबट्रेंड R (मापी जाने वाली लंबाई) बन सकता है; दूसरे शब्दों में घटाएं जाने का यह "अर्थ" आपस में बदल सकता है।

निम्नलिखित संस्करण का उपयोग C-परिवार की प्रोग्रामिंग भाषाओं के साथ किया जा सकता है: C-परिवार से प्रोग्रामिंग भाषाएं:

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B){
     A=abs(A);
     B=abs(B);
     while (B!=0){
          while (A>B) A=A-B;
          B=B-A;
     }
     return A;                                                                   }

यूक्लिड एल्गोरिथम का परीक्षण

क्या कोई एल्गोरिथम वही करता है जो उसका लेखक उससे करना चाहता है? कुछ परीक्षण मामले आमतौर पर मुख्य कार्यक्षमता में कुछ विश्वास देते हैं। लेकिन परीक्षण पर्याप्त नहीं हैं। परीक्षण मामलों के लिए, एक स्रोत 3009 और 884 का उपयोग करता है। नुथ ने 40902, 24140 का सुझाव दिया।

एक और दिलचस्प मामला दो अपेक्षाकृत अभाज्य संख्याएँ 14157 और 5950 है। लेकिन "असाधारण मामलों" की पहचान की जानी चाहिए और उनका परीक्षण किया जाना चाहिए। क्या R > S, S > R, R = S होने पर "इनलीगेंट" ठीक से प्रदर्शन करेगा? "सुरुचिपूर्ण" के लिए डिट्टो: B> A, A> B, A = B? (हाँ सभी को)। क्या होता है जब एक संख्या शून्य होती है, दोनों संख्याएँ शून्य होती हैं? ("सुरुचिपूर्ण" सभी मामलों में हमेशा के लिए गणना करता है; "सुरुचिपूर्ण" हमेशा के लिए गणना करता है जब A = 0.) यदि ऋणात्मक संख्याएँ दर्ज की जाती हैं तो क्या होता है? भिन्नात्मक संख्याएँ? यदि इनपुट नंबर, यानी कलन विधि (एल्गोरिथ्म)/प्रोग्राम द्वारा गणना किए गए फ़ंक्शन का डोमेन शून्य सहित केवल सकारात्मक पूर्णांक शामिल करना है, तो शून्य पर विफलताएं इंगित करती हैं कि कलन विधि (एल्गोरिथ्म) (और प्रोग्राम जो इसे तुरंत चालू करता है) इसके बजाय आंशिक कार्य है एक कुल समारोह। अपवादों के कारण एक उल्लेखनीय विफलता एरियन 5 फ्लाइट 501 रॉकेट विफलता (4 जून, 1996) है।

गणितीय प्रेरण के उपयोग से कार्यक्रम की शुद्धता का प्रमाण: नुथ यूक्लिड के एल्गोरिथम के "विस्तारित" संस्करण में गणितीय प्रेरण के अनुप्रयोग को प्रदर्शित करता है, और वह "किसी भी एल्गोरिथम की वैधता को साबित करने के लिए लागू एक सामान्य विधि" का प्रस्ताव करता है। टॉसवर्थ का प्रस्ताव है कि किसी कार्यक्रम की जटिलता का माप उसके शुद्धता प्रमाण की लंबाई हो।

यूक्लिड कलन विधि (एल्गोरिथ्म) को मापने और सुधारना

लालित्य (कॉम्पैक्टनेस) बनाम अच्छाई (गति): केवल छह मुख्य निर्देशों के साथ, तेरह निर्देशों में "सुरुचिपूर्ण" की तुलना में "सुरुचिपूर्ण" स्पष्ट विजेता है। हालांकि, "सुरुचिपूर्ण" तेज है (यह कम चरणों में एचएएलटी पर पहुंचता है)। एल्गोरिथम विश्लेषण इंगित करता है कि ऐसा क्यों है: "सुरुचिपूर्ण" प्रत्येक घटाव लूप में दो सशर्त परीक्षण करता है, जबकि "सुरुचिपूर्ण" केवल एक ही करता है। चूंकि एल्गोरिथम (आमतौर पर) को कई लूप की आवश्यकता होती है, औसतन "B = 0?" करने में बहुत समय बर्बाद होता है। परीक्षण जो शेष की गणना के बाद ही आवश्यक है।

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

पाँच चरणों को समाप्त करके "सुरुचिपूर्ण" की कॉम्पैक्टनेस में सुधार किया जा सकता है। लेकिन चैतिन ने साबित कर दिया कि एक कलन विधि (एल्गोरिथ्म) को संकुचित करना एक सामान्यीकृत कलन विधि (एल्गोरिथ्म) द्वारा स्वचालित नहीं किया जा सकता है; बल्कि, यह केवल अनुमान से ही किया जा सकता है; यानी, संपूर्ण खोज (व्यस्त बीवर में पाए जाने वाले उदाहरण), परीक्षण और त्रुटि, चतुराई, अंतर्दृष्टि, आगमनात्मक तर्क का अनुप्रयोग, आदि। ध्यान दें कि चरण 4, 5 और 6 चरण 11, 12 और 13 में दोहराए गए हैं। "सुरुचिपूर्ण" के साथ तुलना एक संकेत प्रदान करती है कि चरण 2 और 3 के साथ इन चरणों को समाप्त किया जा सकता है। यह मूल निर्देशों की संख्या को तेरह से घटाकर आठ कर देता है, जो इसे नौ चरणों में "सुरुचिपूर्ण" से "अधिक सुरुचिपूर्ण" बनाता है।

"B=0?" को स्थानांतरित करके "सुरुचिपूर्ण" की गति में सुधार किया जा सकता है। दो घटाव छोरों के बाहर परीक्षण करें। यह परिवर्तन तीन निर्देशों (B = 0?, A = 0?, GOTO) को जोड़ने के लिए कहता है। अब "सुरुचिपूर्ण" उदाहरण संख्याओं की तेज़ी से गणना करता है; क्या किसी दिए गए A, B और R के लिए हमेशा ऐसा ही होता है, S को विस्तृत विश्लेषण की आवश्यकता होगी।

एल्गोरिथम विश्लेषण

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

अलग-अलग कलन विधि (एल्गोरिथ्म) एक ही कार्य को निर्देशों के एक अलग सेट के साथ कम या अधिक समय, स्थान, या दूसरों की तुलना में 'प्रयास' में पूरा कर सकते हैं। उदाहरण के लिए, एक द्विआधारी खोज कलन विधि (एल्गोरिथ्म) (लागत O(log n) के साथ) एक अनुक्रमिक खोज (लागत O(n)) से बेहतर प्रदर्शन करता है जब क्रमबद्ध सूचियों या सरणियों पर तालिका लुकअप के लिए उपयोग किया जाता है।

औपचारिक बनाम अनुभवजन्य

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

अनुभवजन्य परीक्षण उपयोगी है क्योंकि यह अप्रत्याशित अंतःक्रियाओं को उजागर कर सकता है जो प्रदर्शन को प्रभावित करते हैं। प्रोग्राम ऑप्टिमाइजेशन (Programming Optimization) के बाद किसी एल्गोरिथम में संभावित सुधारों से पहले/बाद में तुलना करने के लिए बेंचमार्क का उपयोग किया जा सकता है। अनुभवजन्य परीक्षण औपचारिक विश्लेषण की जगह नहीं ले सकते, हालांकि, और निष्पक्ष तरीके से प्रदर्शन करने के लिए तुच्छ नहीं हैं।

निष्पादन दक्षता

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

वर्गीकरण

कलन विधि (एल्गोरिथ्म) को वर्गीकृत करने के कई तरीके हैं, जिनमें से प्रत्येक की अपनी खूबियां हैं।

कार्यान्वयन द्वारा

कलन विधि (एल्गोरिथ्म) को वर्गीकृत करने का एक तरीका कार्यान्वयन के माध्यम से है।

int gcd(int A, int B) { if (B == 0) return A; else if (A > B) return gcd(A-B,B); else return gcd(A,B-A); }

उपरोक्त फ़्लोचार्ट (above flowchart) से यूक्लिड के कलन विधि (एल्गोरिथ्म) का पुनरावर्ती सी (C) कार्यान्वयन

प्रत्यावर्तन

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

तार्किक

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

धारावाहिक, समानांतर या वितरित

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

नियतात्मक या गैर-नियतात्मक

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

सटीक या अनुमानित

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

मात्रा का कलन विधि (एल्गोरिथ्म)

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

डिजाइन प्रतिमान द्वारा

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

ब्रूट-फोर्स या एग्जॉस्टिव सर्च

यह देखने के लिए कि कौन सा सबसे अच्छा है, हर संभव समाधान की कोशिश करने का यह भोला तरीका है।

विभक्त करो और अधिकार करो (डिवाइड एंड कौंकर)

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

खोज और गणना

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

यादृच्छिक कलन विधि (एल्गोरिथ्म)

इस तरह के कलन विधि (एल्गोरिथ्म) कुछ विकल्प बेतरतीब ढंग से (या छद्म यादृच्छिक रूप से) बनाते हैं। वे समस्याओं के अनुमानित समाधान खोजने में बहुत उपयोगी हो सकते हैं जहां सटीक समाधान खोजना अव्यावहारिक हो सकता है (नीचे अनुमानी विधि देखें)। इनमें से कुछ समस्याओं के लिए, यह ज्ञात है कि सबसे तेज़ सन्निकटन में कुछ यादृच्छिकता शामिल होनी चाहिए। क्या बहुपद समय जटिलता वाले यादृच्छिक कलन विधि (एल्गोरिथ्म) कुछ समस्याओं के लिए सबसे तेज़ कलन विधि (एल्गोरिथ्म) हो सकते हैं, यह एक खुला प्रश्न है जिसे पी बनाम एनपी समस्या के रूप में जाना जाता है। ऐसे कलन विधि (एल्गोरिथ्म) के दो बड़े वर्ग हैं:

1. मोंटे कार्लो कलन विधि (एल्गोरिथ्म) उच्च संभावना के साथ एक सही उत्तर देता है। उदाहरणतयः आरपी (RP) इनका उपवर्ग है जो बहुपद समय में चलता है।
2. लास वेगास कलन विधि (एल्गोरिथ्म) हमेशा सही उत्तर देता है, लेकिन उनके चलने का समय केवल संभाव्य रूप से बाध्य है, जैसे जेडपीपी (ZPP)।

जटिलता में कमी

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

बैक ट्रैकिंग

इस दृष्टिकोण में, कई समाधान क्रमिक रूप से बनाए जाते हैं और छोड़ दिए जाते हैं जब यह निर्धारित किया जाता है कि वे एक वैध पूर्ण समाधान की ओर नहीं ले जा सकते हैं।

अनुकूलन समस्याएं

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

रैखिक प्रोग्रामिंग

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

गतिशील प्रोग्रामिंग

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

लालची (ग्रीडी) विधि

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

हेयुरिस्टिक विधि

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

अध्ययन के क्षेत्र द्वारा

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

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

जटिलता द्वारा

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

• निरंतर समय: यदि इनपुट आकार की परवाह किए बिना कलन विधि (एल्गोरिथ्म) द्वारा आवश्यक समय समान है। उदा. एक सरणी तत्व तक पहुंच।
• लघुगणक समय: यदि समय इनपुट आकार का लघुगणकीय कार्य है। उदा. द्विआधारी खोज कलन विधि (एल्गोरिथ्म)।
• रैखिक समय: यदि समय इनपुट आकार के समानुपाती होता है। उदा. एक सूची का ट्रैवर्स।
• बहुपद समय: यदि समय इनपुट आकार की शक्ति है। उदा. बबल सॉर्ट कलन विधि (एल्गोरिथ्म) में द्विघात समय जटिलता है।
• घातीय समय: यदि समय इनपुट आकार का एक घातीय कार्य है। उदा. पाशविक बल खोज।

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

निरंतर कलन विधि (एल्गोरिथ्म)

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

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

विधिक कारक

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

इसके अतिरिक्त, कुछ क्रिप्टोग्राफ़िक कलन विधि (एल्गोरिथ्म) में निर्यात प्रतिबंध हैं (क्रिप्टोग्राफी का निर्यात देखें)।

इतिहास: कलन विधि (एल्गोरिथ्म) की धारणा का विकास

प्राचीन निकट पूर्व

कलन विधि (एल्गोरिथ्म) का सबसे पहला प्रमाण प्राचीन मेसोपोटामिया (आधुनिक इराक) के बेबीलोन के गणित में मिलता है। बगदाद के पास शुरुप्पक में मिली एक सुमेरियन मिट्टी की गोली और लगभग 2500 ईसा पूर्व की है, जो सबसे पहले विभाजन कलन विधि (एल्गोरिथ्म) का वर्णन करती है। हम्मुराबी राजवंश के दौरान लगभग 1800-1600 ईसा पूर्व, बेबीलोन की मिट्टी की गोलियों ने सूत्रों की गणना के लिए कलन विधि (एल्गोरिथ्म) का वर्णन किया। एल्गोरिथम का उपयोग बेबीलोन के खगोल विज्ञान में भी किया जाता था। बेबीलोन की मिट्टी की गोलियां महत्वपूर्ण खगोलीय घटनाओं के समय और स्थान की गणना करने के लिए कलन विधि (एल्गोरिथ्म) प्रक्रियाओं का वर्णन और उपयोग करती हैं।

अंकगणित के लिए एल्गोरिथम प्राचीन मिस्र के गणित में भी पाए जाते हैं, जो लगभग 1550 ई.पू. बाद में प्राचीन हेलेनिस्टिक गणित (Hellenistic mathematics) में कलन विधि (एल्गोरिथ्म) का उपयोग किया गया। इरेटोस्थनीज की छलनी(Sieve of Eratosthenes) के दो उदाहरण हैं, जिसका वर्णन निकोमाचस (Nicomachus) द्वारा अंकगणित के परिचय में किया गया था, यूक्लिडियन एल्गोरिथम (Introduction to Arithmetic), जिसे पहली बार यूक्लिड के तत्वों (सी. 300 ईसा पूर्व) में वर्णित किया गया था

असतत और अलग -अलग प्रतीक

मिलान-चिह्न: अपने झुंड पर नज़र रखने के लिए, उनके अनाज के बोरे और उनके पैसे पूर्वजों ने मिलान किया: पत्थरों या डंडों पर खरोंच के निशान या मिट्टी में असतत प्रतीक बनाना। बेबीलोन और मिस्र के द्वारा चिह्नों और प्रतीकों के प्रयोग से, अंततः रोमन अंकों और अबेकस (डिलसन, पृष्ठ 16–41) का विकास हुआ। ट्यूरिंग मशीन और पोस्ट ट्यूरिंग मशीन कंप्यूटेशंस में प्रयुक्त यूनरी अंक प्रणाली अंकगणित में टैली मार्क्स प्रमुखता से दिखाई देते हैं।

संख्याओं के लिए स्थान धारकों के रूप में प्रतीकों का हेरफेर: बीजगणित

मुहम्मद इब्न मूसा अल-ख्वारिज्मी, एक फारसी गणितज्ञ, उन्होंने 9वीं शताब्दी में अल-जबर लिखा था। शब्द "एल्गोरिज्म" और "कलन विधि (एल्गोरिथ्म)" अल ख्वारिज्मी नाम से प्राप्त हुए हैं, जबकि "बीजगणित" शब्द अल-जबर पुस्तक से लिया गया है। यूरोप में, शब्द "कलन विधि (एल्गोरिथ्म)" मूल रूप से नियमों और तकनीकों के सेट को संदर्भित करने के लिए इस्तेमाल किया गया था जिसका उपयोग अल-ख्वारिज्मी द्वारा बीजीय समीकरणों को हल करने के लिए किया जाता है, बाद में नियमों या तकनीकों के किसी भी सेट को संदर्भित करने के लिए सामान्यीकृत होने से पहले। यह अंततः लीबनिज़ की कैलकुलस रेशियोसिनेटर (सी. 1680) की धारणा में परिणत हुआ:

अपने समय से डेढ़ सौ आगे, लाइबनिज ने तर्क के बीजगणित का प्रस्ताव रखा, एक बीजगणित जो तार्किक अवधारणाओं को तरीके से हेरफेर करने के नियमों को निर्दिष्ट करेगा कि साधारण बीजगणित संख्याओं में हेर-फेर के नियमों को निर्दिष्ट करता है.

क्रिप्टोग्राफिक कलन विधि (एल्गोरिथ्म)

एन्क्रिप्टेड कोड को समझने के लिए पहला क्रिप्टोग्राफ़िक कलन विधि (एल्गोरिथ्म) इसे 9वीं शताब्दी के अरब गणितज्ञ अल किंडी द्वारा ए मैनुस्क्रिप्ट ऑन डिक्रिप्शन क्रिप्टोग्राफ़िक संदेशों में विकसित किया गया था। उन्होंने आवृत्ति विश्लेषण द्वारा क्रिप्टोएनालिसिस का पहला विवरण दिया, जो सबसे पुराना कोडब्रेकिंग कलन विधि (एल्गोरिथ्म) था।।

असतत स्थितिों के साथ यांत्रिक विरोधाभास

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

लॉजिकल मशीन 1870 स्टेनली जेवन्स का "तार्किक अबेकस" और "तार्किक मशीन": तकनीकी समस्या बूलियन समीकरणों को कम करने की थी जब एक रूप में प्रस्तुत किया जाता है जिसे अब कर्णघ मानचित्र के रूप में जाना जाता है। जेवन्स (1880) पहले एक साधारण "अबेकस" का वर्णन करता है, जिसमें "पिनों से सुसज्जित लकड़ी की पर्चियां" बनाई गई हैं। ताकि [तार्किक] संयोजनों के किसी भी भाग या वर्ग को यंत्रवत् निकाला जा सके हाल ही में, हालांकि, मैंने सिस्टम को पूरी तरह से यांत्रिक रूप में कम कर दिया है, और इस प्रकार अनुमान की पूरी अप्रत्यक्ष प्रक्रिया को एक तार्किक मशीन कहा जा सकता है" उनकी मशीन "कुछ चलने योग्य लकड़ी की छड़" से सुसज्जित थी और "पैर में 21 चाबियां हैं जैसे पियानो इत्यादि..."। इस मशीन के साथ वह एक "न्यायवाद या किसी अन्य सरल तार्किक तर्क" का विश्लेषण कर सकता था।

इस मशीन को उन्होंने 1870 में रॉयल सोसाइटी के फेलो के सामने प्रदर्शित किया था। एक अन्य तर्कशास्त्री जॉन वेन ने, हालांकि, अपने 1881 के प्रतीकात्मक तर्क में, इस प्रयास के लिए पीलिया से आंखें फेर लीं: "मेरे पास स्वयं की रुचि या महत्व का कोई उच्च अनुमान नहीं है तार्किक मशीन किसे कहते हैं?... मुझे ऐसा नहीं लगता है कि वर्तमान में ज्ञात या खोजे जाने की संभावना वाली कोई भी युक्ति वास्तव में तार्किक मशीनों के नाम के लायक है"; एल्गोरिथम अभिलक्षणन पर और देखें। लेकिन आगे नहीं बढ़ने के लिए उन्होंने भी "कुछ हद तक समान योजना प्रस्तुत की, मुझे लगता है, प्रो. जेवॉन के अबेकस के लिए... और फिर, प्रो। जेवन्स की तार्किक मशीन के अनुरूप, निम्नलिखित अंतर्विरोध का वर्णन किया जा सकता है। मैं इसे केवल एक तार्किक आरेख मशीन कहना पसंद करता हूं... लेकिन मुझे लगता है कि यह पूरी तरह से वह सब कुछ कर सकता है जिसकी किसी तार्किक मशीन से तर्कसंगत रूप से अपेक्षा की जा सकती है"।

जैक्वार्ड लूम, होलेरिथ पंच कार्ड, टेलीग्राफी और टेलीफोनी विद्युत यांत्रिक रिले: बेल और नेवेल (1971) इंगित करते हैं कि जैक्वार्ड लूम (1801), हॉलेरिथ कार्ड्स (पंच कार्ड, 1887) के अग्रदूत, और "टेलीफोन स्विचिंग प्रौद्योगिकियां" पहले कंप्यूटर के विकास के लिए अग्रणी एक पेड़ की जड़ें थीं। 19वीं सदी के मध्य तक टेलीग्राफ, टेलीफोन का अग्रदूत, दुनिया भर में उपयोग में था, अक्षरों का असतत और अलग-अलग एन्कोडिंग "डॉट्स और डैश" के रूप में एक सामान्य ध्वनि है। 19वीं सदी के अंत तक टिकर टेप (c. 1870s) उपयोग में था, जैसा कि 1890 की अमेरिकी जनगणना में होलेरिथ कार्ड का उपयोग था। इसके बाद टेलीप्रिंटर (c. 1910) आया, जिसमें टेप पर बॉडॉट कोड के छिद्रित कागज का उपयोग किया गया था।

जॉर्ज स्टिबिट्ज़ (1937) के काम के पीछे इलेक्ट्रोमैकेनिकल रिले (1835 का आविष्कार) के टेलीफोन स्विचिंग नेटवर्क थे, डिजिटल एडिंग डिवाइस के आविष्कारक। जब उन्होंने बेल लेबोरेटरीज में काम किया, तो उन्होंने गियर के साथ मैकेनिकल कैलकुलेटर के "बोझ" उपयोग को देखा। 1937 की एक शाम वे अपने विचार को परखने के इरादे से घर गए... जब छेड़खानी खत्म हुई, स्टिबिट्ज़ ने एक बाइनरी एडिंग डिवाइस का निर्माण किया था"।

गणितज्ञ मार्टिन डेविस इलेक्ट्रोमैकेनिकल रिले के विशेष महत्व को देखते हैं (इसके दो "बाइनरी स्टेट्स" खुले और बंद हैं):

यह केवल 1930 के दशक में विद्युत रिले का उपयोग करने वाले इलेक्ट्रोमैकेनिकल कैलकुलेटर के विकास के साथ था, बैबेज ने जिस दायरे की कल्पना की थी, उसमें मशीनों का निर्माण किया गया था।"

गणित 19 वीं शताब्दी के दौरान 20 वीं शताब्दी के मध्य तक

प्रतीक और नियम के अनुसार तेजी से उत्तराधिकार के रूप में, जॉर्ज बूले (1847, 1854), गॉटलोब फ्रेगे (1879) और ग्यूसेप पीनो (1888-1889) के गणित ने अंकगणित को नियमों द्वारा हेरफेर किए गए प्रतीकों के अनुक्रम को कम कर दिया। पिनो के अंकगणित के सिद्धांत के अनुसार, एक नई विधि द्वारा प्रस्तुत (1888) "एक प्रतीकात्मक भाषा में गणित के स्वयंसिद्धीकरण का पहला प्रयास" था।

लेकिन हाइजेनोर्ट फ्रेज (1879) को यह यश देता है: फ्रेज "शायद तर्क में लिखा गया अब तक का सबसे महत्वपूर्ण एकल कार्य है। जिसमें हम एक "'सूत्र भाषा' देखते हैं, यह एक लिंगुआ चरित्र है, विशेष प्रतीकों के साथ लिखी गई भाषा, "शुद्ध विचार के लिए", जो कि अलंकारिक अलंकरणों से मुक्त है जिसका निर्माण विशिष्ट प्रतीकों से किया गया है जिन्हें निश्चित नियमों के अनुसार हेरफेर किया जाता है"। अल्फ्रेड नॉर्थ व्हाइटहेड और बर्ट्रेंड रसेल ने अपने प्रिंसिपिया मैथेमेटिका (1910-1913) में फ्रेज के काम को और सरल और प्रवर्धित किया।

विरोधाभास के कारण एक ही समय में साहित्य में कई परेशान करने वाले विरोधाभास दिखाई दिए, विशेष रूप से, बुराली-फोर्टी विरोधाभास (1897), रसेल विरोधाभास (1902–03), और रिचर्ड विरोधाभास। परिणामी विचारों ने कर्ट गोडेल के पेपर (1931) को जन्म दिया वह विशेष रूप से झूठे विरोधाभासों का हवाला देता है जो संख्याओं के पुनरावर्तन के नियमों को पूरी तरह से कम कर देता है।

प्रभावी परिकलन क्षमता के अनुसार 1928 में हिल्बर्ट द्वारा सटीक रूप से परिभाषित इंटशेडुंगस समस्या (Entscheidungs problem) को हल करने के प्रयास में, गणितज्ञों ने सबसे पहले "प्रभावी विधि" या "प्रभावी गणना" या "प्रभावी गणना" (यानी, एक गणना जो सफल होगी) से क्या मतलब था, यह परिभाषित करने के बारे में निर्धारित किया। तेजी से उत्तराधिकार में निम्नलिखित दिखाई दिया: अलोंजो चर्च, स्टीफन क्लेन और जेबी रॉसर के -कैलकुलस जैक्स हेरब्रांड (cf. गोडेल के प्रिंसटन लेक्चर ऑफ 1934) और क्लेन द्वारा बाद के सरलीकरण के सुझावों पर गोडेल के काम से "सामान्य रिकर्सन" की एक अच्छी तरह से सम्मानित परिभाषा है। चर्च का प्रमाण है कि इंटशेडुंगस समस्या (Entscheidungs problem) असाध्य था, एमिल पोस्ट की प्रभावी गणना की परिभाषा एक कार्यकर्ता के रूप में बिना दिमाग के निर्देशों की एक सूची के बाद कमरे के एक क्रम के माध्यम से बाएं या दाएं स्थानांतरित करने के लिए और जब वहाँ या तो एक कागज को चिह्नित करें या मिटा दें या कागज का निरीक्षण करें और अगले निर्देश के बारे में हाँ या ना में निर्णय लें। एलन ट्यूरिंग का सबूत है कि इंटशेडुंगस समस्या (Entscheidungs problem) उनकी "एक स्वचालित मशीन" के उपयोग से हल करने योग्य नहीं था। लगभग पोस्ट के "फॉर्मूलेशन" के समान, जे बार्कले रॉसर की "एक मशीन" के संदर्भ में "प्रभावी विधि" की परिभाषा। क्लेन का "चर्च थीसिस" के अग्रदूत का प्रस्ताव जिसे उन्होंने "थीसिस " कहा, और कुछ साल बाद क्लेन ने अपनी थीसिस का नाम बदलकर "चर्च ट्यूरिंग थीसिस" और "ट्यूरिंग की थीसिस" का प्रस्ताव रखा।

एमिल पोस्ट (1936) और एलन ट्यूरिंग (1936–37, 1939)

एमिल पोस्ट (1936) ने "कंप्यूटर" (मनुष्य) की क्रियाओं का वर्णन इस प्रकार किया है:

"... दो अवधारणाएं शामिल हैं: एक प्रतीक स्थान का जिसमें समस्या से उत्तर की ओर ले जाने का कार्य किया जाना है, और दिशाओं का एक निश्चित अपरिवर्तनीय सेट।

उसका प्रतीक स्थान होगा।

"रिक्त स्थान या बक्से का दो-तरफा अनंत क्रम... समस्या हल करने वाला या कार्यकर्ता इस प्रतीक स्थान में स्थानांतरित होने और काम करने में सक्षम है, जिसमें होने में सक्षम है, और एक समय में एक बॉक्स में काम कर रहा है.... एक बॉक्स में दो संभावित शर्तों को स्वीकार करना है, यानी खाली या अचिह्नित होना और उसमें एक ही निशान होना, वर्टिकल स्ट्रोक कहते हैं।

"एक बॉक्स को सिंगल आउट किया जाना है और शुरुआती बिंदु कहा जाता है।... एक विशिष्ट समस्या को सांकेतिक रूप में एक सीमित संख्या में बक्से [यानी, INPUT] द्वारा एक स्ट्रोक के साथ चिह्नित किया जाना है। इसी तरह, उत्तर [यानी, OUTPUT] चिह्नित बक्सों के इस तरह के विन्यास द्वारा प्रतीकात्मक रूप में दिया जाना है ...

"एक सामान्य समस्या पर लागू निर्देशों का एक सेट प्रत्येक विशिष्ट समस्या पर लागू होने पर एक नियतात्मक प्रक्रिया स्थापित करता है। यह प्रक्रिया तभी समाप्त होती है जब प्रकार (C) की दिशा की बात आती है। [यानी, STOP]" पोस्ट-ट्यूरिंग मशीन पर और देखे

बेलेचले पार्क में एलन ट्यूरिंग की प्रतिमा

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

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

"कम्प्यूटिंग आम तौर पर कागज पर कुछ प्रतीकों को लिखकर किया जाता है। हम मान सकते हैं कि यह पेपर एक बच्चे की अंकगणित की किताब की तरह वर्गों में बांटा गया है... तब मुझे लगता है कि गणना एक आयामी कागज पर की जाती है, यानी, वर्गों में विभाजित एक टेप पर। मैं यह भी मानूंगा कि मुद्रित किए जा सकने वाले प्रतीकों की संख्या सीमित है...

"किसी भी क्षण कंप्यूटर का व्यवहार उसके द्वारा देखे जा रहे प्रतीकों से निर्धारित होता है, और उस समय उसकी "मन की स्थिति"। हम मान सकते हैं कि प्रतीकों या वर्गों की संख्या के लिए एक बाध्य बी है जिसे कंप्यूटर एक पल में देख सकता है। यदि वह और अधिक अवलोकन करना चाहता है, तो उसे क्रमिक प्रेक्षणों का उपयोग करना चाहिए। हम यह भी मानेंगे कि मन की अवस्थाओं की संख्या जिसे ध्यान में रखा जाना चाहिए वह सीमित है ... "आइए हम कल्पना करें कि कंप्यूटर द्वारा किए गए कार्यों को 'सरल संचालन' में विभाजित किया जाना है। जो इतने प्राथमिक हैं कि उन्हें और विभाजित करने की कल्पना करना आसान नहीं है।"

ट्यूरिंग की कमी से निम्नलिखित पैदावार होती है:

"सरल संचालन में इसलिए शामिल होना चाहिए:

"(A) देखे गए वर्गों में से एक पर प्रतीक का परिवर्तन

"(B) पहले देखे गए वर्गों में से एक के एल वर्गों के भीतर दूसरे वर्ग में देखे गए वर्गों में से एक का परिवर्तन।

"यह हो सकता है कि इनमें से कुछ परिवर्तन अनिवार्य रूप से मन की स्थिति में बदलाव का आह्वान करते हैं।

इसलिए, सबसे सामान्य एकल ऑपरेशन को निम्नलिखित में से एक माना जाना चाहिए:

"(A) एक संभावित परिवर्तन (A) एक साथ मन की स्थिति के संभावित परिवर्तन के साथ प्रतीक का।

"(B) एक संभावित परिवर्तन (B) मनाया वर्गों के साथ, मन की स्थिति के संभावित परिवर्तन के साथ"

"अब हम इस कंप्यूटर का काम करने के लिए एक मशीन का निर्माण कर सकते हैं।"

कुछ साल बाद, ट्यूरिंग ने अपने विश्लेषण (शोध प्रबंध (थीसिस), परिभाषा) को इस सशक्त अभिव्यक्ति के साथ विस्तारित किया:

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

जे.बी. रोसेर (1939) और एस.सी. क्लेन (1943)

जे. बार्कले रॉसर ने एक 'प्रभावी गणितीय विधि' को निम्नलिखित तरीके से परिभाषित किया (इटैलिकाइज़ेशन जोड़ा गया): "प्रभावी विधि" का प्रयोग यहाँ प्रत्येक चरण में एक विधि के विशेष अर्थ में किया गया है जिनमें से वह ठीक-ठीक निर्धारित है और जो निश्चित रूप से चरणों की एक सीमित संख्या में उत्तर देगा। इसी विशेष अर्थ के साथ आज तक तीन अलग-अलग सटीक परिभाषाएँ दी गई हैं। [उनका फुटनोट #5; तुरंत नीचे चर्चा देखें]। इनमें से सबसे सरल स्थिति के लिए (पोस्ट और ट्यूरिंग के कारण) अनिवार्य रूप से कहता है समस्याओं के कुछ सेटों को हल करने का एक प्रभावी तरीका मौजूद है अगर कोई मशीन बना सकता है जो तब प्रश्न को सम्मिलित करने और (बाद में) उत्तर को पढ़ने से परे बिना किसी मानवीय हस्तक्षेप के सेट की किसी भी समस्या का समाधान करेगा। सभी तीन परिभाषाएँ समान हैं, इसलिए इससे कोई फ़र्क नहीं पड़ता कि किसका उपयोग किया जाता है। इसके अलावा, यह तथ्य कि तीनों समान हैं, किसी एक की शुद्धता के लिए एक बहुत मजबूत तर्क है।" (रॉसर 1939:225-226)

रॉसर का फुटनोट नंबर 5 (1) चर्च और क्लेन के काम और -परिभाषा की उनकी परिभाषा का संदर्भ देता है, विशेष रूप से, प्राथमिक संख्या सिद्धांत की अपनी एक अनसुलझी समस्या (1936) में चर्च द्वारा इसका उपयोग; (2) हेरब्रांड और गोडेल और उनके पुनरावर्तन का उपयोग, विशेष रूप से, गोडेल का अपने प्रसिद्ध पेपर ऑन फॉर्मली अनडिसीडेबल प्रपोज़िशन ऑफ़ प्रिंसिपिया मैथमैटिका एंड रिलेटेड सिस्टम्स I (1931) में उपयोग; और (3) पोस्ट (1936) और ट्यूरिंग (1936-37) उनकी गणना के तंत्र मॉडल में।

स्टीफन सी. क्लेन ने अपने अब तक के प्रसिद्ध "शोध प्रबंध (थीसिस)" के रूप में परिभाषित किया, जिसे चर्च ट्यूरिंग थीसिस के रूप में जाना जाता है। लेकिन उन्होंने इसे निम्नलिखित संदर्भ में किया (मूल में बोल्डफेस):

"12. कलन विधि (एल्गोरिथ्म) सिद्धांत... एक पूर्ण कलन विधि (एल्गोरिथ्म) सिद्धांत की स्थापना में, हम क्या करते हैं एक प्रक्रिया का वर्णन करने के लिए, स्वतंत्र चर के मूल्यों के प्रत्येक सेट के लिए प्रदर्शन योग्य, कौन सी प्रक्रिया अनिवार्य रूप से समाप्त हो जाती है और इस तरह से कि परिणाम से हम इस प्रश्न का एक निश्चित उत्तर "हां" या "नहीं" पढ़ सकते हैं, "क्या विधेय मान सत्य है?" (क्लेन 1943:273)

इतिहास 1950 के बाद

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

यह भी देखें

• सार मशीन
• एल्गोरिथम इंजीनियरिंग
• एल्गोरिथम लक्षण वर्णन
• एल्गोरिथम पूर्वाग्रह
• एल्गोरिथम रचना
• एल्गोरिथम संस्थाएं
• एल्गोरिथम संश्लेषण
• एल्गोरिथम तकनीक
• एल्गोरिथम टोपोलॉजी
• कचरा अंदर कचरा बाहर
• एल्गोरिदम का परिचय (पाठ्यपुस्तक)
• एल्गोरिदम की सूची
• एल्गोरिथ्म सामान्य विषयों की सूची
• सैद्धांतिक कंप्यूटर विज्ञान में महत्वपूर्ण प्रकाशनों की सूची - एल्गोरिदम
• एल्गोरिदम का विनियमन
• गणना का सिद्धांत
  • कम्प्यूटिबिलिटी थ्योरी
  • कम्प्यूटेशनल जटिलता सिद्धांत
• कम्प्यूटेशनल गणित

ग्रन्थसूची

• Axt, P (1959). "On a Subrecursive Hierarchy and Primitive Recursive Degrees". Transactions of the American Mathematical Society. 92 (1): 85–105. doi:10.2307/1993169. JSTOR 1993169.
• Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw–Hill Book Company, New York. ISBN 0-07-004357-4.
• Blass, Andreas; Gurevich, Yuri (2003). "Algorithms: A Quest for Absolute Definitions" (PDF). Bulletin of European Association for Theoretical Computer Science. 81. Includes an excellent bibliography of 56 references.
• Bolter, David J. (1984). Turing's Man: Western Culture in the Computer Age (1984 ed.). Chapel Hill, NC: The University of North Carolina Press. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0
• Boolos, George; Jeffrey, Richard (1999) [1974]. Computability and Logic (4th ed.). Cambridge University Press, London. ISBN 978-0-521-20402-6.: cf. Chapter 3 Turing machines where they discuss "certain enumerable sets not effectively (mechanically) enumerable".
• Burgin, Mark (2004). Super-Recursive Algorithms. Springer. ISBN 978-0-387-95569-8.
• Campagnolo, M.L., Moore, C., and Costa, J.F. (2000) An analog characterization of the subrecursive functions. In Proc. of the 4th Conference on Real Numbers and Computers, Odense University, pp. 91–109
• Church, Alonzo (1936). "An Unsolvable Problem of Elementary Number Theory". The American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Reprinted in The Undecidable, p. 89ff. The first expression of "Church's Thesis". See in particular page 100 (The Undecidable) where he defines the notion of "effective calculability" in terms of "an algorithm", and he uses the word "terminates", etc.
• Church, Alonzo (1936). "A Note on the Entscheidungsproblem". The Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. Church, Alonzo (1936). "Correction to a Note on the Entscheidungsproblem". The Journal of Symbolic Logic. 1 (3): 101–102. doi:10.2307/2269030. JSTOR 2269030. Reprinted in The Undecidable, p. 110ff. Church shows that the Entscheidungsproblem is unsolvable in about 3 pages of text and 3 pages of footnotes.
• Daffa', Ali Abdullah al- (1977). The Muslim contribution to mathematics. London: Croom Helm. ISBN 978-0-85664-464-1.
• Davis, Martin (1965). The Undecidable: Basic Papers On Undecidable Propositions, Unsolvable Problems and Computable Functions. New York: Raven Press. ISBN 978-0-486-43228-1. Davis gives commentary before each article. Papers of Gödel, Alonzo Church, Turing, Rosser, Kleene, and Emil Post are included; those cited in the article are listed here by author's name.
• Davis, Martin (2000). Engines of Logic: Mathematicians and the Origin of the Computer. New York: W.W. Nortion. ISBN 978-0-393-32229-3. Davis offers concise biographies of Leibniz, Boole, Frege, Cantor, Hilbert, Gödel and Turing with von Neumann as the show-stealing villain. Very brief bios of Joseph-Marie Jacquard, Babbage, Ada Lovelace, Claude Shannon, Howard Aiken, etc.
•  This article incorporates public domain material from Black, Paul E. "algorithm". Dictionary of Algorithms and Data Structures.
• Dean, Tim (2012). "Evolution and moral diversity". Baltic International Yearbook of Cognition, Logic and Communication. 7. doi:10.4148/biyclc.v7i0.1775.
• Dennett, Daniel (1995). Darwin's Dangerous Idea. pp. 32–36. Bibcode:1996Cmplx...2a..32M. doi:10.1002/(SICI)1099-0526(199609/10)2:1<32::AID-CPLX8>3.0.CO;2-H. ISBN 978-0-684-80290-9. {{cite book}}: |journal= ignored (help)
• Dilson, Jesse (2007). The Abacus ((1968, 1994) ed.). St. Martin's Press, NY. ISBN 978-0-312-10409-2., ISBN 0-312-10409-X
• Yuri Gurevich, Sequential Abstract State Machines Capture Sequential Algorithms, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pp. 77–111. Includes bibliography of 33 sources.
• van Heijenoort, Jean (2001). From Frege to Gödel, A Source Book in Mathematical Logic, 1879–1931 ((1967) ed.). Harvard University Press, Cambridge. ISBN 978-0-674-32449-7., 3rd edition 1976[?], ISBN 0-674-32449-8 (pbk.)
• Hodges, Andrew (1983). Alan Turing: The Enigma. pp. 107–108. Bibcode:1984PhT....37k.107H. doi:10.1063/1.2915935. ISBN 978-0-671-49207-6. {{cite book}}: |journal= ignored (help), ISBN 0-671-49207-1. Cf. Chapter "The Spirit of Truth" for a history leading to, and a discussion of, his proof.
• Kleene, Stephen C. (1936). "General Recursive Functions of Natural Numbers". Mathematische Annalen. 112 (5): 727–742. doi:10.1007/BF01565439. S2CID 120517999. Archived from the original on September 3, 2014. Retrieved September 30, 2013. Presented to the American Mathematical Society, September 1935. Reprinted in The Undecidable, p. 237ff. Kleene's definition of "general recursion" (known now as mu-recursion) was used by Church in his 1935 paper An Unsolvable Problem of Elementary Number Theory that proved the "decision problem" to be "undecidable" (i.e., a negative result).
• Kleene, Stephen C. (1943). "Recursive Predicates and Quantifiers". Transactions of the American Mathematical Society. 53 (1): 41–73. doi:10.2307/1990131. JSTOR 1990131. Reprinted in The Undecidable, p. 255ff. Kleene refined his definition of "general recursion" and proceeded in his chapter "12. Algorithmic theories" to posit "Thesis I" (p. 274); he would later repeat this thesis (in Kleene 1952:300) and name it "Church's Thesis"(Kleene 1952:317) (i.e., the Church thesis).
• Kleene, Stephen C. (1991) [1952]. Introduction to Metamathematics (Tenth ed.). North-Holland Publishing Company. ISBN 978-0-7204-2103-3.
• Knuth, Donald (1997). Fundamental Algorithms, Third Edition. Reading, Massachusetts: Addison–Wesley. ISBN 978-0-201-89683-1.
• Knuth, Donald (1969). Volume 2/Seminumerical Algorithms, The Art of Computer Programming First Edition. Reading, Massachusetts: Addison–Wesley.
• Kosovsky, N.K. Elements of Mathematical Logic and its Application to the theory of Subrecursive Algorithms, LSU Publ., Leningrad, 1981
• Kowalski, Robert (1979). "Algorithm=Logic+Control". Communications of the ACM. 22 (7): 424–436. doi:10.1145/359131.359136. S2CID 2509896.
• A.A. Markov (1954) Theory of algorithms. [Translated by Jacques J. Schorr-Kon and PST staff] Imprint Moscow, Academy of Sciences of the USSR, 1954 [i.e., Jerusalem, Israel Program for Scientific Translations, 1961; available from the Office of Technical Services, U.S. Dept. of Commerce, Washington] Description 444 p. 28 cm. Added t.p. in Russian Translation of Works of the Mathematical Institute, Academy of Sciences of the USSR, v. 42. Original title: Teoriya algerifmov. [QA248.M2943 Dartmouth College library. U.S. Dept. of Commerce, Office of Technical Services, number OTS 60-51085.]
• Minsky, Marvin (1967). Computation: Finite and Infinite Machines (First ed.). Prentice-Hall, Englewood Cliffs, NJ. ISBN 978-0-13-165449-5. Minsky expands his "...idea of an algorithm – an effective procedure..." in chapter 5.1 Computability, Effective Procedures and Algorithms. Infinite machines.
• Post, Emil (1936). "Finite Combinatory Processes, Formulation I". The Journal of Symbolic Logic. 1 (3): 103–105. doi:10.2307/2269031. JSTOR 2269031. Reprinted in The Undecidable, pp. 289ff. Post defines a simple algorithmic-like process of a man writing marks or erasing marks and going from box to box and eventually halting, as he follows a list of simple instructions. This is cited by Kleene as one source of his "Thesis I", the so-called Church–Turing thesis.
• Rogers, Jr, Hartley (1987). Theory of Recursive Functions and Effective Computability. The MIT Press. ISBN 978-0-262-68052-3.
• Rosser, J.B. (1939). "An Informal Exposition of Proofs of Godel's Theorem and Church's Theorem". Journal of Symbolic Logic. 4 (2): 53–60. doi:10.2307/2269059. JSTOR 2269059. Reprinted in The Undecidable, p. 223ff. Herein is Rosser's famous definition of "effective method": "...a method each step of which is precisely predetermined and which is certain to produce the answer in a finite number of steps... a machine which will then solve any problem of the set with no human intervention beyond inserting the question and (later) reading the answer" (p. 225–226, The Undecidable)
• Santos-Lang, Christopher (2014). "Moral Ecology Approaches to Machine Ethics" (PDF). In van Rysewyk, Simon; Pontier, Matthijs (eds.). Machine Medical Ethics. Intelligent Systems, Control and Automation: Science and Engineering. Vol. 74. Switzerland: Springer. pp. 111–127. doi:10.1007/978-3-319-08108-3_8. ISBN 978-3-319-08107-6.
• Scott, Michael L. (2009). Programming Language Pragmatics (3rd ed.). Morgan Kaufmann Publishers/Elsevier. ISBN 978-0-12-374514-9.
• Sipser, Michael (2006). Introduction to the Theory of Computation. PWS Publishing Company. ISBN 978-0-534-94728-6.
• Sober, Elliott; Wilson, David Sloan (1998). Unto Others: The Evolution and Psychology of Unselfish Behavior. Cambridge: Harvard University Press. ISBN 9780674930469.
• Stone, Harold S. (1972). Introduction to Computer Organization and Data Structures (1972 ed.). McGraw-Hill, New York. ISBN 978-0-07-061726-1. Cf. in particular the first chapter titled: Algorithms, Turing Machines, and Programs. His succinct informal definition: "...any sequence of instructions that can be obeyed by a robot, is called an algorithm" (p. 4).
• Tausworthe, Robert C (1977). Standardized Development of Computer Software Part 1 Methods. Englewood Cliffs NJ: Prentice–Hall, Inc. ISBN 978-0-13-842195-3.
• Turing, Alan M. (1936–37). "On Computable Numbers, With An Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2. 42: 230–265. doi:10.1112/plms/s2-42.1.230.. Corrections, ibid, vol. 43(1937) pp. 544–546. Reprinted in The Undecidable, p. 116ff. Turing's famous paper completed as a Master's dissertation while at King's College Cambridge UK.
• Turing, Alan M. (1939). "Systems of Logic Based on Ordinals". Proceedings of the London Mathematical Society. 45: 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. Reprinted in The Undecidable, pp. 155ff. Turing's paper that defined "the oracle" was his PhD thesis while at Princeton.
• United States Patent and Trademark Office (2006), 2106.02 **>Mathematical Algorithms: 2100 Patentability, Manual of Patent Examining Procedure (MPEP). Latest revision August 2006

अग्रिम पठन

• Bellah, Robert Neelly (1985). Habits of the Heart: Individualism and Commitment in American Life. Berkeley: University of California Press. ISBN 978-0-520-25419-0.
• Berlinski, David (2001). The Advent of the Algorithm: The 300-Year Journey from an Idea to the Computer. Harvest Books. ISBN 978-0-15-601391-8.
• Chabert, Jean-Luc (1999). A History of Algorithms: From the Pebble to the Microchip. Springer Verlag. ISBN 978-3-540-63369-3.
• Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009). Introduction To Algorithms (3rd ed.). MIT Press. ISBN 978-0-262-03384-8.
• Harel, David; Feldman, Yishai (2004). Algorithmics: The Spirit of Computing. Addison-Wesley. ISBN 978-0-321-11784-7.
• Hertzke, Allen D.; McRorie, Chris (1998). "The Concept of Moral Ecology". In Lawler, Peter Augustine; McConkey, Dale (eds.). Community and Political Thought Today. Westport, CT: Praeger.
• Knuth, Donald E. (2000). Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information.
• Knuth, Donald E. (2010). Selected Papers on Design of Algorithms. Stanford, California: Center for the Study of Language and Information.
• Wallach, Wendell; Allen, Colin (November 2008). Moral Machines: Teaching Robots Right from Wrong. US: Oxford University Press. ISBN 978-0-19-537404-9.
• Bleakley, Chris (2020). Poems that Solve Puzzles: The History and Science of Algorithms. Oxford University Press. ISBN 978-0-19-885373-2.

बाहरी संबंध

• "Algorithm", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Algorithms at Curlie
• Weisstein, Eric W. "Algorithm". MathWorld.
• Dictionary of Algorithms and Data Structures – National Institute of Standards and Technology

Algorithm repositories

• The Stony Brook Algorithm Repository – State University of New York at Stony Brook
• Collected Algorithms of the ACM – Association for Computing Machinery
• The Stanford GraphBase – Stanford University