गणना का मॉडल

For computer models simulating complex systems, see Computational model.

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

मॉडल

गणना के मॉडल को तीन श्रेणियों में वर्गीकृत किया जा सकता है: अनुक्रमिक मॉडल, कार्यात्मक मॉडल और समवर्ती मॉडल।

अनुक्रमिक मॉडल

अनुक्रमिक मॉडल में शामिल हैं:

• परिमित राज्य मशीनें
• पोस्ट मशीन (पोस्ट-ट्यूरिंग मशीन और टैग सिस्टम)।
• पुशडाउन ऑटोमेटा
• रजिस्टर मशीन
  • रैंडम-एक्सेस मशीनें
• ट्यूरिंग मशीनें
• निर्णय वृक्ष मॉडल

कार्यात्मक मॉडल

कार्यात्मक मॉडल में शामिल हैं:

• सार पुनर्लेखन प्रणाली
• संयुक्त तर्क
• सामान्य पुनरावर्ती कार्य
• लैम्ब्डा कैलकुलस

समवर्ती मॉडल

समवर्ती मॉडल में शामिल हैं:

• अभिनेता मॉडल
• सेलुलर automaton
• इंटरेक्शन नेट
• क्हान प्रक्रिया नेटवर्क
• लॉजिक गेट्स और सर्किट (कंप्यूटर साइंस)
• पेट्री जाल
• तुल्यकालिक डेटा प्रवाह

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

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

उपयोग करता है

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

यह भी देखें

• स्टैक मशीन (0-ऑपरेंड मशीन)
• संचायक मशीन (1-ऑपरेंड मशीन)
• रजिस्टर मशीन (2,3,... ऑपरेंड मशीन)
• रैंडम-एक्सेस मशीन
• सार मशीन
• सेल-जांच मॉडल
• रॉबर्टसन-वेब क्वेरी मॉडल
• चॉम्स्की पदानुक्रम
• ट्यूरिंग पूर्णता

आगे की पढाई

• Fernández, Maribel (2009). Models of Computation: An Introduction to Computability Theory. Undergraduate Topics in Computer Science. Springer. ISBN 978-1-84882-433-1.
• Savage, John E. (1998). Models Of Computation: Exploring the Power of Computing. Addison-Wesley. ISBN 978-0201895391.

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