Computability

कंप्यूटर साइंस में कॉन्सेप्ट्स

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Computability क्या है?

Computable Problem

  • एल्गोरिदम का होना: स्पष्ट प्रक्रिया मौजूद है.
  • सीमित समय: सीमित चरणों में आउटपुट देता है.

Non-Computable Problem

  • एल्गोरिदम न होना: सभी संभावित इनपुट पर हल नहीं कर सकता.
  • अनंत गणना: निष्कर्ष तक कभी न पहुँचे.
1 Non-Computable समस्याएँ, एल्गोरिदम मिल जाने पर और/या किसी ज्ञात एल्गोरिदम को सीमित समय में समाप्त करा देने पर, Computable बन सकती हैं.
कंप्यूटर साइंस में कॉन्सेप्ट्स

Automata

Automata की परिभाषा

  • काल्पनिक मशीनें
  • गणना कैसे काम करती है, समझने में मदद
  • स्टेट्स होते हैं
  • स्टेट्स के बीच ट्रांज़िशन के नियम होते हैं

Automata को दर्शाने के लिए ट्रैफिक लाइट का उदाहरण

कंप्यूटर साइंस में कॉन्सेप्ट्स

Finite Automata (FA)

Finite Automata (FA)

  • साधारण machines
  • स्टेट्स की तय संख्या
  • वर्तमान स्टेट से आगे मेमोरी नहीं

Finite Automata के लिए ट्रैफिक लाइट और स्टेट्स का उदाहरण

कंप्यूटर साइंस में कॉन्सेप्ट्स

Pushdown Automata (PDA)

Pushdown Automata (PDA)

  • अधिक शक्तिशाली
  • स्टेट्स होते हैं
  • अधिक जटिल निर्णयों के लिए स्टैक-आधारित मेमोरी

Pushdown Automata के लिए ट्रैफिक लाइट और स्टेट्स का उदाहरण

कंप्यूटर साइंस में कॉन्सेप्ट्स

सारांश

Finite Automata (FA)

  • सरल टास्क के लिए उपयोगी

Pushdown Automata (PDA)

  • जटिल समस्याओं के लिए अधिक शक्तिशाली

महत्त्व

  • यदि किसी समस्या को automata से मॉडल कर सकते हैं, तो उसे हल करने का एल्गोरिदम लागू कर सकते हैं
कंप्यूटर साइंस में कॉन्सेप्ट्स

अभ्यास करते हैं!

कंप्यूटर साइंस में कॉन्सेप्ट्स

Preparing Video For Download...