UPPSC LT Grade Teacher Computer Science Exam Notes

कंप्यूटर विज्ञान: डिजिटल लॉजिक और सर्किट्स & डिस्क्रीट मैथमेटिकल स्ट्रक्चर्स

यूनिट 1: डिजिटल लॉजिक और सर्किट्स (Digital Logic and Circuits)

1. संख्यात्मक प्रणाली और कोड (Number Systems and Codes)

संख्यात्मक प्रणाली (Number system) एक ऐसी विधि है जिसका उपयोग संख्याओं का प्रतिनिधित्व करने के लिए किया जाता है। कंप्यूटर विभिन्न संख्यात्मक प्रणालियों का उपयोग करते हैं, जिनमें से बाइनरी सबसे महत्वपूर्ण है।

1.1 बाइनरी संख्यात्मक प्रणाली (Binary Number System - द्विक संख्यात्मक प्रणाली)

बाइनरी संख्यात्मक प्रणाली, जिसे द्विक संख्यात्मक प्रणाली भी कहा जाता है, आधार-2 (base-2) वाली एक संख्या प्रणाली है। यह केवल दो प्रतीकों का उपयोग करती है: 0 और 1 (bits)। कंप्यूटर सिस्टम इसके साथ काम करते हैं क्योंकि यह सीधे विद्युत ऑन (on) और ऑफ (off) स्थितियों का प्रतिनिधित्व करता है।

उदाहरण: बाइनरी संख्या 1011₂ को दशमीक में (1 * 2^3) + (0 * 2^2) + (1 * 2^1) + (1 * 2^0) = 8 + 0 + 2 + 1 = 11₁₀ लिखा जा सकता है।

1.2 दशमीक, अष्टभुज, और हेक्साडेसीमल प्रणालियाँ (Decimal, Octal, and Hexadecimal Systems)

• दशमीक प्रणाली (Decimal System): यह आधार-10 (base-10) वाली प्रणाली है और इसमें 0 से 9 तक के 10 अंक होते हैं। यह हमारी दैनिक जीवन में उपयोग की जाने वाली सामान्य संख्या प्रणाली है।
• अष्टभुज प्रणाली (Octal System): यह आधार-8 (base-8) वाली प्रणाली है और इसमें 0 से 7 तक के 8 अंक होते हैं। कंप्यूटर में, तीन बाइनरी बिट्स एक अष्टभुज अंक का प्रतिनिधित्व कर सकते हैं।
• हेक्साडेसीमल प्रणाली (Hexadecimal System): यह आधार-16 (base-16) वाली प्रणाली है और इसमें 0 से 9 तक के अंक और A से F तक के अक्षर (जो 10 से 15 तक का प्रतिनिधित्व करते हैं) होते हैं। यह चार बाइनरी बिट्स का उपयोग करके बड़े बाइनरी संख्याओं को संक्षिप्त रूप से दर्शाने के लिए उपयोग किया जाता है।

1.3 संख्या प्रणाली रूपांतरण (Number System Conversions)

विभिन्न संख्या प्रणालियों के बीच संख्याओं को परिवर्तित करना डिजिटल इलेक्ट्रॉनिक्स में एक महत्वपूर्ण कौशल है।

1. दशमीक से बाइनरी/अष्टभुज/हेक्साडेसीमल (Decimal to Binary/Octal/Hexadecimal): संख्या को आधार (2, 8, या 16) से लगातार विभाजित करें और शेषफलों को उल्टे क्रम में लिखें।
2. बाइनरी/अष्टभुज/हेक्साडेसीमल से दशमीक (Binary/Octal/Hexadecimal to Decimal): प्रत्येक अंक को उसके संबंधित स्थिति मान (positional value) से गुणा करें और परिणामों को जोड़ें।
3. बाइनरी से अष्टभुज/हेक्साडेसीमल और इसके विपरीत (Binary to Octal/Hexadecimal and Vice Versa):
   • बाइनरी से अष्टभुज: बाइनरी अंकों को दाईं से बाईं ओर तीन-तीन के समूह में बांटें और प्रत्येक समूह को उसके अष्टभुज समकक्ष में बदलें।
   • अष्टभुज से बाइनरी: प्रत्येक अष्टभुज अंक को उसके तीन-बिट बाइनरी समकक्ष में बदलें।
   • बाइनरी से हेक्साडेसीमल: बाइनरी अंकों को दाईं से बाईं ओर चार-चार के समूह में बांटें और प्रत्येक समूह को उसके हेक्साडेसीमल समकक्ष में बदलें।
   • हेक्साडेसीमल से बाइनरी: प्रत्येक हेक्साडेसीमल अंक को उसके चार-बिट बाइनरी समकक्ष में बदलें।

1.4 बाइनरी अंकगणित (Binary Arithmetic - Addition, Subtraction, Multiplication, Division)

बाइनरी अंकगणित (Binary arithmetic) बाइनरी संख्याओं पर गणितीय संचालन को संदर्भित करता है।

• जोड़ (Addition):
  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 0 (और कैरी 1)
• घटाव (Subtraction): पूरक विधि (complement method) का उपयोग आमतौर पर किया जाता है। 1 के पूरक (1's complement) और 2 के पूरक (2's complement) होते हैं।
  • 1 के पूरक: बाइनरी संख्या के सभी 0 को 1 और 1 को 0 में बदलना।
  • 2 के पूरक: 1 के पूरक में 1 जोड़ना।

  उदाहरण (घटाव 2 के पूरक का उपयोग करके): 1101 - 0101 (13 - 5)

  0101 का 2 का पूरक = 1010 + 1 = 1011

  1101 + 1011 = 11000 (अंतिम कैरी को अनदेखा करें) = 1000₂ = 8₁₀

• गुणा (Multiplication): दशमीक गुणा के समान, लेकिन केवल 0 और 1 का उपयोग किया जाता है।
• भाग (Division): पुनरावृत्त घटाव विधि (repeated subtraction method) का उपयोग किया जाता है।

1.5 बीसीडी कोड (BCD - Binary Coded Decimal Codes)

बीसीडी (BCD) एक बाइनरी-कोडित दशमीक (Binary Coded Decimal) प्रणाली है जहाँ दशमीक संख्या के प्रत्येक अंक को एक अलग चार-बिट बाइनरी संख्या द्वारा दर्शाया जाता है।

उदाहरण: दशमीक संख्या 47 को बीसीडी में 0100 0111 के रूप में दर्शाया जाता है (जबकि बाइनरी में 47 101111 होगा)।

1.6 ग्रे कोड (Gray Code), एक्सेस-3 कोड (Excess-3 Code)

• ग्रे कोड (Gray Code): यह एक असंकलन कोड (non-weighted code) है जहाँ एक क्रमिक संख्या से दूसरी संख्या में केवल एक बिट बदलता है। यह त्रुटियों को कम करने के लिए एन्कोडर और अन्य डिजिटल प्रणालियों में उपयोगी है।

उदाहरण: बाइनरी 000 (0) -> ग्रे 000

बाइनरी 001 (1) -> ग्रे 001

बाइनरी 010 (2) -> ग्रे 011 (केवल एक बिट बदला)

• एक्सेस-3 कोड (Excess-3 Code): यह एक गैर-भारित (non-weighted) और स्व-पूरक (self-complementing) कोड है। यह दशमीक अंक में 3 जोड़कर प्राप्त बीसीडी कोड है। यह गणितीय संचालन के लिए उपयोगी है क्योंकि यह 9 के पूरक को आसानी से प्राप्त करने की अनुमति देता है।

उदाहरण: दशमीक 4 का बीसीडी 0100 है। एक्सेस-3 कोड 0100 + 0011 (3 का बाइनरी) = 0111 है।

2. बूलियन बीजगणित और लॉजिक गेट्स (Boolean Algebra and Logic Gates)

बूलियन बीजगणित (Boolean Algebra) गणित की एक शाखा है जो लॉजिक संचालन (logic operations) और उनके नियमों से संबंधित है। यह डिजिटल सर्किट के विश्लेषण और डिजाइन के लिए मौलिक है।

2.1 बूलियन एक्सप्रेशन (Boolean Expressions)

एक बूलियन एक्सप्रेशन (Boolean expression) एक समीकरण है जिसमें बूलियन चर (Boolean variables) (जो केवल 0 या 1 मान ले सकते हैं) और लॉजिक ऑपरेटर (logic operators) (AND, OR, NOT) होते हैं।

उदाहरण: F = A . B + C' (A AND B OR NOT C)

2.2 बेसिक लॉजिक गेट्स (Basic Logic Gates): AND, OR, NOT

लॉजिक गेट्स (Logic gates) डिजिटल सर्किट के बिल्डिंग ब्लॉक्स हैं जो एक या अधिक इनपुट लेते हैं और एक एकल आउटपुट का उत्पादन करते हैं।

• AND गेट (AND Gate): आउटपुट तभी 1 होता है जब सभी इनपुट 1 हों।

  आउटपुट (Y) = A . B (या AB)

• OR गेट (OR Gate): आउटपुट तभी 1 होता है जब कम से कम एक इनपुट 1 हो।

  आउटपुट (Y) = A + B

• NOT गेट (NOT Gate/Inverter): यह इनपुट को उल्टा करता है (0 को 1 और 1 को 0)।

  आउटपुट (Y) = A' (या $\bar{A}$)

2.3 यूनिवर्सल गेट्स (Universal Gates): NAND, NOR

सार्वभौमिक गेट्स (Universal gates) वे गेट्स हैं जिनसे किसी भी अन्य लॉजिक गेट (AND, OR, NOT) को बनाया जा सकता है।

• NAND गेट (NAND Gate): यह AND गेट का उलटा (NOT AND) है। आउटपुट तभी 0 होता है जब सभी इनपुट 1 हों।

  आउटपुट (Y) = (A . B)'

• NOR गेट (NOR Gate): यह OR गेट का उलटा (NOT OR) है। आउटपुट तभी 1 होता है जब सभी इनपुट 0 हों।

  आउटपुट (Y) = (A + B)'

2.4 ट्रुथ टेबल्स (Truth Tables)

एक ट्रुथ टेबल (Truth table) एक गणितीय तालिका है जिसका उपयोग बूलियन लॉजिक फ़ंक्शन के सभी संभावित इनपुट संयोजनों और उनके संबंधित आउटपुट को प्रदर्शित करने के लिए किया जाता है।

उदाहरण: AND गेट के लिए ट्रुथ टेबल

इनपुट A	इनपुट B	आउटपुट Y = A . B
0	0	0
0	1	0
1	0	0
1	1	1

2.5 बूलियन नियम और प्रमेय (Boolean Laws and Theorems)

बूलियन बीजगणित में विभिन्न नियम और प्रमेय होते हैं जो बूलियन एक्सप्रेशन को सरल बनाने में मदद करते हैं:

• कम्यूटेटिव लॉ (Commutative Law): A + B = B + A; A . B = B . A
• एसोसिएटिव लॉ (Associative Law): A + (B + C) = (A + B) + C; A . (B . C) = (A . B) . C
• डिस्ट्रिब्यूटिव लॉ (Distributive Law): A . (B + C) = A . B + A . C; A + (B . C) = (A + B) . (A + C)
• पहचान नियम (Identity Law): A + 0 = A; A . 1 = A
• निरसन नियम (Annihilation Law): A + 1 = 1; A . 0 = 0
• एकरूपता नियम (Idempotent Law): A + A = A; A . A = A
• पूरक नियम (Complement Law): A + A' = 1; A . A' = 0
• दोहरा निषेध (Double Negation): (A')' = A
• डी मॉर्गन का प्रमेय (De Morgan's Theorem):
  • (A + B)' = A' . B'
  • (A . B)' = A' + B'

2.6 कर्णघ मैप (K-Map) का उपयोग करके सरलीकरण (Simplification using Karnaugh Map)

कर्णघ मैप (K-Map) एक ग्राफिकल विधि है जिसका उपयोग बूलियन एक्सप्रेशन को सरल बनाने के लिए किया जाता है। यह उत्पाद-के-योग (POS - Product-of-Sums) या योग-के-उत्पाद (SOP - Sum-of-Products) के रूप में न्यूनतम एक्सप्रेशन प्राप्त करने में मदद करता है।

K-Map में, समान (adjacent) 1s (जो केवल एक बिट स्थिति में भिन्न होते हैं) को समूहित किया जाता है ताकि एक्सप्रेशन को छोटा किया जा सके। 2, 4, 8, 16 आदि के समूह बनाए जाते हैं।

उदाहरण: यदि आपके पास एक ट्रुथ टेबल है और आपको F(A, B, C) = $\sum$m(0, 1, 4, 5) को सरल बनाना है, तो आप एक 3-चर K-Map बनाएंगे और 1s को समूहित करके न्यूनतम एक्सप्रेशन प्राप्त करेंगे (जैसे $\bar{A}\bar{B}$ और $A\bar{B}$ के समूह से $\bar{B}$ या $\bar{A}\bar{B}$ और $A\bar{B}$ के समूह से $\bar{B}$)।

3. कॉम्बिनेशनल और सीक्वेंशियल सर्किट्स (Combinational and Sequential Circuits)

डिजिटल सर्किट्स को उनके आउटपुट की निर्भरता के आधार पर कॉम्बिनेशनल या सीक्वेंशियल के रूप में वर्गीकृत किया जा सकता है।

3.1 कॉम्बिनेशनल सर्किट्स (Combinational Circuits - Definition, Characteristics)

कॉम्बिनेशनल सर्किट्स (Combinational circuits) वे डिजिटल सर्किट्स हैं जहाँ आउटपुट केवल वर्तमान इनपुट पर निर्भर करता है। उनके पास कोई मेमोरी तत्व (memory element) नहीं होता है।

• विशेषताएँ (Characteristics):
  • कोई फीडबैक (feedback) नहीं।
  • कोई मेमोरी (memory) नहीं।
  • आउटपुट तात्कालिक (instantaneous) होता है और सीधे इनपुट के वर्तमान संयोजन पर निर्भर करता है।

3.2 हाफ ऐडर, फुल ऐडर, मल्टीप्लेक्सर, एनकोडर, डिकोडर (Half Adder, Full Adder, Multiplexers, Encoders, Decoders)

• हाफ ऐडर (Half Adder): दो बाइनरी बिट्स को जोड़ता है और सम (Sum) और कैरी (Carry) आउटपुट उत्पन्न करता है।

Sum = A $\oplus$ B

Carry = A . B

• फुल ऐडर (Full Adder): तीन बाइनरी बिट्स (दो इनपुट बिट्स और एक इनपुट कैरी) को जोड़ता है और सम और कैरी आउटपुट उत्पन्न करता है।
• मल्टीप्लेक्सर (Multiplexers - MUX): एक डेटा सेलेक्टर (Data Selector) भी कहा जाता है, यह कई इनपुट लाइनों में से एक को चुनता है और इसे एक सिंगल आउटपुट लाइन में रूट करता है। चयन (selection) नियंत्रण इनपुट (control inputs) द्वारा किया जाता है।
• एनकोडर (Encoders): 2^n इनपुट लाइनों में से एक को सक्रिय होने पर एक n-बिट बाइनरी कोड में परिवर्तित करता है।
• डिकोडर (Decoders): n इनपुट लाइनों से 2^n आउटपुट लाइनों को सक्रिय करता है। यह बाइनरी कोड को दशमीक या अन्य प्रारूपों में परिवर्तित करता है।

3.3 सीक्वेंशियल सर्किट्स (Sequential Circuits - Definition, Types)

सीक्वेंशियल सर्किट्स (Sequential circuits) वे डिजिटल सर्किट्स हैं जहाँ आउटपुट केवल वर्तमान इनपुट पर ही नहीं, बल्कि पिछले इनपुट के क्रम (sequence) पर भी निर्भर करता है। उनके पास मेमोरी तत्व (memory elements) होते हैं।

• विशेषताएँ (Characteristics):
  • फीडबैक पाथ (feedback path) होता है।
  • मेमोरी तत्व होते हैं (जैसे फ्लिप-फ्लॉप)।
  • आउटपुट वर्तमान और पिछली इनपुट स्थितियों पर निर्भर करता है।
• प्रकार (Types):
  • सिंक्रोनस सीक्वेंशियल सर्किट (Synchronous Sequential Circuits): क्लॉक सिग्नल (clock signal) द्वारा ट्रिगर होते हैं।
  • असिंक्रोनस सीक्वेंशियल सर्किट (Asynchronous Sequential Circuits): क्लॉक सिग्नल के बिना इनपुट सिग्नल के परिवर्तन से ट्रिगर होते हैं।

3.4 फ्लिप-फ्लॉप (Flip-Flops): SR, JK, D, T

फ्लिप-फ्लॉप (Flip-flop) एक मौलिक मेमोरी तत्व है जो एक बिट बाइनरी डेटा को स्टोर कर सकता है। यह सीक्वेंशियल सर्किट्स का आधार है।

• SR फ्लिप-फ्लॉप (SR Flip-Flop - Set-Reset): सबसे सरल फ्लिप-फ्लॉप। S = 1, R = 0 सेट करता है (आउटपुट Q=1), S = 0, R = 1 रीसेट करता है (आउटपुट Q=0)। S = 1, R = 1 एक अमान्य स्थिति (invalid state) है।
• JK फ्लिप-फ्लॉप (JK Flip-Flop): SR फ्लिप-फ्लॉप की "अमान्य" स्थिति की समस्या को हल करता है। J = 1, K = 1 होने पर आउटपुट टॉगल (toggle) होता है।
• D फ्लिप-फ्लॉप (D Flip-Flop - Data/Delay): डेटा इनपुट को सीधे आउटपुट में पास करता है जब क्लॉक पल्स (clock pulse) सक्रिय होता है। यह डेटा स्टोरेज के लिए उपयोग किया जाता है।
• T फ्लिप-फ्लॉप (T Flip-Flop - Toggle): प्रत्येक क्लॉक पल्स पर आउटपुट की स्थिति को टॉगल करता है (उल्टा करता है)। यह काउंटर्स (counters) के लिए उपयोगी है।

3.5 काउंटर्स (Counters - Asynchronous and Synchronous)

काउंटर्स (Counters) सीक्वेंशियल सर्किट्स होते हैं जो क्लॉक पल्स की संख्या गिनने के लिए उपयोग किए जाते हैं।

• असिंक्रोनस काउंटर्स (Asynchronous Counters / Ripple Counters): क्लॉक पल्स पहले फ्लिप-फ्लॉप पर लागू होती है, और प्रत्येक फ्लिप-फ्लॉप का आउटपुट अगले को क्लॉक करता है। इनमें प्रचार विलंब (propagation delay) होता है।
• सिंक्रोनस काउंटर्स (Synchronous Counters): सभी फ्लिप-फ्लॉप को एक साथ एक ही क्लॉक पल्स द्वारा क्लॉक किया जाता है। यह प्रचार विलंब को कम करता है।

3.6 रजिस्टर्स (Registers)

रजिस्टर्स (Registers) फ्लिप-फ्लॉप का एक समूह है जिसका उपयोग बाइनरी जानकारी (डेटा) के समूह को स्टोर करने के लिए किया जाता है। एक n-बिट रजिस्टर n फ्लिप-फ्लॉप से बना होता है।

रजिस्टरों का उपयोग अस्थायी रूप से डेटा को स्टोर करने, डेटा को शिफ्ट करने (शिफ्ट रजिस्टर), और गणना के लिए किया जाता है।

यूनिट 1: डिस्क्रीट मैथमेटिकल स्ट्रक्चर्स (Discrete Mathematical Structures)

4. सेट्स, संबंध, और कार्य (Sets, Relations, and Functions)

डिस्क्रीट मैथमेटिक्स में सेट्स, संबंध और कार्य मूलभूत अवधारणाएं हैं, जो कंप्यूटर विज्ञान में डेटा संरचनाओं और एल्गोरिदम को समझने के लिए महत्वपूर्ण हैं।

4.1 सेट थ्योरी (Set Theory): परिभाषाएँ, नोटेशन, सेट्स के प्रकार

सेट (Set) विशिष्ट वस्तुओं का एक सु-परिभाषित (well-defined) संग्रह है।

• नोटेशन (Notations): सेट को आमतौर पर कैपिटल अक्षरों से दर्शाया जाता है, और तत्वों को कर्ली ब्रैकेट {} में सूचीबद्ध किया जाता है।

  उदाहरण: A = {1, 2, 3, 4}

• सेट्स के प्रकार (Types of Sets):
  • खाली सेट / शून्य सेट (Empty Set / Null Set - $\emptyset$ or {}): जिसमें कोई तत्व नहीं होता है।
  • सिंगलटन सेट (Singleton Set): जिसमें केवल एक तत्व होता है।
  • परिमित सेट (Finite Set): जिसमें तत्वों की संख्या सीमित होती है।
  • अनंत सेट (Infinite Set): जिसमें तत्वों की संख्या अनंत होती है।
  • समान सेट (Equal Sets): यदि उनमें समान तत्व हों।
  • सबसेट (Subset - $\subseteq$): यदि एक सेट के सभी तत्व दूसरे सेट में भी हों।
  • सुपरसेट (Superset - $\supseteq$): यदि एक सेट में दूसरे सेट के सभी तत्व हों।
  • समुचित सबसेट (Proper Subset - $\subset$): यदि एक सेट दूसरे का सबसेट है लेकिन उसके बराबर नहीं है।
  • यूनिवर्सल सेट (Universal Set - U): एक विशेष संदर्भ में सभी तत्वों का संग्रह।
  • पावर सेट (Power Set - P(A)): एक सेट के सभी संभावित सबसेट्स का सेट।

4.2 वेन डायग्राम (Venn Diagrams)

वेन डायग्राम (Venn diagram) सेटों और उनके बीच संबंधों को दर्शाने के लिए एक चित्रमय प्रतिनिधित्व है। आयत यूनिवर्सल सेट का प्रतिनिधित्व करता है, और वृत्त सेट्स का प्रतिनिधित्व करते हैं।

4.3 सेट्स पर संचालन (Operations on Sets): यूनियन, इंटरसेक्शन, अंतर

• यूनियन (Union - $\cup$): दो सेटों के सभी तत्वों का सेट।

  A $\cup$ B = {x | x $\in$ A या x $\in$ B}

• इंटरसेक्शन (Intersection - $\cap$): दो सेटों में सामान्य तत्वों का सेट।

  A $\cap$ B = {x | x $\in$ A और x $\in$ B}

• अंतर (Difference - - or \): एक सेट में वे तत्व जो दूसरे सेट में नहीं हैं।

  A - B = {x | x $\in$ A और x $\notin$ B}

• पूरक (Complement - A' or $\bar{A}$): यूनिवर्सल सेट में वे तत्व जो सेट A में नहीं हैं।

  A' = U - A

4.4 कार्टेशियन उत्पाद (Cartesian Product)

दो सेटों A और B का कार्टेशियन उत्पाद (Cartesian product) (A $\times$ B) सभी क्रमित जोड़ों (ordered pairs) (a, b) का सेट है जहाँ a $\in$ A और b $\in$ B।

A $\times$ B = {(a, b) | a $\in$ A और b $\in$ B}

उदाहरण: यदि A = {1, 2} और B = {x, y}, तो A $\times$ B = {(1, x), (1, y), (2, x), (2, y)}

4.5 संबंध (Relations): प्रकार (रिफ्लेक्सिव, सिमेट्रिक, ट्रांजिटिव), गुण

एक संबंध (Relation) एक सेट से दूसरे सेट तक क्रमित जोड़ों (ordered pairs) का एक सेट है। इसे कार्टेशियन उत्पाद का एक सबसेट कहा जा सकता है।

• संबंधों के प्रकार (Types of Relations):
  • रिफ्लेक्सिव (Reflexive): यदि प्रत्येक तत्व स्वयं से संबंधित हो (a, a) $\in$ R, सभी a $\in$ A के लिए।
  • सिमेट्रिक (Symmetric): यदि (a, b) $\in$ R, तो (b, a) $\in$ R भी होना चाहिए।
  • एंटी-सिमेट्रिक (Anti-Symmetric): यदि (a, b) $\in$ R और (b, a) $\in$ R, तो a = b होना चाहिए।
  • ट्रांजिटिव (Transitive): यदि (a, b) $\in$ R और (b, c) $\in$ R, तो (a, c) $\in$ R भी होना चाहिए।
  • तुल्यता संबंध (Equivalence Relation): एक संबंध जो रिफ्लेक्सिव, सिमेट्रिक और ट्रांजिटिव तीनों होता है।

4.6 कार्य (Functions): परिभाषा, प्रकार (वन-वन, ऑनटो, इनवर्टिबल)

एक कार्य (Function) एक विशेष प्रकार का संबंध है जहाँ डोमेन (domain) में प्रत्येक तत्व को कोडोमेन (codomain) में ठीक एक तत्व से मैप किया जाता है।

• कार्यों के प्रकार (Types of Functions):
  • वन-वन (One-one / Injective Function): यदि डोमेन के प्रत्येक विशिष्ट तत्व को कोडोमेन के विशिष्ट तत्व से मैप किया जाता है। (f(a) = f(b) $\implies$ a = b)
  • ऑनटो (Onto / Surjective Function): यदि कोडोमेन का प्रत्येक तत्व डोमेन के कम से कम एक तत्व की छवि (image) है (यानी, रेंज = कोडोमेन)।
  • बाइजेक्टिव (Bijective Function): एक कार्य जो वन-वन और ऑनटो दोनों होता है।
  • इनवर्टिबल (Invertible Function): एक बाइजेक्टिव कार्य जिसमें एक व्युत्क्रम कार्य (inverse function) होता है।

5. ग्राफ थ्योरी और ट्रीज (Graph Theory and Trees)

ग्राफ थ्योरी और ट्रीज कंप्यूटर विज्ञान में विभिन्न समस्याओं को मॉडलिंग करने और हल करने के लिए महत्वपूर्ण उपकरण हैं, जैसे नेटवर्क, एल्गोरिदम और डेटा संरचनाएं।

5.1 ग्राफ का परिचय (Introduction to Graphs - ग्राफ का परिचय)

एक ग्राफ (Graph) वर्टेक्स (Vertices) (नोड्स - nodes) के एक सेट और किनारों (Edges) के एक सेट से बना होता है जो वर्टेक्स को जोड़ते हैं।

G = (V, E)

जहाँ V = वर्टेक्स का सेट, E = किनारों का सेट

5.2 ग्राफ के प्रकार (Types of Graphs): सिंपल, अनडायरेक्टेड, डायरेक्टेड, वेटेड

• सिंपल ग्राफ (Simple Graph): जिसमें कोई लूप (loop) और समानांतर किनारे (parallel edges) नहीं होते हैं।
• अनडायरेक्टेड ग्राफ (Undirected Graph): जहाँ किनारे (edges) में कोई दिशा नहीं होती है (दोनों दिशाओं में चला जा सकता है)।
• डायरेक्टेड ग्राफ (Directed Graph / Digraph): जहाँ किनारे में एक विशिष्ट दिशा होती है।
• वेटेड ग्राफ (Weighted Graph): जहाँ प्रत्येक किनारे से एक संख्यात्मक मान (वजन - weight) जुड़ा होता है (जैसे दूरी, लागत)।
• कंप्लीट ग्राफ (Complete Graph): जहाँ वर्टेक्स के प्रत्येक जोड़े के बीच एक किनारा होता है।
• कनेक्टेड ग्राफ (Connected Graph): जहाँ वर्टेक्स के प्रत्येक जोड़े के बीच एक पाथ (path) होता है।

5.3 वर्टेक्स की डिग्री, पाथ, साइकिल (Degree of a Vertex, Path, Cycle)

• वर्टेक्स की डिग्री (Degree of a Vertex): एक वर्टेक्स से जुड़े किनारों की संख्या। डायरेक्टेड ग्राफ में, इन-डिग्री (in-degree) और आउट-डिग्री (out-degree) होती है।
• पाथ (Path): किनारों का एक क्रम जो एक वर्टेक्स को दूसरे से जोड़ता है।
• साइकिल (Cycle): एक पाथ जो एक ही वर्टेक्स से शुरू और खत्म होता है।

5.4 ट्री (Tree): परिभाषा, गुण, प्रकार

एक ट्री (Tree) एक अनडायरेक्टेड ग्राफ है जिसमें कोई साइकिल (cycle) नहीं होती है। यह एक कनेक्टेड, अनसाइक्लिकल ग्राफ है।

• गुण (Properties):
  • एक ट्री जिसमें N वर्टेक्स होते हैं, उसमें N-1 किनारे होते हैं।
  • दो वर्टेक्स के बीच केवल एक ही अद्वितीय पाथ होता है।
  • ट्री एक रूट (root) नोड, पैरेंट (parent) नोड्स, चाइल्ड (child) नोड्स और लीफ (leaf) नोड्स के रूप में पदानुक्रमित संरचना (hierarchical structure) होती है।
• प्रकार (Types):
  • रूटेड ट्री (Rooted Tree): एक ट्री जिसमें एक विशिष्ट वर्टेक्स को रूट के रूप में नामित किया जाता है।
  • स्पैनिंग ट्री (Spanning Tree): एक ग्राफ का एक सबग्राफ जिसमें ग्राफ के सभी वर्टेक्स शामिल होते हैं और जो एक ट्री भी होता है।

5.5 बाइनरी ट्री, ट्रैवर्सल मेथड्स (Binary Trees, Traversal Methods - Inorder, Preorder, Postorder)

एक बाइनरी ट्री (Binary Tree) एक ट्री है जिसमें प्रत्येक नोड में अधिकतम दो बच्चे (children) होते हैं (एक बायां बच्चा और एक दायां बच्चा)।

• ट्रैवर्सल मेथड्स (Traversal Methods): बाइनरी ट्री में नोड्स पर जाने के तरीके।
  • इनऑर्डर ट्रैवर्सल (Inorder Traversal): बायां सबट्री -> रूट -> दायां सबट्री (Left Subtree -> Root -> Right Subtree)
  • प्रीऑर्डर ट्रैवर्सल (Preorder Traversal): रूट -> बायां सबट्री -> दायां सबट्री (Root -> Left Subtree -> Right Subtree)
  • पोस्टऑर्डर ट्रैवर्सल (Postorder Traversal): बायां सबट्री -> दायां सबट्री -> रूट (Left Subtree -> Right Subtree -> Root)

5.6 कंप्यूटर विज्ञान में ट्रीज और ग्राफ्स के अनुप्रयोग (Applications of Trees and Graphs in Computer Science)

• ग्राफ के अनुप्रयोग (Applications of Graphs):
  • नेटवर्क टोपोलॉजी (Network Topology) जैसे LAN, WAN को मॉडल करना।
  • पाथ-फाइंडिंग एल्गोरिदम (Path-finding algorithms) (जैसे Dijkstra's, A* algorithm)।
  • सोशल नेटवर्क विश्लेषण (Social Network Analysis)।
  • मानचित्र और नेविगेशन सिस्टम (Maps and Navigation systems)।
  • डेटाबेस डिजाइन (Database Design)।
• ट्री के अनुप्रयोग (Applications of Trees):
  • फ़ाइल सिस्टम (File Systems) का प्रतिनिधित्व।
  • पार्सिंग (Parsing) और कंपाइलर्स (Compilers) में सिंटैक्स ट्री (Syntax Trees)।
  • डेटाबेस इंडेक्सिंग (Database Indexing) (B-Trees, B+ Trees)।
  • निर्णय लेने के एल्गोरिदम (Decision-making algorithms) में निर्णय ट्री (Decision Trees)।
  • हीप (Heap) डेटा संरचना (प्रायोरिटी क्यू के लिए)।

© 2025 UPPSC LT Grade Teacher Computer Science Exam Notes