Ukraine 11 клас Informatics (profile level)
अध्याय: 4
1. Databases
Data modelling · Working with a relational DB
- संबंधपरक डेटाबेस: तालिकाएँ, पंक्तियाँ, स्तंभ और कीज़ – डेटा को कई अलग फ़ाइलों में रखने से डेटा दोहराता है, कॉपियाँ आपस में मेल नहीं खातीं और खोजना कठिन होता है, इसलिए हम DBMS से चलने वाला डेटाबेस उपयोग करते हैं। संबंधपरक मॉडल में डेटा रिलेशन कहलाने वाली तालिकाओं में रहता है। स्तंभ एट्रिब्यूट है, पंक्ति ट्यूपल है, और किसी स्तंभ के मान्य मानों का समूह उसका डोमेन है। स्तंभों की संख्या डिग्री है; पंक्तियों की संख्या कार्डिनैलिटी। कैंडिडेट की वह स्तंभ (या समूह) है जो हर पंक्ति को अलग पहचान सके; चुनी गई प्राइमरी की है और बाकी अल्टरनेट की। फ़ॉरेन की एक तालिका का वह स्तंभ है जो दूसरी तालिका की प्राइमरी की की ओर इशारा करके उन्हें जोड़ता है।
- कक्षा 12 के लिए SQL: तालिका बनाइए, प्रश्न पूछिए, तालिकाएँ जोड़िए – SQL संबंधपरक डेटाबेस बनाने और उनसे प्रश्न पूछने की भाषा है। DDL कमांड (CREATE, ALTER, DROP) ढाँचा बनाते हैं; DML कमांड (INSERT, UPDATE, DELETE) पंक्तियाँ बदलते हैं; SELECT डेटा पढ़ता है। स्तंभों को डेटा प्रकार (CHAR, VARCHAR, INT, FLOAT, DATE) और कंस्ट्रेंट (NOT NULL, UNIQUE, PRIMARY KEY, DEFAULT, FOREIGN KEY) मिलते हैं। SELECT में उपनाम (alias), DISTINCT, संबंधपरक और तार्किक ऑपरेटरों के साथ WHERE, IN, BETWEEN, LIKE, IS NULL और ORDER BY आते हैं। एग्रीगेट फ़ंक्शन (MAX, MIN, AVG, SUM, COUNT) कई पंक्तियों का सार देते हैं; GROUP BY समूह बनाता है और HAVING समूह छाँटता है। कार्टेशियन प्रोडक्ट एक तालिका की हर पंक्ति को दूसरी की हर पंक्ति से जोड़ता है; इक्वी-जॉइन केवल वे जोड़े रखता है जिनका साझा स्तंभ मेल खाए; नेचुरल जॉइन भी यही करता है पर साझा स्तंभ एक बार दिखाता है।
2. Algorithms
Algorithm design and complexity · Number theory · Sorting and searching · Strings and graphs · Advanced techniques · Computational geometry
- एल्गोरिदम कॉम्प्लेक्सिटी: एल्गोरिदम कितनी तेज़ी से बढ़ता है? – एक ही सवाल को कई एल्गोरिदम हल कर सकते हैं, पर कुछ बहुत ज़्यादा कदम लेते हैं। हम घड़ी के सेकंड नहीं, बल्कि इनपुट के आकार n के साथ बढ़ते कदम गिनते हैं। बिग O इस बढ़त का नाम है: O(1) स्थिर, O(log n), O(n) रैखिक, O(n log n) और O(n²)। लीनियर सर्च O(n), बाइनरी सर्च O(log n); बबल सॉर्ट O(n²), मर्ज सॉर्ट O(n log n)। मेमोरी की बढ़त = स्पेस कॉम्प्लेक्सिटी।
- सॉर्टिंग एल्गोरिदम (छाँटने के तरीक़े) – सॉर्टिंग एल्गोरिदम किसी सूची को क्रम में लगाता है। बबल सॉर्ट पड़ोसियों की अदला-बदली करता है, इंसर्शन सॉर्ट हर चीज़ को छँटे हिस्से में सही जगह खिसकाता है, सिलेक्शन सॉर्ट हर बार सबसे छोटा चुनता है, और मर्ज सॉर्ट सूची को तोड़कर छँटे हिस्से जोड़ता है। लंबी सूची पर मर्ज सॉर्ट बहुत कम तुलनाएँ करता है (लगभग n²/2 की जगह n log₂ n)।
- ग्राफ़ एल्गोरिद्म – ग्राफ़ शीर्षों (vertices) का समूह है जो किनारों (edges) से जुड़े होते हैं, और किनारों पर भार हो सकता है। चौड़ाई-प्रथम खोज (BFS) कतार से परत-दर-परत खोजती है और सबसे कम किनारों वाला रास्ता देती है। गहराई-प्रथम खोज (DFS) ढेर या रिकर्शन से गहराई में जाती है और लौटती है। ट्री को प्री-ऑर्डर, इन-ऑर्डर और पोस्ट-ऑर्डर में घूमा जाता है। डाइक्स्ट्रा एल्गोरिद्म ग़ैर-ऋणात्मक भार पर एक शीर्ष से सबसे छोटे रास्ते देता है। क्रुस्कल और प्रिम न्यूनतम स्पैनिंग ट्री बनाते हैं। रूट इंस्पेक्शन हर किनारे पर चलने वाला सबसे छोटा बंद रास्ता ढूँढ़ता है; ट्रैवलिंग सेल्सपर्सन हर शीर्ष का सबसे छोटा चक्कर। प्रवाह नेटवर्क में अधिकतम प्रवाह = न्यूनतम कट की क्षमता।
- डायनामिक प्रोग्रामिंग (Dynamic Programming) – डायनामिक प्रोग्रामिंग (DP) बड़ी समस्या को हल करते समय हर छोटी उपसमस्या को केवल एक बार हल करके उत्तर सहेज लेती है। यह तब काम करती है जब उपसमस्याएँ दोहराती हों और बड़ा सबसे अच्छा उत्तर छोटे सबसे अच्छे उत्तरों से बने (इष्टतम उपसंरचना)। ऊपर से नीचे DP मेमोइज़ेशन है; नीचे से ऊपर DP तालिका भरती है। DP अक्सर घातांकी समय को बहुपद समय बना देती है।
3. Web technologies
Web design and development
- वेब डेवलपमेंट: HTML, CSS और JavaScript से वेब पेज कैसे बनता है – वेब पेज कुछ टेक्स्ट फ़ाइलों से बनता है। ब्राउज़र (क्लाइंट) URL और HTTP से सर्वर से ये फ़ाइलें माँगता है। HTML पेज का ढाँचा बनाता है: हेडिंग, पैराग्राफ़, लिंक, चित्र, सूची, टेबल और फ़ॉर्म। CSS सजावट देता है: रंग, फ़ॉन्ट, दूरी और लेआउट। JavaScript व्यवहार देता है: क्लिक पर पेज बदलता है। रिस्पॉन्सिव डिज़ाइन से एक ही पेज फ़ोन और कंप्यूटर दोनों पर ठीक दिखता है।
4. Programming paradigms and technologies
Software engineering process
- सॉफ़्टवेयर विकास: विचार से चलते ऐप तक – अच्छा सॉफ़्टवेयर चरणों में बनता है: समस्या का विश्लेषण करके आवश्यकताएँ लिखो, हल डिज़ाइन करो, छोटे हिस्सों में कोड करो, सामान्य, सीमा और गलत डेटा से परीक्षण करो, उपयोगकर्ताओं तक पहुँचाओ और रखरखाव करो। वॉटरफ़ॉल हर चरण एक बार क्रम से करता है; एजाइल छोटे चक्र दोहराता है। मज़बूत प्रोग्राम इनपुट जाँचते हैं, और टीमें वर्ज़न कंट्रोल, साफ़ भूमिकाएँ और उपयोगकर्ता की राय इस्तेमाल करती हैं।