कंप्यूटर · भाग C - सॉफ़्टवेयर, एल्गोरिद्म (काम करने के क्रमवार नियम) और गणना · 39 में से मुख्य टॉपिक 10

संगणना का सिद्धांत, औपचारिक भाषाएँ और सत्यापन

गणना की गणितीय सीमाएँ, भाषा की पहचान, औपचारिक विनिर्देश और प्रोग्राम के व्यवहार पर भरोसा।

अंदर 128 चीज़ेंCOM-10

इसे भी देखें: भूगोल: मानव भूगोल — 10. भाषा भूगोलतर्कशक्ति (रीज़निंग): रीज़निंग सीखने का रास्ता (रोडमैप)विज्ञान और प्रौद्योगिकी: कंप्यूटर संरचना, ऑपरेटिंग सिस्टम, प्रोग्रामिंग और सॉफ़्टवेयरकला और संस्कृति: भारत की भाषाएँ और लिपियाँ

  1. 1

    ऐतिहासिक विकास — प्रमुख तिथियाँ

    • गोडेल के अपूर्णता परिणाम औपचारिक प्रणालियों की तस्वीर बदल देते हैं।1931
    • ट्यूरिंग और चर्च एक-दूसरे के पूरक तरीकों से कम्प्यूटेबिलिटी को औपचारिक रूप देते हैं।1936
    • ऑटोमेटा और औपचारिक भाषा मॉडल स्विचिंग और संचार सिद्धांत के साथ विकसित होते हैं।1940s-1950s
    • चॉम्स्की का व्याकरण पदानुक्रम औपचारिक भाषाओं को व्यवस्थित करने में मदद करता है।1956
    • जटिलता वर्ग, प्रोग्राम सत्यापन और तर्क-आधारित विनिर्देश परिपक्व होते हैं।1960s-1970s
    • मॉडल चेकिंग, SAT हल करना और प्रूफ़ असिस्टेंट व्यावहारिक सत्यापन उपकरण बनते हैं।1980s-2000s
    • औपचारिक विधियाँ क्रिप्टोग्राफ़ी, प्रोटोकॉल, सुरक्षा-महत्त्वपूर्ण सिस्टम और सत्यापित सॉफ़्टवेयर पर लागू होती हैं।2010s-2020s
  2. 2

    औपचारिक नींव

    • वर्णमाला (alphabet); प्रतीक; स्ट्रिंग; भाषा; संयोजन (concatenation); क्लोज़र; भाषा पर संक्रिया; व्याकरण (grammar); उत्पादन नियम (production rule); व्युत्पत्ति (derivation)
      10 और बातें
      • वर्णमाला (alphabet)
      • प्रतीक
      • स्ट्रिंग
      • भाषा
      • संयोजन (concatenation)
      • क्लोज़र
      • भाषा पर संक्रिया
      • व्याकरण (grammar)
      • उत्पादन नियम (production rule)
      • व्युत्पत्ति (derivation)
    • रेगुलर एक्सप्रेशन; रेगुलर भाषा; संदर्भ-मुक्त (context-free) भाषा; संदर्भ-संवेदी और अप्रतिबंधित व्याकरण
      4 और बातें
      • रेगुलर एक्सप्रेशन
      • रेगुलर भाषा
      • संदर्भ-मुक्त (context-free) भाषा
      • संदर्भ-संवेदी और अप्रतिबंधित व्याकरण
  3. 3

    ऑटोमेटा और पहचान

    • नियतात्मक/अनियतात्मक परिमित ऑटोमेटा (DFA/NFA); एप्सिलॉन संक्रमण; रेगुलर एक्सप्रेशन से तुल्यता
      3 और बातें
      • नियतात्मक/अनियतात्मक परिमित ऑटोमेटा (DFA/NFA)
      • एप्सिलॉन संक्रमण
      • रेगुलर एक्सप्रेशन से तुल्यता
    • पुशडाउन ऑटोमेटा; स्टैक; संदर्भ-मुक्त भाषा; पार्स ट्री; अस्पष्टता (ambiguity)
      5 और बातें
      • पुशडाउन ऑटोमेटा
      • स्टैक
      • संदर्भ-मुक्त भाषा
      • पार्स ट्री
      • अस्पष्टता (ambiguity)
    • ट्यूरिंग मशीन; टेप; अवस्था (state); संक्रमण फलन; बहु-टेप मॉडल; सार्वभौमिक (universal) मशीन
      6 और बातें
      • ट्यूरिंग मशीन
      • टेप
      • अवस्था (state)
      • संक्रमण फलन
      • बहु-टेप मॉडल
      • सार्वभौमिक (universal) मशीन
  4. 4

    कम्प्यूटेबिलिटी और निर्णेयता

    • गणनीय (computable) फलन; पहचानने वाला बनाम निर्णय करने वाला (recognizer vs decider); हॉल्टिंग प्रॉब्लम; न्यूनीकरण; अनिर्णेय समस्या
      5 और बातें
      • गणनीय (computable) फलन
      • पहचानने वाला बनाम निर्णय करने वाला (recognizer vs decider)
      • हॉल्टिंग प्रॉब्लम
      • न्यूनीकरण
      • अनिर्णेय समस्या
    • चर्च-ट्यूरिंग थीसिस; सार्वभौमिक कंप्यूटेशन; विकर्णीकरण (diagonalization); राइस का प्रमेय; औपचारिक तर्क की सीमाएँ
      5 और बातें
      • चर्च-ट्यूरिंग थीसिस
      • सार्वभौमिक कंप्यूटेशन
      • विकर्णीकरण (diagonalization)
      • राइस का प्रमेय
      • औपचारिक तर्क की सीमाएँ
  5. 5

    जटिलता सिद्धांत

    • समय/स्थान वर्ग; P; NP; Co-NP; NP-पूर्ण; NP-कठोर; बहुपद अपचयन (polynomial reduction)
      7 और बातें
      • समय/स्थान वर्ग
      • P
      • NP
      • Co-NP
      • NP-पूर्ण
      • NP-कठोर
      • बहुपद अपचयन (polynomial reduction)
    • यादृच्छिक वर्ग; सन्निकटन; पैरामीटरयुक्त जटिलता; स्थान पदानुक्रम; सर्किट जटिलता; क्वांटम जटिलता का परिचय
      6 और बातें
      • यादृच्छिक वर्ग
      • सन्निकटन
      • पैरामीटरयुक्त जटिलता
      • स्थान पदानुक्रम
      • सर्किट जटिलता
      • क्वांटम जटिलता का परिचय
  6. 6

    कंप्यूटर विज्ञान के लिए तर्कशास्त्र

    • प्रस्तावात्मक/विधेय तर्क; कालिक (temporal) तर्क; होर तर्क (Hoare logic); मोडल तर्क; टाइप तर्क; फ़िक्स्ड-पॉइंट तर्क
      6 और बातें
      • प्रस्तावात्मक/विधेय तर्क
      • कालिक (temporal) तर्क
      • होर तर्क (Hoare logic)
      • मोडल तर्क
      • टाइप तर्क
      • फ़िक्स्ड-पॉइंट तर्क
    • SAT/SMT; प्रमेय सिद्ध करना (theorem proving); रिज़ॉल्यूशन; एकीकरण (unification); बाधा हल करना (constraint solving); संतुष्टि-योग्यता और मॉडल निर्माण
      6 और बातें
      • SAT/SMT
      • प्रमेय सिद्ध करना (theorem proving)
      • रिज़ॉल्यूशन
      • एकीकरण (unification)
      • बाधा हल करना (constraint solving)
      • संतुष्टि-योग्यता और मॉडल निर्माण
  7. 7

    प्रोग्राम विनिर्देश और प्रमाण

    • पूर्व-शर्तें/पश्च-शर्तें; इनवेरिएंट; कॉन्ट्रैक्ट (शर्तें); परिष्कार (refinement); सबसे कमज़ोर पूर्व-शर्त (weakest precondition); समाप्ति का प्रमाण
      6 और बातें
      • पूर्व-शर्तें/पश्च-शर्तें
      • इनवेरिएंट
      • कॉन्ट्रैक्ट (शर्तें)
      • परिष्कार (refinement)
      • सबसे कमज़ोर पूर्व-शर्त (weakest precondition)
      • समाप्ति का प्रमाण
    • होर ट्रिपल; सेपरेशन लॉजिक; स्वामित्व/उधार (ownership/borrowing) पर तर्क; कार्यात्मक शुद्धता; गैर-कार्यात्मक गुण
      5 और बातें
      • होर ट्रिपल
      • सेपरेशन लॉजिक
      • स्वामित्व/उधार (ownership/borrowing) पर तर्क
      • कार्यात्मक शुद्धता
      • गैर-कार्यात्मक गुण
  8. 8

    सत्यापन की विधियाँ

    • स्टैटिक विश्लेषण; प्रतीकात्मक निष्पादन (symbolic execution); अमूर्त व्याख्या (abstract interpretation); मॉडल चेकिंग; तुल्यता जाँच (equivalence checking); प्रूफ़ असिस्टेंट
      6 और बातें
      • स्टैटिक विश्लेषण
      • प्रतीकात्मक निष्पादन (symbolic execution)
      • अमूर्त व्याख्या (abstract interpretation)
      • मॉडल चेकिंग
      • तुल्यता जाँच (equivalence checking)
      • प्रूफ़ असिस्टेंट
    • टेस्ट बनाना; कवरेज-निर्देशित फ़ज़िंग; गुण-आधारित टेस्ट; रनटाइम सत्यापन; प्रमाण-सहित कोड (proof-carrying code)
      5 और बातें
      • टेस्ट बनाना
      • कवरेज-निर्देशित फ़ज़िंग
      • गुण-आधारित टेस्ट
      • रनटाइम सत्यापन
      • प्रमाण-सहित कोड (proof-carrying code)
  9. 9

    विश्वसनीयता और आश्वासन

    • सुरक्षा मामले (safety cases); ख़तरा विश्लेषण; फ़ॉल्ट ट्री; औपचारिक आवश्यकताएँ; अनुरेखणीयता; स्वतंत्र सत्यापन/वैधीकरण
      6 और बातें
      • सुरक्षा मामले (safety cases)
      • ख़तरा विश्लेषण
      • फ़ॉल्ट ट्री
      • औपचारिक आवश्यकताएँ
      • अनुरेखणीयता
      • स्वतंत्र सत्यापन/वैधीकरण
    • भरोसेमंद कंप्यूटिंग आधार (TCB); आश्वासन स्तर; समीक्षा के प्रमाण; दोबारा जाँचे जा सकने वाले प्रमाण और उपकरणों की सीमाएँ
      4 और बातें
      • भरोसेमंद कंप्यूटिंग आधार (TCB)
      • आश्वासन स्तर
      • समीक्षा के प्रमाण
      • दोबारा जाँचे जा सकने वाले प्रमाण और उपकरणों की सीमाएँ