Romania Clasa a XI-a Computer Science (intensive informatics)
अध्याय: 5
1. Dynamic data structures
Dynamically allocated structures
- लिंक्ड लिस्ट (Linked List) – लिंक्ड लिस्ट चीज़ों को नोड में रखती है। हर नोड में डेटा और एक पॉइंटर (अगले नोड का पता) होता है। head नाम का वेरिएबल पहले नोड को दिखाता है; आख़िरी नोड NULL को दिखाता है। नोड मेमोरी में कहीं भी हो सकते हैं, इसलिए शुरू में जोड़ना-हटाना बस पॉइंटर बदलना है, पर k-वाँ आइटम ढूँढने के लिए head से चलना पड़ता है।
2. Graphs
Terminology and special graphs · Graph algorithms
- ग्राफ़ सिद्धांत: बिंदु, रेखाएँ और नेटवर्क – ग्राफ़ शीर्षों (बिंदुओं) का समूह है जिन्हें किनारे (रेखाएँ) जोड़ते हैं। किसी शीर्ष की घात उसे छूने वाले किनारों की संख्या है, और सभी घातों का योग किनारों का दुगुना होता है। ऑयलर पथ हर किनारे का एक बार उपयोग करता है और तभी संभव है जब 0 या 2 शीर्ष विषम घात के हों। वृक्ष ऐसा जुड़ा ग्राफ़ है जिसमें चक्र नहीं और n − 1 किनारे हैं। भारित ग्राफ़ सड़कें और नेटवर्क दिखाते हैं; क्रुस्कल और प्रिम विधियाँ न्यूनतम विस्तृत वृक्ष ढूँढती हैं।
- ग्राफ़ एल्गोरिद्म – ग्राफ़ शीर्षों (vertices) का समूह है जो किनारों (edges) से जुड़े होते हैं, और किनारों पर भार हो सकता है। चौड़ाई-प्रथम खोज (BFS) कतार से परत-दर-परत खोजती है और सबसे कम किनारों वाला रास्ता देती है। गहराई-प्रथम खोज (DFS) ढेर या रिकर्शन से गहराई में जाती है और लौटती है। ट्री को प्री-ऑर्डर, इन-ऑर्डर और पोस्ट-ऑर्डर में घूमा जाता है। डाइक्स्ट्रा एल्गोरिद्म ग़ैर-ऋणात्मक भार पर एक शीर्ष से सबसे छोटे रास्ते देता है। क्रुस्कल और प्रिम न्यूनतम स्पैनिंग ट्री बनाते हैं। रूट इंस्पेक्शन हर किनारे पर चलने वाला सबसे छोटा बंद रास्ता ढूँढ़ता है; ट्रैवलिंग सेल्सपर्सन हर शीर्ष का सबसे छोटा चक्कर। प्रवाह नेटवर्क में अधिकतम प्रवाह = न्यूनतम कट की क्षमता।
3. Trees
Rooted and binary trees
- डेटा स्ट्रक्चर में ट्री: बाइनरी ट्री और बाइनरी सर्च ट्री – ट्री डेटा को नोड्स में रखता है जो किनारों (edges) से जुड़े होते हैं, जैसे उल्टा खड़ा वंश-वृक्ष। सबसे ऊपर वाला नोड रूट (मूल) है, जिनके बच्चे नहीं वे लीफ (पत्ती) हैं। n नोड वाले ट्री में n − 1 किनारे होते हैं। नोड की गहराई = रूट से उसकी दूरी (किनारों में); ट्री की ऊँचाई = रूट से पत्ती तक सबसे लंबा रास्ता। बाइनरी ट्री में हर नोड के अधिकतम दो बच्चे होते हैं। बाइनरी सर्च ट्री (BST) में छोटी कुंजियाँ बाएँ, बड़ी दाएँ रहती हैं, इसलिए खोज हर कदम पर आधा ट्री छोड़ देती है। ट्रैवर्सल हर नोड पर जाता है: प्री-ऑर्डर (रूट, बायाँ, दायाँ), इन-ऑर्डर (बायाँ, रूट, दायाँ), पोस्ट-ऑर्डर (बायाँ, दायाँ, रूट)। BST पर इन-ऑर्डर क्रमबद्ध (sorted) आउटपुट देता है।
4. Programming methods
Greedy, backtracking, divide and conquer, dynamic programming
- डायनामिक प्रोग्रामिंग (Dynamic Programming) – डायनामिक प्रोग्रामिंग (DP) बड़ी समस्या को हल करते समय हर छोटी उपसमस्या को केवल एक बार हल करके उत्तर सहेज लेती है। यह तब काम करती है जब उपसमस्याएँ दोहराती हों और बड़ा सबसे अच्छा उत्तर छोटे सबसे अच्छे उत्तरों से बने (इष्टतम उपसंरचना)। ऊपर से नीचे DP मेमोइज़ेशन है; नीचे से ऊपर DP तालिका भरती है। DP अक्सर घातांकी समय को बहुपद समय बना देती है।
5. Object-oriented programming
OOP basics
- ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग (OOP) – ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग में प्रोग्राम ऑब्जेक्ट्स से बनता है। क्लास एक ब्लूप्रिंट है जो बताता है कि उसके ऑब्जेक्ट्स के पास कौन-सा डेटा (एट्रिब्यूट) और कौन-से काम (मेथड) होंगे। हर ऑब्जेक्ट क्लास से बनता है और अपना डेटा ख़ुद रखता है। चार बड़े विचार हैं: एनकैप्सुलेशन (डेटा को मेथड के पीछे छिपाना), इनहेरिटेंस (नई क्लास पुरानी को दोबारा इस्तेमाल करे), पॉलीमॉर्फ़िज़्म (एक ही मेथड हर ऑब्जेक्ट के लिए सही ढंग से चले) और एब्स्ट्रैक्शन (ज़रूरी चीज़ ही दिखाना)।