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

एल्गोरिदम और डेटा संरचनाएँ

सही और कुशल विधियाँ, और जानकारी को व्यवस्थित करने वाली संरचनाएँ।

अंदर 176 चीज़ेंपढ़े गए RPSC/RSSB पेपरों में 1 बार पूछा गया, आख़िरी बार 2013 मेंCOM-09

इसे भी देखें: विज्ञान और प्रौद्योगिकी: कंप्यूटर संरचना, ऑपरेटिंग सिस्टम, प्रोग्रामिंग और सॉफ़्टवेयरविज्ञान और प्रौद्योगिकी: गणित, सांख्यिकी और डेटा की बुनियाद

  1. 1

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

    • यूक्लिड का एल्गोरिद्म एक क्लासिक सीमित विधि देता है।c. 300 BCE
    • औपचारिक कंप्यूटेशन मॉडल एल्गोरिद्म और यांत्रिक विधि की सीमाएँ तय करते हैं।1930s
    • इलेक्ट्रॉनिक कंप्यूटरों के लिए संख्यात्मक एल्गोरिद्म और सॉर्टिंग/सर्चिंग का अध्ययन होता है।1940s-1950s
    • एल्गोरिद्म विश्लेषण, ग्राफ़, डायनेमिक प्रोग्रामिंग और जटिलता सिद्धांत परिपक्व होते हैं।1960s-1970s
    • यादृच्छिक, सन्निकटन, ऑनलाइन और वितरित एल्गोरिद्म टूलकिट को बढ़ाते हैं।1980s-2000s
    • विशाल डेटा, डीप लर्निंग, निजता, निष्पक्षता और तेज़ हार्डवेयर के लिए एल्गोरिद्म का महत्त्व बढ़ता है।2010s-2020s
  2. 2

    एल्गोरिद्म का वर्णन

    • सामान्य भाषा में चरण; फ़्लोचार्ट; स्यूडोकोड (कोड जैसी सरल भाषा); स्टेट बदलाव; पूर्व-शर्त/पश्च-शर्त; लूप इनवेरिएंट; समाप्ति
      7 और बातें
      • सामान्य भाषा में चरण
      • फ़्लोचार्ट
      • स्यूडोकोड (कोड जैसी सरल भाषा)
      • स्टेट बदलाव
      • पूर्व-शर्त/पश्च-शर्त
      • लूप इनवेरिएंट
      • समाप्ति
    • इनपुट का दायरा; आउटपुट की शर्त (contract); सीमांत मामले (edge cases); शुद्धता का प्रमाण; ट्रेस; प्रति-उदाहरण
      6 और बातें
      • इनपुट का दायरा
      • आउटपुट की शर्त (contract)
      • सीमांत मामले (edge cases)
      • शुद्धता का प्रमाण
      • ट्रेस
      • प्रति-उदाहरण
  3. 3

    जटिलता विश्लेषण

    • समय/स्थान जटिलता; सबसे अच्छा/औसत/सबसे बुरा मामला; अनंतस्पर्शी संकेतन O, Ω, Θ; निचली/ऊपरी सीमाएँ
      4 और बातें
      • समय/स्थान जटिलता
      • सबसे अच्छा/औसत/सबसे बुरा मामला
      • अनंतस्पर्शी संकेतन O, Ω, Θ
      • निचली/ऊपरी सीमाएँ
    • स्थिर/लघुगणकीय/रैखिक/रैखिक-लघुगणकीय/द्विघाती/घातांकीय/क्रमगुणित वृद्धि; परिशोधित (amortized) विश्लेषण
      2 और बातें
      • स्थिर/लघुगणकीय/रैखिक/रैखिक-लघुगणकीय/द्विघाती/घातांकीय/क्रमगुणित वृद्धि
      • परिशोधित (amortized) विश्लेषण
    • पुनरावृत्ति संबंध (recurrence relations); प्रतिस्थापन; रिकर्शन ट्री; मास्टर प्रमेय; पोटेंशियल विधि
      5 और बातें
      • पुनरावृत्ति संबंध (recurrence relations)
      • प्रतिस्थापन
      • रिकर्शन ट्री
      • मास्टर प्रमेय
      • पोटेंशियल विधि
  4. 4

    रैखिक संरचनाएँ

    • ऐरे; डायनेमिक ऐरे; लिंक्ड लिस्ट; सिंगली/डबली/सर्कुलर लिस्ट; स्टैक; क्यू (कतार); डेक (Deque); प्रायोरिटी क्यू
      8 और बातें
      • ऐरे
      • डायनेमिक ऐरे
      • लिंक्ड लिस्ट
      • सिंगली/डबली/सर्कुलर लिस्ट
      • स्टैक
      • क्यू (कतार)
      • डेक (Deque)
      • प्रायोरिटी क्यू
    • स्थिर बनाम गतिशील स्टोरेज; सूचीकरण (इंडेक्सिंग); ट्रैवर्सल (हर तत्व से गुज़रना); जोड़ना/हटाना; इटरेटर और उसका अमान्य होना
      5 और बातें
      • स्थिर बनाम गतिशील स्टोरेज
      • सूचीकरण (इंडेक्सिंग)
      • ट्रैवर्सल (हर तत्व से गुज़रना)
      • जोड़ना/हटाना
      • इटरेटर और उसका अमान्य होना
  5. 5

    पदानुक्रमित और साहचर्य (associative) संरचनाएँ

    • राष्ट्रीय वृक्ष; बाइनरी ट्री; बाइनरी सर्च ट्री; AVL/रेड-ब्लैक ट्री; हीप; ट्राई (Trie); B/B+ ट्री; सेगमेंट ट्री; फ़ेनविक ट्री
      9 और बातें
      • राष्ट्रीय वृक्ष
      • बाइनरी ट्री
      • बाइनरी सर्च ट्री
      • AVL/रेड-ब्लैक ट्री
      • हीप
      • ट्राई (Trie)
      • B/B+ ट्री
      • सेगमेंट ट्री
      • फ़ेनविक ट्री
    • हैश टेबल; हैश फ़ंक्शन; टकराव (collision) सँभालना; ओपन एड्रेसिंग; चेनिंग; लोड फ़ैक्टर; ब्लूम फ़िल्टर
      7 और बातें
      • हैश टेबल
      • हैश फ़ंक्शन
      • टकराव (collision) सँभालना
      • ओपन एड्रेसिंग
      • चेनिंग
      • लोड फ़ैक्टर
      • ब्लूम फ़िल्टर
    • असंयुक्त समुच्चय संघ (disjoint-set union); यूनियन-फ़ाइंड; पाथ कम्प्रेशन; रैंक/आकार के आधार पर यूनियन
      4 और बातें
      • असंयुक्त समुच्चय संघ (disjoint-set union)
      • यूनियन-फ़ाइंड
      • पाथ कम्प्रेशन
      • रैंक/आकार के आधार पर यूनियन
  6. 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) एल्गोरिद्म परिवार
      • ग्राफ़ रंगना
  7. 7

    सर्चिंग और सॉर्टिंग

    • रैखिक/बाइनरी सर्च; हैश-आधारित खोज; इंटरपोलेशन और इंडेक्स वाली खोज की अवधारणाएँ
      3 और बातें
      • रैखिक/बाइनरी सर्च
      • हैश-आधारित खोज
      • इंटरपोलेशन और इंडेक्स वाली खोज की अवधारणाएँ
    • बबल, सिलेक्शन, इंसर्शन, मर्ज, क्विक, हीप, काउंटिंग, रैडिक्स और बकेट सॉर्ट।
    • स्थिरता; इन-प्लेस बनाम आउट-ऑफ़-प्लेस; तुलना-आधारित सॉर्ट की निचली सीमा; बाहरी (external) सॉर्टिंग; स्ट्रीमिंग में चयन
      5 और बातें
      • स्थिरता
      • इन-प्लेस बनाम आउट-ऑफ़-प्लेस
      • तुलना-आधारित सॉर्ट की निचली सीमा
      • बाहरी (external) सॉर्टिंग
      • स्ट्रीमिंग में चयन
  8. 8

    एल्गोरिद्म डिज़ाइन की शैलियाँ

    • ब्रूट फ़ोर्स (सब कुछ आज़माना); बाँटो और जीतो (divide-and-conquer); लालची (greedy); डायनेमिक प्रोग्रामिंग; बैकट्रैकिंग (पीछे लौटकर खोजना); ब्रांच-एंड-बाउंड
      6 और बातें
      • ब्रूट फ़ोर्स (सब कुछ आज़माना)
      • बाँटो और जीतो (divide-and-conquer)
      • लालची (greedy)
      • डायनेमिक प्रोग्रामिंग
      • बैकट्रैकिंग (पीछे लौटकर खोजना)
      • ब्रांच-एंड-बाउंड
    • यादृच्छिक (randomized); सन्निकटन (approximation); ऑनलाइन; स्ट्रीमिंग; लोकल सर्च; ब्रांच प्रेडिक्शन को ध्यान में रखकर डिज़ाइन; समानांतर एल्गोरिद्म
      7 और बातें
      • यादृच्छिक (randomized)
      • सन्निकटन (approximation)
      • ऑनलाइन
      • स्ट्रीमिंग
      • लोकल सर्च
      • ब्रांच प्रेडिक्शन को ध्यान में रखकर डिज़ाइन
      • समानांतर एल्गोरिद्म
  9. 9

    विशेष एल्गोरिदम वाली समस्याएँ

    1 बार पूछा गया · आख़िरी बार 2013

    • स्ट्रिंग मिलान; एडिट दूरी; सफ़िक्स ऐरे/ट्री; संपीडन (compression); पार्सिंग; शेड्यूलिंग; रूटिंग; नैपसैक (थैला भरने की समस्या); उपसमुच्चय योग (subset sum)
      9 और बातें
      • स्ट्रिंग मिलान
      • एडिट दूरी
      • सफ़िक्स ऐरे/ट्री
      • संपीडन (compression)
      • पार्सिंग
      • शेड्यूलिंग
      • रूटिंग
      • नैपसैक (थैला भरने की समस्या)
      • उपसमुच्चय योग (subset sum)
    • संख्यात्मक विधियाँ; ज्यामितीय एल्गोरिद्म; कम्प्यूटेशनल जीवविज्ञान; रिकमेंडर (सुझाव देने वाले) सिस्टम; ग्राफ़ माइनिंग
      5 और बातें
      • संख्यात्मक विधियाँ
      • ज्यामितीय एल्गोरिद्म
      • कम्प्यूटेशनल जीवविज्ञान
      • रिकमेंडर (सुझाव देने वाले) सिस्टम
      • ग्राफ़ माइनिंग
  10. 10

    शुद्धता और सत्यापन

    • प्रेरण; लूप इनवेरिएंट; डेटा संरचनाओं के इनवेरिएंट; समाप्ति (termination) का प्रमाण; परिष्कार (refinement); मॉडल चेकिंग का परिचय
      6 और बातें
      • प्रेरण
      • लूप इनवेरिएंट
      • डेटा संरचनाओं के इनवेरिएंट
      • समाप्ति (termination) का प्रमाण
      • परिष्कार (refinement)
      • मॉडल चेकिंग का परिचय
    • गुण-आधारित (property-based) टेस्टिंग; फ़ज़िंग (बेतरतीब इनपुट से जाँच); तुलनात्मक (differential) टेस्टिंग; मेटामॉर्फ़िक टेस्टिंग; प्रतिकूल (adversarial) इनपुट
      5 और बातें
      • गुण-आधारित (property-based) टेस्टिंग
      • फ़ज़िंग (बेतरतीब इनपुट से जाँच)
      • तुलनात्मक (differential) टेस्टिंग
      • मेटामॉर्फ़िक टेस्टिंग
      • प्रतिकूल (adversarial) इनपुट
  11. 11

    उन्नत सिद्धांत और शोध

    • P, NP, NP-पूर्णता, NP-कठोरता; अपचयन (reductions); अनिर्णेयता (undecidability); पैरामीटरयुक्त जटिलता
      4 और बातें
      • P, NP, NP-पूर्णता, NP-कठोरता
      • अपचयन (reductions)
      • अनिर्णेयता (undecidability)
      • पैरामीटरयुक्त जटिलता
    • यादृच्छिक जटिलता; सन्निकटन अनुपात; ऑनलाइन प्रतिस्पर्धी विश्लेषण; सूक्ष्म-स्तरीय (fine-grained) जटिलता; क्वांटम एल्गोरिद्म
      5 और बातें
      • यादृच्छिक जटिलता
      • सन्निकटन अनुपात
      • ऑनलाइन प्रतिस्पर्धी विश्लेषण
      • सूक्ष्म-स्तरीय (fine-grained) जटिलता
      • क्वांटम एल्गोरिद्म