कंप्यूटर · भाग C - सॉफ़्टवेयर, एल्गोरिद्म (काम करने के क्रमवार नियम) और गणना · 39 में से मुख्य टॉपिक 9
एल्गोरिदम और डेटा संरचनाएँ
सही और कुशल विधियाँ, और जानकारी को व्यवस्थित करने वाली संरचनाएँ।
अंदर 176 चीज़ेंपढ़े गए RPSC/RSSB पेपरों में 1 बार पूछा गया, आख़िरी बार 2013 मेंCOM-09
इसे भी देखें: विज्ञान और प्रौद्योगिकी: कंप्यूटर संरचना, ऑपरेटिंग सिस्टम, प्रोग्रामिंग और सॉफ़्टवेयरविज्ञान और प्रौद्योगिकी: गणित, सांख्यिकी और डेटा की बुनियाद
- 1
ऐतिहासिक विकास — प्रमुख तिथियाँ
- यूक्लिड का एल्गोरिद्म एक क्लासिक सीमित विधि देता है।c. 300 BCE
- औपचारिक कंप्यूटेशन मॉडल एल्गोरिद्म और यांत्रिक विधि की सीमाएँ तय करते हैं।1930s
- इलेक्ट्रॉनिक कंप्यूटरों के लिए संख्यात्मक एल्गोरिद्म और सॉर्टिंग/सर्चिंग का अध्ययन होता है।1940s-1950s
- एल्गोरिद्म विश्लेषण, ग्राफ़, डायनेमिक प्रोग्रामिंग और जटिलता सिद्धांत परिपक्व होते हैं।1960s-1970s
- यादृच्छिक, सन्निकटन, ऑनलाइन और वितरित एल्गोरिद्म टूलकिट को बढ़ाते हैं।1980s-2000s
- विशाल डेटा, डीप लर्निंग, निजता, निष्पक्षता और तेज़ हार्डवेयर के लिए एल्गोरिद्म का महत्त्व बढ़ता है।2010s-2020s
- 2
एल्गोरिद्म का वर्णन
- सामान्य भाषा में चरण; फ़्लोचार्ट; स्यूडोकोड (कोड जैसी सरल भाषा); स्टेट बदलाव; पूर्व-शर्त/पश्च-शर्त; लूप इनवेरिएंट; समाप्ति
7 और बातें
- सामान्य भाषा में चरण
- फ़्लोचार्ट
- स्यूडोकोड (कोड जैसी सरल भाषा)
- स्टेट बदलाव
- पूर्व-शर्त/पश्च-शर्त
- लूप इनवेरिएंट
- समाप्ति
- इनपुट का दायरा; आउटपुट की शर्त (contract); सीमांत मामले (edge cases); शुद्धता का प्रमाण; ट्रेस; प्रति-उदाहरण
6 और बातें
- इनपुट का दायरा
- आउटपुट की शर्त (contract)
- सीमांत मामले (edge cases)
- शुद्धता का प्रमाण
- ट्रेस
- प्रति-उदाहरण
- सामान्य भाषा में चरण; फ़्लोचार्ट; स्यूडोकोड (कोड जैसी सरल भाषा); स्टेट बदलाव; पूर्व-शर्त/पश्च-शर्त; लूप इनवेरिएंट; समाप्ति
- 3
जटिलता विश्लेषण
- समय/स्थान जटिलता; सबसे अच्छा/औसत/सबसे बुरा मामला; अनंतस्पर्शी संकेतन O, Ω, Θ; निचली/ऊपरी सीमाएँ
4 और बातें
- समय/स्थान जटिलता
- सबसे अच्छा/औसत/सबसे बुरा मामला
- अनंतस्पर्शी संकेतन O, Ω, Θ
- निचली/ऊपरी सीमाएँ
- स्थिर/लघुगणकीय/रैखिक/रैखिक-लघुगणकीय/द्विघाती/घातांकीय/क्रमगुणित वृद्धि; परिशोधित (amortized) विश्लेषण
2 और बातें
- स्थिर/लघुगणकीय/रैखिक/रैखिक-लघुगणकीय/द्विघाती/घातांकीय/क्रमगुणित वृद्धि
- परिशोधित (amortized) विश्लेषण
- पुनरावृत्ति संबंध (recurrence relations); प्रतिस्थापन; रिकर्शन ट्री; मास्टर प्रमेय; पोटेंशियल विधि
5 और बातें
- पुनरावृत्ति संबंध (recurrence relations)
- प्रतिस्थापन
- रिकर्शन ट्री
- मास्टर प्रमेय
- पोटेंशियल विधि
- समय/स्थान जटिलता; सबसे अच्छा/औसत/सबसे बुरा मामला; अनंतस्पर्शी संकेतन O, Ω, Θ; निचली/ऊपरी सीमाएँ
- 4
रैखिक संरचनाएँ
- ऐरे; डायनेमिक ऐरे; लिंक्ड लिस्ट; सिंगली/डबली/सर्कुलर लिस्ट; स्टैक; क्यू (कतार); डेक (Deque); प्रायोरिटी क्यू
8 और बातें
- ऐरे
- डायनेमिक ऐरे
- लिंक्ड लिस्ट
- सिंगली/डबली/सर्कुलर लिस्ट
- स्टैक
- क्यू (कतार)
- डेक (Deque)
- प्रायोरिटी क्यू
- स्थिर बनाम गतिशील स्टोरेज; सूचीकरण (इंडेक्सिंग); ट्रैवर्सल (हर तत्व से गुज़रना); जोड़ना/हटाना; इटरेटर और उसका अमान्य होना
5 और बातें
- स्थिर बनाम गतिशील स्टोरेज
- सूचीकरण (इंडेक्सिंग)
- ट्रैवर्सल (हर तत्व से गुज़रना)
- जोड़ना/हटाना
- इटरेटर और उसका अमान्य होना
- ऐरे; डायनेमिक ऐरे; लिंक्ड लिस्ट; सिंगली/डबली/सर्कुलर लिस्ट; स्टैक; क्यू (कतार); डेक (Deque); प्रायोरिटी क्यू
- 5
पदानुक्रमित और साहचर्य (associative) संरचनाएँ
- राष्ट्रीय वृक्ष; बाइनरी ट्री; बाइनरी सर्च ट्री; AVL/रेड-ब्लैक ट्री; हीप; ट्राई (Trie); B/B+ ट्री; सेगमेंट ट्री; फ़ेनविक ट्री
9 और बातें
- राष्ट्रीय वृक्ष
- बाइनरी ट्री
- बाइनरी सर्च ट्री
- AVL/रेड-ब्लैक ट्री
- हीप
- ट्राई (Trie)
- B/B+ ट्री
- सेगमेंट ट्री
- फ़ेनविक ट्री
- हैश टेबल; हैश फ़ंक्शन; टकराव (collision) सँभालना; ओपन एड्रेसिंग; चेनिंग; लोड फ़ैक्टर; ब्लूम फ़िल्टर
7 और बातें
- हैश टेबल
- हैश फ़ंक्शन
- टकराव (collision) सँभालना
- ओपन एड्रेसिंग
- चेनिंग
- लोड फ़ैक्टर
- ब्लूम फ़िल्टर
- असंयुक्त समुच्चय संघ (disjoint-set union); यूनियन-फ़ाइंड; पाथ कम्प्रेशन; रैंक/आकार के आधार पर यूनियन
4 और बातें
- असंयुक्त समुच्चय संघ (disjoint-set union)
- यूनियन-फ़ाइंड
- पाथ कम्प्रेशन
- रैंक/आकार के आधार पर यूनियन
- राष्ट्रीय वृक्ष; बाइनरी ट्री; बाइनरी सर्च ट्री; AVL/रेड-ब्लैक ट्री; हीप; ट्राई (Trie); B/B+ ट्री; सेगमेंट ट्री; फ़ेनविक ट्री
- 6
ग्राफ़
- दिष्ट/अदिष्ट (directed/undirected); भारित/अभारित (weighted/unweighted); एडजेसेंसी मैट्रिक्स/लिस्ट; एज लिस्ट; डिग्री (कोटि); पथ; चक्र (cycle); संयोजकता (connectivity)
8 और बातें
- दिष्ट/अदिष्ट (directed/undirected)
- भारित/अभारित (weighted/unweighted)
- एडजेसेंसी मैट्रिक्स/लिस्ट
- एज लिस्ट
- डिग्री (कोटि)
- पथ
- चक्र (cycle)
- संयोजकता (connectivity)
- BFS (चौड़ाई-पहले खोज); DFS (गहराई-पहले खोज); टोपोलॉजिकल सॉर्टिंग; सबसे छोटा पथ; न्यूनतम स्पैनिंग ट्री; प्रबल रूप से जुड़े घटक (strongly connected components); प्रवाह/कट (flow/cut); मेल (काम और कामगार का)
8 और बातें
- BFS (चौड़ाई-पहले खोज)
- DFS (गहराई-पहले खोज)
- टोपोलॉजिकल सॉर्टिंग
- सबसे छोटा पथ
- न्यूनतम स्पैनिंग ट्री
- प्रबल रूप से जुड़े घटक (strongly connected components)
- प्रवाह/कट (flow/cut)
- मेल (काम और कामगार का)
- डाइक्स्ट्रा; बेलमैन-फ़ोर्ड; फ़्लॉयड-वॉर्शल; क्रुस्कल; प्रिम; अधिकतम-प्रवाह (max-flow) एल्गोरिद्म परिवार; ग्राफ़ रंगना
7 और बातें
- डाइक्स्ट्रा
- बेलमैन-फ़ोर्ड
- फ़्लॉयड-वॉर्शल
- क्रुस्कल
- प्रिम
- अधिकतम-प्रवाह (max-flow) एल्गोरिद्म परिवार
- ग्राफ़ रंगना
- दिष्ट/अदिष्ट (directed/undirected); भारित/अभारित (weighted/unweighted); एडजेसेंसी मैट्रिक्स/लिस्ट; एज लिस्ट; डिग्री (कोटि); पथ; चक्र (cycle); संयोजकता (connectivity)
- 7
सर्चिंग और सॉर्टिंग
- रैखिक/बाइनरी सर्च; हैश-आधारित खोज; इंटरपोलेशन और इंडेक्स वाली खोज की अवधारणाएँ
3 और बातें
- रैखिक/बाइनरी सर्च
- हैश-आधारित खोज
- इंटरपोलेशन और इंडेक्स वाली खोज की अवधारणाएँ
- बबल, सिलेक्शन, इंसर्शन, मर्ज, क्विक, हीप, काउंटिंग, रैडिक्स और बकेट सॉर्ट।
- स्थिरता; इन-प्लेस बनाम आउट-ऑफ़-प्लेस; तुलना-आधारित सॉर्ट की निचली सीमा; बाहरी (external) सॉर्टिंग; स्ट्रीमिंग में चयन
5 और बातें
- स्थिरता
- इन-प्लेस बनाम आउट-ऑफ़-प्लेस
- तुलना-आधारित सॉर्ट की निचली सीमा
- बाहरी (external) सॉर्टिंग
- स्ट्रीमिंग में चयन
- रैखिक/बाइनरी सर्च; हैश-आधारित खोज; इंटरपोलेशन और इंडेक्स वाली खोज की अवधारणाएँ
- 8
एल्गोरिद्म डिज़ाइन की शैलियाँ
- ब्रूट फ़ोर्स (सब कुछ आज़माना); बाँटो और जीतो (divide-and-conquer); लालची (greedy); डायनेमिक प्रोग्रामिंग; बैकट्रैकिंग (पीछे लौटकर खोजना); ब्रांच-एंड-बाउंड
6 और बातें
- ब्रूट फ़ोर्स (सब कुछ आज़माना)
- बाँटो और जीतो (divide-and-conquer)
- लालची (greedy)
- डायनेमिक प्रोग्रामिंग
- बैकट्रैकिंग (पीछे लौटकर खोजना)
- ब्रांच-एंड-बाउंड
- यादृच्छिक (randomized); सन्निकटन (approximation); ऑनलाइन; स्ट्रीमिंग; लोकल सर्च; ब्रांच प्रेडिक्शन को ध्यान में रखकर डिज़ाइन; समानांतर एल्गोरिद्म
7 और बातें
- यादृच्छिक (randomized)
- सन्निकटन (approximation)
- ऑनलाइन
- स्ट्रीमिंग
- लोकल सर्च
- ब्रांच प्रेडिक्शन को ध्यान में रखकर डिज़ाइन
- समानांतर एल्गोरिद्म
- ब्रूट फ़ोर्स (सब कुछ आज़माना); बाँटो और जीतो (divide-and-conquer); लालची (greedy); डायनेमिक प्रोग्रामिंग; बैकट्रैकिंग (पीछे लौटकर खोजना); ब्रांच-एंड-बाउंड
- 9
विशेष एल्गोरिदम वाली समस्याएँ
- स्ट्रिंग मिलान; एडिट दूरी; सफ़िक्स ऐरे/ट्री; संपीडन (compression); पार्सिंग; शेड्यूलिंग; रूटिंग; नैपसैक (थैला भरने की समस्या); उपसमुच्चय योग (subset sum)
9 और बातें
- स्ट्रिंग मिलान
- एडिट दूरी
- सफ़िक्स ऐरे/ट्री
- संपीडन (compression)
- पार्सिंग
- शेड्यूलिंग
- रूटिंग
- नैपसैक (थैला भरने की समस्या)
- उपसमुच्चय योग (subset sum)
- संख्यात्मक विधियाँ; ज्यामितीय एल्गोरिद्म; कम्प्यूटेशनल जीवविज्ञान; रिकमेंडर (सुझाव देने वाले) सिस्टम; ग्राफ़ माइनिंग
5 और बातें
- संख्यात्मक विधियाँ
- ज्यामितीय एल्गोरिद्म
- कम्प्यूटेशनल जीवविज्ञान
- रिकमेंडर (सुझाव देने वाले) सिस्टम
- ग्राफ़ माइनिंग
- स्ट्रिंग मिलान; एडिट दूरी; सफ़िक्स ऐरे/ट्री; संपीडन (compression); पार्सिंग; शेड्यूलिंग; रूटिंग; नैपसैक (थैला भरने की समस्या); उपसमुच्चय योग (subset sum)
- 10
शुद्धता और सत्यापन
- प्रेरण; लूप इनवेरिएंट; डेटा संरचनाओं के इनवेरिएंट; समाप्ति (termination) का प्रमाण; परिष्कार (refinement); मॉडल चेकिंग का परिचय
6 और बातें
- प्रेरण
- लूप इनवेरिएंट
- डेटा संरचनाओं के इनवेरिएंट
- समाप्ति (termination) का प्रमाण
- परिष्कार (refinement)
- मॉडल चेकिंग का परिचय
- गुण-आधारित (property-based) टेस्टिंग; फ़ज़िंग (बेतरतीब इनपुट से जाँच); तुलनात्मक (differential) टेस्टिंग; मेटामॉर्फ़िक टेस्टिंग; प्रतिकूल (adversarial) इनपुट
5 और बातें
- गुण-आधारित (property-based) टेस्टिंग
- फ़ज़िंग (बेतरतीब इनपुट से जाँच)
- तुलनात्मक (differential) टेस्टिंग
- मेटामॉर्फ़िक टेस्टिंग
- प्रतिकूल (adversarial) इनपुट
- प्रेरण; लूप इनवेरिएंट; डेटा संरचनाओं के इनवेरिएंट; समाप्ति (termination) का प्रमाण; परिष्कार (refinement); मॉडल चेकिंग का परिचय
- 11
उन्नत सिद्धांत और शोध
- P, NP, NP-पूर्णता, NP-कठोरता; अपचयन (reductions); अनिर्णेयता (undecidability); पैरामीटरयुक्त जटिलता
4 और बातें
- P, NP, NP-पूर्णता, NP-कठोरता
- अपचयन (reductions)
- अनिर्णेयता (undecidability)
- पैरामीटरयुक्त जटिलता
- यादृच्छिक जटिलता; सन्निकटन अनुपात; ऑनलाइन प्रतिस्पर्धी विश्लेषण; सूक्ष्म-स्तरीय (fine-grained) जटिलता; क्वांटम एल्गोरिद्म
5 और बातें
- यादृच्छिक जटिलता
- सन्निकटन अनुपात
- ऑनलाइन प्रतिस्पर्धी विश्लेषण
- सूक्ष्म-स्तरीय (fine-grained) जटिलता
- क्वांटम एल्गोरिद्म
- P, NP, NP-पूर्णता, NP-कठोरता; अपचयन (reductions); अनिर्णेयता (undecidability); पैरामीटरयुक्त जटिलता
