कंप्यूटर · भाग C - सॉफ़्टवेयर, एल्गोरिद्म (काम करने के क्रमवार नियम) और गणना · 39 में से मुख्य टॉपिक 10
संगणना का सिद्धांत, औपचारिक भाषाएँ और सत्यापन
गणना की गणितीय सीमाएँ, भाषा की पहचान, औपचारिक विनिर्देश और प्रोग्राम के व्यवहार पर भरोसा।
अंदर 128 चीज़ेंCOM-10
इसे भी देखें: भूगोल: मानव भूगोल — 10. भाषा भूगोलतर्कशक्ति (रीज़निंग): रीज़निंग सीखने का रास्ता (रोडमैप)विज्ञान और प्रौद्योगिकी: कंप्यूटर संरचना, ऑपरेटिंग सिस्टम, प्रोग्रामिंग और सॉफ़्टवेयरकला और संस्कृति: भारत की भाषाएँ और लिपियाँ
- 1
ऐतिहासिक विकास — प्रमुख तिथियाँ
- गोडेल के अपूर्णता परिणाम औपचारिक प्रणालियों की तस्वीर बदल देते हैं।1931
- ट्यूरिंग और चर्च एक-दूसरे के पूरक तरीकों से कम्प्यूटेबिलिटी को औपचारिक रूप देते हैं।1936
- ऑटोमेटा और औपचारिक भाषा मॉडल स्विचिंग और संचार सिद्धांत के साथ विकसित होते हैं।1940s-1950s
- चॉम्स्की का व्याकरण पदानुक्रम औपचारिक भाषाओं को व्यवस्थित करने में मदद करता है।1956
- जटिलता वर्ग, प्रोग्राम सत्यापन और तर्क-आधारित विनिर्देश परिपक्व होते हैं।1960s-1970s
- मॉडल चेकिंग, SAT हल करना और प्रूफ़ असिस्टेंट व्यावहारिक सत्यापन उपकरण बनते हैं।1980s-2000s
- औपचारिक विधियाँ क्रिप्टोग्राफ़ी, प्रोटोकॉल, सुरक्षा-महत्त्वपूर्ण सिस्टम और सत्यापित सॉफ़्टवेयर पर लागू होती हैं।2010s-2020s
- 2
औपचारिक नींव
- वर्णमाला (alphabet); प्रतीक; स्ट्रिंग; भाषा; संयोजन (concatenation); क्लोज़र; भाषा पर संक्रिया; व्याकरण (grammar); उत्पादन नियम (production rule); व्युत्पत्ति (derivation)
10 और बातें
- वर्णमाला (alphabet)
- प्रतीक
- स्ट्रिंग
- भाषा
- संयोजन (concatenation)
- क्लोज़र
- भाषा पर संक्रिया
- व्याकरण (grammar)
- उत्पादन नियम (production rule)
- व्युत्पत्ति (derivation)
- रेगुलर एक्सप्रेशन; रेगुलर भाषा; संदर्भ-मुक्त (context-free) भाषा; संदर्भ-संवेदी और अप्रतिबंधित व्याकरण
4 और बातें
- रेगुलर एक्सप्रेशन
- रेगुलर भाषा
- संदर्भ-मुक्त (context-free) भाषा
- संदर्भ-संवेदी और अप्रतिबंधित व्याकरण
- वर्णमाला (alphabet); प्रतीक; स्ट्रिंग; भाषा; संयोजन (concatenation); क्लोज़र; भाषा पर संक्रिया; व्याकरण (grammar); उत्पादन नियम (production rule); व्युत्पत्ति (derivation)
- 3
ऑटोमेटा और पहचान
- नियतात्मक/अनियतात्मक परिमित ऑटोमेटा (DFA/NFA); एप्सिलॉन संक्रमण; रेगुलर एक्सप्रेशन से तुल्यता
3 और बातें
- नियतात्मक/अनियतात्मक परिमित ऑटोमेटा (DFA/NFA)
- एप्सिलॉन संक्रमण
- रेगुलर एक्सप्रेशन से तुल्यता
- पुशडाउन ऑटोमेटा; स्टैक; संदर्भ-मुक्त भाषा; पार्स ट्री; अस्पष्टता (ambiguity)
5 और बातें
- पुशडाउन ऑटोमेटा
- स्टैक
- संदर्भ-मुक्त भाषा
- पार्स ट्री
- अस्पष्टता (ambiguity)
- ट्यूरिंग मशीन; टेप; अवस्था (state); संक्रमण फलन; बहु-टेप मॉडल; सार्वभौमिक (universal) मशीन
6 और बातें
- ट्यूरिंग मशीन
- टेप
- अवस्था (state)
- संक्रमण फलन
- बहु-टेप मॉडल
- सार्वभौमिक (universal) मशीन
- नियतात्मक/अनियतात्मक परिमित ऑटोमेटा (DFA/NFA); एप्सिलॉन संक्रमण; रेगुलर एक्सप्रेशन से तुल्यता
- 4
कम्प्यूटेबिलिटी और निर्णेयता
- गणनीय (computable) फलन; पहचानने वाला बनाम निर्णय करने वाला (recognizer vs decider); हॉल्टिंग प्रॉब्लम; न्यूनीकरण; अनिर्णेय समस्या
5 और बातें
- गणनीय (computable) फलन
- पहचानने वाला बनाम निर्णय करने वाला (recognizer vs decider)
- हॉल्टिंग प्रॉब्लम
- न्यूनीकरण
- अनिर्णेय समस्या
- चर्च-ट्यूरिंग थीसिस; सार्वभौमिक कंप्यूटेशन; विकर्णीकरण (diagonalization); राइस का प्रमेय; औपचारिक तर्क की सीमाएँ
5 और बातें
- चर्च-ट्यूरिंग थीसिस
- सार्वभौमिक कंप्यूटेशन
- विकर्णीकरण (diagonalization)
- राइस का प्रमेय
- औपचारिक तर्क की सीमाएँ
- गणनीय (computable) फलन; पहचानने वाला बनाम निर्णय करने वाला (recognizer vs decider); हॉल्टिंग प्रॉब्लम; न्यूनीकरण; अनिर्णेय समस्या
- 5
जटिलता सिद्धांत
- समय/स्थान वर्ग; P; NP; Co-NP; NP-पूर्ण; NP-कठोर; बहुपद अपचयन (polynomial reduction)
7 और बातें
- समय/स्थान वर्ग
- P
- NP
- Co-NP
- NP-पूर्ण
- NP-कठोर
- बहुपद अपचयन (polynomial reduction)
- यादृच्छिक वर्ग; सन्निकटन; पैरामीटरयुक्त जटिलता; स्थान पदानुक्रम; सर्किट जटिलता; क्वांटम जटिलता का परिचय
6 और बातें
- यादृच्छिक वर्ग
- सन्निकटन
- पैरामीटरयुक्त जटिलता
- स्थान पदानुक्रम
- सर्किट जटिलता
- क्वांटम जटिलता का परिचय
- समय/स्थान वर्ग; P; NP; Co-NP; NP-पूर्ण; NP-कठोर; बहुपद अपचयन (polynomial reduction)
- 6
कंप्यूटर विज्ञान के लिए तर्कशास्त्र
- प्रस्तावात्मक/विधेय तर्क; कालिक (temporal) तर्क; होर तर्क (Hoare logic); मोडल तर्क; टाइप तर्क; फ़िक्स्ड-पॉइंट तर्क
6 और बातें
- प्रस्तावात्मक/विधेय तर्क
- कालिक (temporal) तर्क
- होर तर्क (Hoare logic)
- मोडल तर्क
- टाइप तर्क
- फ़िक्स्ड-पॉइंट तर्क
- SAT/SMT; प्रमेय सिद्ध करना (theorem proving); रिज़ॉल्यूशन; एकीकरण (unification); बाधा हल करना (constraint solving); संतुष्टि-योग्यता और मॉडल निर्माण
6 और बातें
- SAT/SMT
- प्रमेय सिद्ध करना (theorem proving)
- रिज़ॉल्यूशन
- एकीकरण (unification)
- बाधा हल करना (constraint solving)
- संतुष्टि-योग्यता और मॉडल निर्माण
- प्रस्तावात्मक/विधेय तर्क; कालिक (temporal) तर्क; होर तर्क (Hoare logic); मोडल तर्क; टाइप तर्क; फ़िक्स्ड-पॉइंट तर्क
- 7
प्रोग्राम विनिर्देश और प्रमाण
- पूर्व-शर्तें/पश्च-शर्तें; इनवेरिएंट; कॉन्ट्रैक्ट (शर्तें); परिष्कार (refinement); सबसे कमज़ोर पूर्व-शर्त (weakest precondition); समाप्ति का प्रमाण
6 और बातें
- पूर्व-शर्तें/पश्च-शर्तें
- इनवेरिएंट
- कॉन्ट्रैक्ट (शर्तें)
- परिष्कार (refinement)
- सबसे कमज़ोर पूर्व-शर्त (weakest precondition)
- समाप्ति का प्रमाण
- होर ट्रिपल; सेपरेशन लॉजिक; स्वामित्व/उधार (ownership/borrowing) पर तर्क; कार्यात्मक शुद्धता; गैर-कार्यात्मक गुण
5 और बातें
- होर ट्रिपल
- सेपरेशन लॉजिक
- स्वामित्व/उधार (ownership/borrowing) पर तर्क
- कार्यात्मक शुद्धता
- गैर-कार्यात्मक गुण
- पूर्व-शर्तें/पश्च-शर्तें; इनवेरिएंट; कॉन्ट्रैक्ट (शर्तें); परिष्कार (refinement); सबसे कमज़ोर पूर्व-शर्त (weakest precondition); समाप्ति का प्रमाण
- 8
सत्यापन की विधियाँ
- स्टैटिक विश्लेषण; प्रतीकात्मक निष्पादन (symbolic execution); अमूर्त व्याख्या (abstract interpretation); मॉडल चेकिंग; तुल्यता जाँच (equivalence checking); प्रूफ़ असिस्टेंट
6 और बातें
- स्टैटिक विश्लेषण
- प्रतीकात्मक निष्पादन (symbolic execution)
- अमूर्त व्याख्या (abstract interpretation)
- मॉडल चेकिंग
- तुल्यता जाँच (equivalence checking)
- प्रूफ़ असिस्टेंट
- टेस्ट बनाना; कवरेज-निर्देशित फ़ज़िंग; गुण-आधारित टेस्ट; रनटाइम सत्यापन; प्रमाण-सहित कोड (proof-carrying code)
5 और बातें
- टेस्ट बनाना
- कवरेज-निर्देशित फ़ज़िंग
- गुण-आधारित टेस्ट
- रनटाइम सत्यापन
- प्रमाण-सहित कोड (proof-carrying code)
- स्टैटिक विश्लेषण; प्रतीकात्मक निष्पादन (symbolic execution); अमूर्त व्याख्या (abstract interpretation); मॉडल चेकिंग; तुल्यता जाँच (equivalence checking); प्रूफ़ असिस्टेंट
- 9
विश्वसनीयता और आश्वासन
- सुरक्षा मामले (safety cases); ख़तरा विश्लेषण; फ़ॉल्ट ट्री; औपचारिक आवश्यकताएँ; अनुरेखणीयता; स्वतंत्र सत्यापन/वैधीकरण
6 और बातें
- सुरक्षा मामले (safety cases)
- ख़तरा विश्लेषण
- फ़ॉल्ट ट्री
- औपचारिक आवश्यकताएँ
- अनुरेखणीयता
- स्वतंत्र सत्यापन/वैधीकरण
- भरोसेमंद कंप्यूटिंग आधार (TCB); आश्वासन स्तर; समीक्षा के प्रमाण; दोबारा जाँचे जा सकने वाले प्रमाण और उपकरणों की सीमाएँ
4 और बातें
- भरोसेमंद कंप्यूटिंग आधार (TCB)
- आश्वासन स्तर
- समीक्षा के प्रमाण
- दोबारा जाँचे जा सकने वाले प्रमाण और उपकरणों की सीमाएँ
- सुरक्षा मामले (safety cases); ख़तरा विश्लेषण; फ़ॉल्ट ट्री; औपचारिक आवश्यकताएँ; अनुरेखणीयता; स्वतंत्र सत्यापन/वैधीकरण
