National Year 10 Computer Science

अध्याय: 3

1. 3.1 Fundamentals of algorithms

3.1.1 Representing algorithms · 3.1.2 Efficiency of algorithms · 3.1.3 Searching algorithms · 3.1.4 Sorting algorithms

समस्या समाधान का परिचय – कंप्यूटर से समस्या हल करने के चरण: समस्या का विश्लेषण (इनपुट, आउटपुट, नियम), एल्गोरिद्म बनाना (सीमित, स्पष्ट, क्रमबद्ध चरण), प्रोग्रामिंग भाषा में कोड करना, अलग-अलग इनपुट से जाँचना (टेस्ट), और डीबग (गलतियाँ ढूँढकर हटाना)। एल्गोरिद्म को फ़्लोचार्ट (अंडाकार = शुरू/रुको, समांतर चतुर्भुज = इनपुट/आउटपुट, आयत = प्रक्रिया, हीरा = निर्णय, तीर = दिशा) या स्यूडोकोड (सरल संरचित भाषा) में दिखाते हैं। विघटन बड़ी समस्या को छोटी उप-समस्याओं में तोड़ता है।
एल्गोरिदम कॉम्प्लेक्सिटी: एल्गोरिदम कितनी तेज़ी से बढ़ता है? – एक ही सवाल को कई एल्गोरिदम हल कर सकते हैं, पर कुछ बहुत ज़्यादा कदम लेते हैं। हम घड़ी के सेकंड नहीं, बल्कि इनपुट के आकार 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)। मेमोरी की बढ़त = स्पेस कॉम्प्लेक्सिटी।
खोज (Searching) और छँटाई (Sorting) एल्गोरिदम – खोज एल्गोरिदम सूची में कोई चीज़ ढूँढता है; छँटाई एल्गोरिदम सूची को क्रम में लगाता है। रेखीय खोज एक-एक करके देखती है और किसी भी सूची पर चलती है। द्विआधारी खोज छँटी सूची को हर बार आधा करती है और बहुत तेज़ है। बबल सॉर्ट पड़ोसियों की अदला-बदली करता है; मर्ज सॉर्ट सूची तोड़कर छँटे टुकड़े जोड़ता है, जो बड़ी सूचियों में तेज़ है।
सॉर्टिंग एल्गोरिदम (छाँटने के तरीक़े) – सॉर्टिंग एल्गोरिदम किसी सूची को क्रम में लगाता है। बबल सॉर्ट पड़ोसियों की अदला-बदली करता है, इंसर्शन सॉर्ट हर चीज़ को छँटे हिस्से में सही जगह खिसकाता है, सिलेक्शन सॉर्ट हर बार सबसे छोटा चुनता है, और मर्ज सॉर्ट सूची को तोड़कर छँटे हिस्से जोड़ता है। लंबी सूची पर मर्ज सॉर्ट बहुत कम तुलनाएँ करता है (लगभग n²/2 की जगह n log₂ n)।

2. 3.2 Programming

3.2.1 Data types · 3.2.2 Programming concepts · 3.2.3-3.2.5 Arithmetic, relational and Boolean operations · 3.2.6 Data structures · 3.2.7-3.2.9 Input/output, strings, random numbers · 3.2.10 Structured programming and subroutines · 3.2.11 Robust and secure programming

प्रोग्रामिंग की मूल बातें: अनुक्रम, चयन, लूप और फ़ंक्शन – प्रोग्राम सटीक निर्देशों का समूह है जिसे कंप्यूटर मानता है। हर प्रोग्राम तीन संरचनाओं से बनता है: अनुक्रम (क्रम से कदम), चयन (if/else से चुनाव) और पुनरावृत्ति (लूप)। चर मान संभालकर रखते हैं। फ़ंक्शन कोड को नाम वाले, दोबारा इस्तेमाल होने वाले खंडों में बाँटते हैं, जिससे प्रोग्राम मॉड्यूलर बनता है और उसे जाँचना, सुधारना और सँभालना आसान होता है।
कंट्रोल फ्लो: क्रम, चयन और पुनरावृत्ति – प्रोग्राम निर्देशों की एक सूची है। ये निर्देश किस क्रम में चलेंगे, इसे कंट्रोल फ्लो कहते हैं। इसके तीन ही हिस्से हैं: क्रम (sequence, एक के बाद एक), चयन (selection, IF से एक रास्ता चुनना) और पुनरावृत्ति (iteration, लूप से दोहराना)। लूप दो तरह के होते हैं: निश्चित (FOR, गिनती पहले से पता) और अनिश्चित (WHILE / REPEAT UNTIL, शर्त बदलने पर रुकता है)। एक ढाँचे के अंदर दूसरा रख सकते हैं (नेस्टिंग)। मान चर (variable, बदल सकता है) और स्थिरांक (constant, नहीं बदलता) में रखे जाते हैं, और इनके नाम साफ़ मतलब वाले होने चाहिए।
ऐरे और लिस्ट: एक नाम में बहुत सारे मान – ऐरे (array) नंबर वाले डिब्बों की एक पंक्ति है जिनका नाम एक ही होता है। हर डिब्बे में एक मान होता है और उसका इंडेक्स 0 से शुरू होता है। इंडेक्स से हम डिब्बा पढ़ते या बदलते हैं, लूप से हर डिब्बे पर जाते हैं (ट्रैवर्सल), और इसी लूप से योग, औसत, सबसे बड़ा मान, गिनती और लीनियर सर्च करते हैं। 2D ऐरे पंक्तियों और स्तंभों का ग्रिड है, जिसे दो इंडेक्स और दो नेस्टेड लूप से पढ़ते हैं। ऐरे का आकार तय होता है; लिस्ट बढ़-घट सकती है।
Python में स्ट्रिंग – स्ट्रिंग अक्षरों का इम्यूटेबल अनुक्रम है जो एकल, दोहरे या तिहरे उद्धरण चिह्नों में लिखा जाता है। हर अक्षर का धनात्मक इंडेक्स (बाएँ से 0) और ऋणात्मक इंडेक्स (दाएँ से −1) होता है। संक्रियाएँ: + (जोड़ना), * (दोहराना), in / not in (सदस्यता) और स्लाइसिंग s[start:stop:step], जो start से stop तक (stop शामिल नहीं) अक्षर लेती है। ट्रैवर्सल = लूप से हर अक्षर पर जाना। len(), upper(), lower(), title(), capitalize(), count(), find(), index(), replace(), split(), join(), strip(), startswith(), endswith(), isalpha(), isdigit(), isalnum(), islower(), isupper(), isspace() जैसे मेथड मूल स्ट्रिंग बदले बिना नया मान देते हैं।
पायथन में फ़ंक्शन: अपनी मशीनें ख़ुद बनाइए – फ़ंक्शन एक नाम वाला कोड-खंड है जो एक काम करता है। पायथन में बिल्ट-इन फ़ंक्शन (print, len), मॉड्यूल के फ़ंक्शन (math.sqrt, random.randint) और def से बने यूज़र-डिफ़ाइंड फ़ंक्शन होते हैं। कॉल में भेजे मान आर्ग्युमेंट हैं; उन्हें पकड़ने वाले नाम पैरामीटर हैं। आर्ग्युमेंट स्थान के अनुसार (positional), नाम से (keyword) या डिफ़ॉल्ट मान से आते हैं। return मान वापस भेजता है। पायथन ऊपर से नीचे चलता है, कॉल पर फ़ंक्शन में कूदता है और फिर लौट आता है। फ़ंक्शन के अंदर बने नाम लोकल, बाहर बने ग्लोबल होते हैं।
सॉफ़्टवेयर विकास: विचार से चलते ऐप तक – अच्छा सॉफ़्टवेयर चरणों में बनता है: समस्या का विश्लेषण करके आवश्यकताएँ लिखो, हल डिज़ाइन करो, छोटे हिस्सों में कोड करो, सामान्य, सीमा और गलत डेटा से परीक्षण करो, उपयोगकर्ताओं तक पहुँचाओ और रखरखाव करो। वॉटरफ़ॉल हर चरण एक बार क्रम से करता है; एजाइल छोटे चक्र दोहराता है। मज़बूत प्रोग्राम इनपुट जाँचते हैं, और टीमें वर्ज़न कंट्रोल, साफ़ भूमिकाएँ और उपयोगकर्ता की राय इस्तेमाल करती हैं।

3. 3.3 Fundamentals of data representation

3.3.1-3.3.2 Number bases and conversion · 3.3.3 Units of information · 3.3.4 Binary arithmetic · 3.3.5 Character encoding · 3.3.6 Representing images · 3.3.7 Representing sound · 3.3.8 Data compression

संख्या पद्धति और कूटन (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; यूनिकोड में हर लिपि है। बिटमैप चित्र पिक्सेल का जाल है; साइज़ = चौड़ाई × ऊँचाई × कलर डेप्थ। ध्वनि के सैंपल लिए जाते हैं: साइज़ = सैंपल रेट × बिट डेप्थ × सेकंड। वेक्टर चित्र पिक्सेल की जगह आकृतियाँ रखता है। कम्प्रेशन फ़ाइल छोटी करता है: लॉसलेस हर बिट बचाता है, लॉसी कुछ बारीकी हटा देता है।
डिजिटल मीडिया: चित्र, आवाज़ और वीडियो संख्याएँ कैसे बनते हैं – डिजिटल मीडिया यानी कंप्यूटर पर संख्याओं के रूप में सहेजा गया हर चित्र, आवाज़, वीडियो या एनिमेशन। रास्टर चित्र पिक्सेल का जाल है; हर पिक्सेल लाल, हरे और नीले के 0 से 255 तक के मानों में सहेजा जाता है। वेक्टर ग्राफ़िक्स आकृतियों को गणित से सहेजते हैं, इसलिए हर आकार में साफ़ रहते हैं। वीडियो और एनिमेशन बहुत सारे फ़्रेम तेज़ी से दिखाना है। रेज़ोल्यूशन बढ़ने से फ़ाइल बड़ी होती है, इसलिए संपीडन करते हैं। मीडिया बनाते-बाँटते समय कॉपीराइट, लाइसेंस और लोगों के चित्र-अधिकार का सम्मान करना ज़रूरी है।