सदस्य वार्ता:Athulya Sebastian/प्रयोगपृष्ठ

संगणना का सिद्धांत

computation

सैद्धांतिक कंप्यूटर विज्ञान और गणित में, कम्प्यूटेशन का सिद्धांत वह शाखा है जो एक एल्गोरिथ्म का उपयोग करके कम्प्यूटेशन के मॉडल पर कितनी कुशलता से समस्याओं को हल कर सकता है। क्षेत्र को तीन प्रमुख शाखाओं में विभाजित किया गया है: ऑटोमेटा सिद्धांत और भाषाएं, कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल जटिलता सिद्धांत, जो इस प्रश्न से जुड़े हैं: "कंप्यूटर की मौलिक क्षमताएं और सीमाएं क्या हैं?" 

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

इतिहास

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

गणना के सिद्धांत के कुछ अग्रदूतों में रेमन लुलुल, अलोंजो चर्च, कर्ट गोडेल, एलन ट्यूरिंग, स्टीफन क्लेन, रोससा पेटर, जॉन वॉन न्यूमैन और क्लैवल शैनन थे।

शाखाओं

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

औपचारिक भाषा सिद्धांत

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

संगणना सिद्धांत

मुख्य लेख: संगणना सिद्धांत

कम्प्यूटेबिलिटी सिद्धांत मुख्य रूप से इस सवाल से संबंधित है कि कंप्यूटर पर समस्या किस हद तक हल है। यह कथन कि ट्यूरिंग मशीन द्वारा हल करने की समस्या को हल नहीं किया जा सकता है [7] कम्प्यूटेबिलिटी सिद्धांत में सबसे महत्वपूर्ण परिणामों में से एक है, क्योंकि यह एक ठोस समस्या का एक उदाहरण है जो ट्यूरिंग मशीन का उपयोग करके हल करना आसान और असंभव दोनों है। । कम्प्यूटिंग सिद्धांत का अधिकांश भाग हॉल्टिंग समस्या के परिणाम पर बनता है।

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

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

कम्प्यूटेशनल जटिलता सिद्धांत

मुख्य लेख: कम्प्यूटेशनल जटिलता सिद्धांत

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

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

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

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

संदर्भ

* माइकल सिपसर (2013)। अभिकलन 3 के सिद्धांत का परिचय। सेनगेज लर्निंग। आईएसबीएन 978-1-133-18779-0। गणना के सिद्धांत के केंद्रीय क्षेत्र: ऑटोमेटा, कम्प्यूटेबिलिटी और जटिलता। (पृष्ठ 1)
*  हॉजेस, एंड्रयू (2012)। एलन ट्यूरिंग: द एनिग्मा (द सेंटेनरी एडिशन)। प्रिंसटन यूनिवर्सिटी प्रेस। आईएसबीएन 978-0-691-15564-7।
*  राबिन, माइकल ओ। (जून 2012)। ट्यूरिंग, चर्च, गोडेल, संगणना, जटिलता और यादृच्छिकता: एक व्यक्तिगत दृष्टिकोण।
*  डोनाल्ड मॉन्क (1976)। गणितीय तर्क। स्प्रिंगर-वर्लग। आईएसबीएन 9780387901701।
*  हॉपक्रॉफ्ट, जॉन ई। और जेफरी डी। उल्मन (2006)। ऑटोमेटा थ्योरी, भाषा और संगणना का परिचय। तीसरा संस्करण। पढ़ना, एमए: एडिसन-वेस्ले। आईएसबीएन 978-0-321-45536-9।