National Year 13 Computer Science

अध्याय: 11

1. 4.1 Fundamentals of programming (A-level)

Pointer data type · Stack frames and recursion · Object-oriented programming

प्रोग्रामिंग की मूल बातें: अनुक्रम, चयन, लूप और फ़ंक्शन – प्रोग्राम सटीक निर्देशों का समूह है जिसे कंप्यूटर मानता है। हर प्रोग्राम तीन संरचनाओं से बनता है: अनुक्रम (क्रम से कदम), चयन (if/else से चुनाव) और पुनरावृत्ति (लूप)। चर मान संभालकर रखते हैं। फ़ंक्शन कोड को नाम वाले, दोबारा इस्तेमाल होने वाले खंडों में बाँटते हैं, जिससे प्रोग्राम मॉड्यूलर बनता है और उसे जाँचना, सुधारना और सँभालना आसान होता है।
रिकर्शन: ख़ुद को पुकारने वाले फ़ंक्शन – रिकर्शन (recursion) तब होता है जब कोई फ़ंक्शन किसी प्रश्न को हल करने के लिए उसी प्रश्न के छोटे रूप पर ख़ुद को पुकारता है। हर रिकर्सिव फ़ंक्शन में एक आधार स्थिति (base case) चाहिए, जहाँ वह रुककर सीधे उत्तर देता है, और एक रिकर्सिव स्थिति जो आधार स्थिति की ओर बढ़ती है। हर पुकार को कॉल स्टैक पर अपना स्टैक फ़्रेम मिलता है; पुकार लौटने पर फ़्रेम हट जाता है।
ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग (OOP) – ऑब्जेक्ट ओरिएंटेड प्रोग्रामिंग में प्रोग्राम ऑब्जेक्ट्स से बनता है। क्लास एक ब्लूप्रिंट है जो बताता है कि उसके ऑब्जेक्ट्स के पास कौन-सा डेटा (एट्रिब्यूट) और कौन-से काम (मेथड) होंगे। हर ऑब्जेक्ट क्लास से बनता है और अपना डेटा ख़ुद रखता है। चार बड़े विचार हैं: एनकैप्सुलेशन (डेटा को मेथड के पीछे छिपाना), इनहेरिटेंस (नई क्लास पुरानी को दोबारा इस्तेमाल करे), पॉलीमॉर्फ़िज़्म (एक ही मेथड हर ऑब्जेक्ट के लिए सही ढंग से चले) और एब्स्ट्रैक्शन (ज़रूरी चीज़ ही दिखाना)।

2. 4.2 Fundamentals of data structures (A-level)

Abstract data types

डेटा संरचना: ऐरे, लिस्ट, स्टैक, क्यू और ट्री – डेटा संरचना मेमोरी में डेटा को ऐसे जमाने का तरीका है कि प्रोग्राम उसे अच्छे से इस्तेमाल कर सके। ऐरे चीज़ों को क्रमांकित डिब्बों में रखता है ताकि सूचकांक से तुरंत पहुँच हो। लिंक्ड लिस्ट नोड्स को पॉइंटर से जोड़ती है, इसलिए बीच में डालना आसान है। स्टैक LIFO (अंतिम आया, पहले गया) और क्यू FIFO (पहले आया, पहले गया) पर चलते हैं। डिक्शनरी कुंजी (key) से मान खोजती है और ट्री डेटा को स्तरों में रखता है ताकि खोज तेज़ हो।

3. 4.3 Fundamentals of algorithms

Traversals · Reverse Polish notation · Searching and sorting · Optimisation

ग्राफ़ एल्गोरिद्म – ग्राफ़ शीर्षों (vertices) का समूह है जो किनारों (edges) से जुड़े होते हैं, और किनारों पर भार हो सकता है। चौड़ाई-प्रथम खोज (BFS) कतार से परत-दर-परत खोजती है और सबसे कम किनारों वाला रास्ता देती है। गहराई-प्रथम खोज (DFS) ढेर या रिकर्शन से गहराई में जाती है और लौटती है। ट्री को प्री-ऑर्डर, इन-ऑर्डर और पोस्ट-ऑर्डर में घूमा जाता है। डाइक्स्ट्रा एल्गोरिद्म ग़ैर-ऋणात्मक भार पर एक शीर्ष से सबसे छोटे रास्ते देता है। क्रुस्कल और प्रिम न्यूनतम स्पैनिंग ट्री बनाते हैं। रूट इंस्पेक्शन हर किनारे पर चलने वाला सबसे छोटा बंद रास्ता ढूँढ़ता है; ट्रैवलिंग सेल्सपर्सन हर शीर्ष का सबसे छोटा चक्कर। प्रवाह नेटवर्क में अधिकतम प्रवाह = न्यूनतम कट की क्षमता।
डेटा संरचना: ऐरे, लिस्ट, स्टैक, क्यू और ट्री – डेटा संरचना मेमोरी में डेटा को ऐसे जमाने का तरीका है कि प्रोग्राम उसे अच्छे से इस्तेमाल कर सके। ऐरे चीज़ों को क्रमांकित डिब्बों में रखता है ताकि सूचकांक से तुरंत पहुँच हो। लिंक्ड लिस्ट नोड्स को पॉइंटर से जोड़ती है, इसलिए बीच में डालना आसान है। स्टैक LIFO (अंतिम आया, पहले गया) और क्यू FIFO (पहले आया, पहले गया) पर चलते हैं। डिक्शनरी कुंजी (key) से मान खोजती है और ट्री डेटा को स्तरों में रखता है ताकि खोज तेज़ हो।
खोज (Searching) और छँटाई (Sorting) एल्गोरिदम – खोज एल्गोरिदम सूची में कोई चीज़ ढूँढता है; छँटाई एल्गोरिदम सूची को क्रम में लगाता है। रेखीय खोज एक-एक करके देखती है और किसी भी सूची पर चलती है। द्विआधारी खोज छँटी सूची को हर बार आधा करती है और बहुत तेज़ है। बबल सॉर्ट पड़ोसियों की अदला-बदली करता है; मर्ज सॉर्ट सूची तोड़कर छँटे टुकड़े जोड़ता है, जो बड़ी सूचियों में तेज़ है।

4. 4.4 Theory of computation (A-level)

Regular languages · Context-free languages · Classification of algorithms · Turing machine

परिमित अवस्था मशीन और औपचारिक भाषाएँ – परिमित अवस्था मशीन (FSM) में अवस्थाओं का एक सीमित समूह, इनपुट चिह्नों की वर्णमाला, एक आरंभ अवस्था, हर चिह्न पर अगली अवस्था बताने वाला संक्रमण नियम, और (स्वीकारक के लिए) स्वीकार अवस्थाएँ होती हैं। यह इनपुट स्ट्रिंग को एक-एक चिह्न पढ़ती है; अंत में स्वीकार अवस्था में हो तो स्ट्रिंग स्वीकार। मीली मशीन हर संक्रमण पर आउटपुट भी देती है। FSM जिन स्ट्रिंग्स को स्वीकार करती है वे रेगुलर भाषा बनाती हैं, जिसे रेगुलर एक्सप्रेशन से भी लिखा जा सकता है। कोष्ठकों जैसी नेस्टिंग वाली भाषाएँ कॉन्टेक्स्ट-फ़्री हैं और BNF नियमों या सिंटैक्स आरेख से लिखी जाती हैं।
संगणनात्मक जटिलता: आसान, कठिन और असंभव समस्याएँ – जटिलता बताती है कि इनपुट का आकार n बढ़ने पर कदम कितनी तेज़ी से बढ़ते हैं। बहुपद (n, n², n³) एल्गोरिदम संभालने लायक (ट्रैक्टेबल) हैं; घातीय (2ⁿ) और क्रमगुणित (n!) बहुत जल्दी बेकाबू हो जाते हैं। कुछ समस्याएँ जाँचने में आसान पर हल करने में कठिन (NP) हैं। हॉल्टिंग समस्या जैसी कुछ समस्याएँ किसी एल्गोरिदम से हल ही नहीं हो सकतीं।
संगणनीयता (Computability): ट्यूरिंग मशीन और कंप्यूटर की सीमाएँ – ट्यूरिंग मशीन किसी भी कंप्यूटर का सरल मॉडल है: खानों वाला अनंत टेप, एक हेड जो एक बार में एक खाना पढ़ता-लिखता है, कुछ अवस्थाएँ (states) और संक्रमण नियमों की तालिका। जो कुछ एल्गोरिद्म गणना कर सकता है, ट्यूरिंग मशीन भी कर सकती है (चर्च-ट्यूरिंग थीसिस)। सार्वभौमिक ट्यूरिंग मशीन दूसरी मशीन के नियम टेप से पढ़कर उसे चलाती है। कुछ समस्याएँ, जैसे हॉल्टिंग समस्या, कोई भी एल्गोरिद्म कभी हल नहीं कर सकता: वे असंगणनीय (अनिर्णेय) हैं।

5. 4.5 Data representation (A-level)

Floating point · Vector graphics

संख्या पद्धति और कूटन (Encoding) – संख्या पद्धति अंकों और आधार से संख्याएँ लिखने का तरीका है। दशमलव (आधार 10) में 0–9, बाइनरी (आधार 2) में 0 और 1, ऑक्टल (आधार 8) में 0–7, और हेक्साडेसिमल (आधार 16) में 0–9 और A–F। दशमलव से किसी आधार में: आधार से बार-बार भाग देकर शेष नीचे से ऊपर पढ़ें; भिन्न भाग के लिए आधार से गुणा करके पूर्णांक ऊपर से नीचे पढ़ें। दशमलव में: हर अंक × स्थानीय मान, फिर जोड़ें। बाइनरी ↔ ऑक्टल में 3 बिट के समूह, बाइनरी ↔ हेक्स में 4 बिट के। टेक्स्ट कूटन से रखा जाता है: ASCII (7 बिट, 128 अक्षर), ISCII (8 बिट, भारतीय लिपियाँ) और यूनिकोड (हर लिपि), जो UTF-8 (1–4 बाइट) या UTF-32 (4 बाइट) में सहेजा जाता है।
डेटा निरूपण: कंप्यूटर संख्या, अक्षर, चित्र और आवाज़ कैसे रखता है – डेटा कच्चे तथ्य हैं; अर्थ मिलने पर वह सूचना (information) बनता है; जिस सूचना से हम काम ले सकें वह ज्ञान है। कंप्यूटर सारा डेटा बिट (0 या 1) में रखता है। 8 बिट = 1 बाइट; 1 kB = 1000 बाइट, 1 MB = 1000 kB, 1 GB = 1000 MB, 1 TB = 1000 GB। संख्याएँ बाइनरी में रहती हैं, जहाँ स्थानीय मान दोगुने होते जाते हैं: 1, 2, 4, 8… अक्षरों के लिए कैरेक्टर सेट होता है: ASCII में 'A' = 65; यूनिकोड में हर लिपि है। बिटमैप चित्र पिक्सेल का जाल है; साइज़ = चौड़ाई × ऊँचाई × कलर डेप्थ। ध्वनि के सैंपल लिए जाते हैं: साइज़ = सैंपल रेट × बिट डेप्थ × सेकंड। वेक्टर चित्र पिक्सेल की जगह आकृतियाँ रखता है। कम्प्रेशन फ़ाइल छोटी करता है: लॉसलेस हर बिट बचाता है, लॉसी कुछ बारीकी हटा देता है।

6. 4.6-4.7 Computer systems and architecture (A-level)

Logic circuits · Interrupts

बूलियन तर्क (Boolean Logic) – बूलियन तर्क में केवल दो मान हैं: 1 (सत्य) और 0 (असत्य)। लॉजिक गेट इन पर काम करते हैं: NOT मान उलटता है; AND तभी 1 जब सभी इनपुट 1; OR तब 1 जब कोई भी इनपुट 1; NAND और NOR, AND और OR के उल्टे हैं; XOR तब 1 जब इनपुट अलग हों। सत्य सारणी हर इनपुट संयोजन का आउटपुट बताती है (n इनपुट पर 2ⁿ पंक्तियाँ)। डी मॉर्गन: (A·B)' = A' + B' और (A + B)' = A'·B'। गेटों को जोड़कर लॉजिक सर्किट बनते हैं।
प्रोसेसर के अंदर: रजिस्टर, फ़ेच-एक्ज़िक्यूट चक्र, पता-विधान और इंटरप्ट – प्रोसेसर में ALU, नियंत्रण इकाई (CU), घड़ी और रजिस्टर (PC, MAR, MDR, CIR, संचायक ACC, स्टेटस रजिस्टर) होते हैं, जो पता बस, डेटा बस और नियंत्रण बस से मुख्य मेमोरी से जुड़े हैं। हर निर्देश फ़ेच होता है (MAR ← [PC]; MDR ← [मेमोरी], PC ← [PC] + 1; CIR ← [MDR]), opcode और operand में डिकोड होता है, फिर एक्ज़िक्यूट। ऑपरेंड तात्कालिक (ख़ुद मान) या प्रत्यक्ष (मेमोरी पता) हो सकता है। असेंबली में LDR, STR, ADD, SUB, CMP, B, BEQ जैसे संक्षेप हैं। प्रदर्शन कोर, कैश, घड़ी गति, शब्द लंबाई और बस चौड़ाई पर निर्भर है। इंटरप्ट में प्रोसेसर अस्थिर वातावरण स्टैक पर सहेजकर ISR चलाता है और फिर लौटता है।

7. 4.9 Communication and networking

The Internet · TCP/IP

वेब सेवाएँ: वेबसाइट खोलने पर क्या होता है – वर्ल्ड वाइड वेब (WWW) इंटरनेट पर रखे आपस में जुड़े वेब पेजों की व्यवस्था है, जिन्हें ब्राउज़र से खोलते हैं। वेब पेज HTML में लिखे जाते हैं, जो तय टैग से सामग्री दिखाता है; XML अपने बनाए टैग से डेटा रखता और ले जाता है। हर वेबसाइट का डोमेन नेम होता है, जैसे example.org, जिसे DNS IP एड्रेस में बदलता है। URL किसी एक संसाधन का पूरा पता है: प्रोटोकॉल, डोमेन और पाथ। वेबसाइट जुड़े वेब पेजों का समूह है। वेब ब्राउज़र पेज माँगकर दिखाता है; वेब सर्वर उन्हें रखकर भेजता है; वेब होस्टिंग ऐसे सर्वर पर जगह किराए पर लेना है ताकि साइट हमेशा ऑनलाइन रहे।
नेटवर्क के प्रकार, टोपोलॉजी और प्रोटोकॉल: आकार, ढाँचा और नियम – नेटवर्क आकार से बँटते हैं: PAN (एक व्यक्ति के आस-पास कुछ मीटर), LAN (कमरा, इमारत या परिसर), MAN (शहर) और WAN (देश या दुनिया)। टोपोलॉजी नोड्स के जुड़ने का ढाँचा है: बस (सब एक बैकबोन केबल पर), स्टार (सब एक केंद्रीय हब या स्विच से) और ट्री (स्तरों में जुड़े स्टार)। प्रोटोकॉल नियमों का समूह है: TCP/IP इंटरनेट पर डेटा तोड़ता और रास्ता देता है, HTTP और HTTPS वेब पेज लाते हैं, FTP फ़ाइलें भेजता है, SMTP ईमेल भेजता है, POP3 ईमेल डाउनलोड करता है, PPP दो उपकरण सीधे जोड़ता है, TELNET दूर के कंप्यूटर में लॉग-इन कराता है, और VoIP इंटरनेट पर आवाज़ ले जाता है।

8. 4.10 Fundamentals of databases

Data modelling and relational design · SQL and client-server databases

संबंधपरक डेटाबेस: तालिकाएँ, पंक्तियाँ, स्तंभ और कीज़ – डेटा को कई अलग फ़ाइलों में रखने से डेटा दोहराता है, कॉपियाँ आपस में मेल नहीं खातीं और खोजना कठिन होता है, इसलिए हम 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 समूह छाँटता है। कार्टेशियन प्रोडक्ट एक तालिका की हर पंक्ति को दूसरी की हर पंक्ति से जोड़ता है; इक्वी-जॉइन केवल वे जोड़े रखता है जिनका साझा स्तंभ मेल खाए; नेचुरल जॉइन भी यही करता है पर साझा स्तंभ एक बार दिखाता है।

9. 4.11 Big Data

What Big Data is · Processing Big Data · Modelling Big Data

बिग डेटा (Big Data) – बिग डेटा वह डेटा है जो एक साधारण कंप्यूटर और साधारण सॉफ़्टवेयर के लिए बहुत बड़ा, बहुत तेज़ या बहुत मिला-जुला हो। इसे तीन V से समझते हैं: मात्रा (Volume), वेग (Velocity) और विविधता (Variety)। इसे संभालने के लिए काम कई मशीनों में एक साथ बाँटा जाता है (वितरित प्रोसेसिंग, जैसे MapReduce)। बिग डेटा को अक्सर तथ्यों (facts) या ग्राफ (नोड और लिंक) के रूप में रखा जाता है। मौसम, नक्शे, स्वास्थ्य, खरीदारी और AI में इसका उपयोग होता है, पर निजता और निष्पक्षता के सवाल भी उठते हैं।

10. 4.12 Fundamentals of functional programming

Functional paradigm · Writing functional programs and lists

फ़ंक्शनल प्रोग्रामिंग: फ़ंक्शन, map, filter और fold – फ़ंक्शनल प्रोग्रामिंग में प्रोग्राम फ़ंक्शनों से बनता है। फ़ंक्शन अपने प्रांत (domain) के हर इनपुट को सह-प्रांत (co-domain) के एक आउटपुट से जोड़ता है; इसका type f: A → B लिखते हैं। शुद्ध (pure) फ़ंक्शन एक ही इनपुट पर वही आउटपुट देता है और बाहर कुछ नहीं बदलता (कोई side effect नहीं); डेटा अपरिवर्तनीय (immutable) रहता है। फ़ंक्शन first-class हैं: नाम दिया जा सकता है, दूसरे को दिया और लौटाया जा सकता है। Partial application में फ़ंक्शन को कुछ इनपुट देकर नया फ़ंक्शन मिलता है। Composition g ∘ f में पहले f, फिर g चलता है। Higher-order फ़ंक्शन: map हर सदस्य पर फ़ंक्शन लगाता है, filter जाँच में पास सदस्य रखता है, fold (reduce) पूरी सूची को एक मान बना देता है। सूची = head (पहला सदस्य) + tail (बाक़ी)।

11. 4.14 Non-exam assessment: practical project

Choosing the project · Report sections and marks · Technical skill and coding style · Testing and evaluation evidence

कंप्यूटिंग का बड़ा प्रोजेक्ट: चुनो, विश्लेषण, डिज़ाइन, बनाओ, जाँचो, परखो – कैपस्टोन (प्रायोगिक) प्रोजेक्ट एक बड़ा काम है जिसमें तुम किसी असली समस्या को प्रोग्राम से हल करते हो, या कंप्यूटिंग के किसी सवाल की जाँच करते हो, और उस पर रिपोर्ट लिखते हो। ऐसी समस्या चुनो जिसका असली उपयोगकर्ता हो और जिसमें पर्याप्त तकनीकी गहराई हो। रिपोर्ट के हिस्से: विश्लेषण (समस्या, उपयोगकर्ता, शोध, मापने योग्य उद्देश्य), डिज़ाइन (डेटा संरचना, एल्गोरिद्म, स्क्रीन, मॉड्यूल), तकनीकी हल (काम करता कोड, जिसके सबसे ज़्यादा अंक), परीक्षण (सामान्य, सीमा और ग़लत डेटा के साथ योजना और सबूत) और मूल्यांकन (हर उद्देश्य पर फ़ैसला, उपयोगकर्ता की राय, सुधार)। अच्छी कोडिंग शैली: अर्थपूर्ण नाम, छोटे एक-काम वाले मॉड्यूल, ज़रूरी टिप्पणियाँ, और ग़लत इनपुट सँभालने वाला सुरक्षित कोड।