कंप्यूटर विज्ञान के मूल सिद्धांत: क्रैम पैक

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 20 अभ्यास प्रश्न, पूरे हल पीछे दिए गए हैं।

नए प्रश्न कोर्स पर वापस जाएँ

प्रिंट विंडो में “PDF के रूप में सहेजें” चुनें, ताकि एक प्रति आपके डिवाइस पर रहे।

1सूत्र और विधियाँ

संख्या पद्धतियाँ

स्थानीय मान: बाइनरी 2^k, ऑक्टल 8^k, हेक्स 16^k
दशमलव में: Σ d_k·b^k
दशमलव से: आधार से भाग दें, शेषफल नीचे से ऊपर पढ़ें
हेक्स ↔ बाइनरी: एक हेक्स अंक = 4 बिट
टू’ज़ कॉम्प्लीमेंट: बिट उलटें और 1 जोड़ें

प्रस्ताविक तर्क और उपपत्तियाँ

सत्यमान सारणी की पंक्तियाँ: 2ⁿ
निहितार्थ: p → q ≡ ¬p ∨ q ≡ ¬q → ¬p
निषिद्ध निहितार्थ: ¬(p → q) ≡ p ∧ ¬q
द्विनिहितार्थ: p ↔ q ≡ (p → q) ∧ (q → p)
डी मॉर्गन: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q
वितरण नियम: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
निषिद्ध परिमाणक: ¬∀x P(x) ≡ ∃x ¬P(x), ¬∃x P(x) ≡ ∀x ¬P(x)
मोडस पोनेंस, मोडस टोलेंस: p → q, p ⊢ q; p → q, ¬q ⊢ ¬p

विधि

अलग-अलग चरों को गिनें: सत्यमान सारणी में 2ⁿ पंक्तियाँ होती हैं, जो सभी के 1 होने से शुरू होती हैं।
हर उप-सूत्र को अपना अलग स्तंभ दें और स्तंभों को भीतर से बाहर की ओर भरें।
हर संयोजक का नियम लगाएँ: → केवल 1 → 0 के लिए 0 होता है, ↔ तब 1 होता है जब दोनों पक्ष समान हों।
तुल्यता के लिए अंतिम स्तंभों की पंक्ति-दर-पंक्ति तुलना करें; किसी तर्क के लिए केवल उन्हीं पंक्तियों को देखें जिनमें हर आधार-वाक्य 1 हो।
परिमाणक वाले कथन का निषेध करने के लिए ¬ को भीतर ले जाएँ, ∀ और ∃ आपस में बदलें, और भीतरी सूत्र का निषेध करें।

डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉप

मूल गेट: A·B, A + B, A′, (A·B)′, (A + B)′, A ⊕ B
बूलीय नियम: X + X′ = 1, X·X′ = 0, X + XY = X, XY + XY′ = X
डी मॉर्गन: (X·Y)′ = X′ + Y′, (X + Y)′ = X′·Y′
कार्नो मानचित्र का क्रम: 00, 01, 11, 10 (Gray code)
2ᵏ खानों का समूह: k चर खो देता है
4-से-1 मल्टीप्लेक्सर: F = A′B′I₀ + A′BI₁ + AB′I₂ + ABI₃
फ़्लिप-फ़्लॉप: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
काउंटर: n-बिट: 2ⁿ अवस्थाएँ; mod-N: सबसे छोटा n जिसमें 2ⁿ ≥ N; f_out = f_clk/N
रिपल काउंटर: f_max = 1/(n·t_pd)
रिंग और जॉनसन काउंटर: n और 2n अवस्थाएँ

विधि

परिपथ के लिए निवेशों से निर्गत तक एक-एक गेट करके काम करें और हर तार पर मान लिखें, या उसका व्यंजक लिखें और सत्यमान सारणी भरें।
सरलीकरण के लिए 1 (और डोंट-केयर को X के रूप में) को ग्रे-कोड पंक्तियों और स्तंभों वाले कार्नो मानचित्र में रखें: 00, 01, 11, 10।
1 को 1, 2, 4, 8 या 16 खानों के जितने कम और जितने बड़े संभव हों उतने समूहों से ढकें, किनारों से लिपटते हुए; हर समूह एक गुणन पद है जो उन चरों से बना है जो स्थिर रहते हैं। POS रूप के लिए 0 को समूहित करें।
फ़्लिप-फ़्लॉप और काउंटरों के लिए हर सक्रिय क्लॉक कोर पर निवेश पढ़ें, हर कोर के बाद अवस्था लिखें, और याद रखें कि n-बिट काउंटर 2ⁿ अवस्थाओं के बाद लौट जाता है।

संख्या सिद्धांत और मॉड्यूलर अंकगणित

शेषफल सहित विभाजन: a = q·n + r, 0 ≤ r < n
यूक्लिड: gcd(a, b) = gcd(b, a mod b)
लघुत्तम समापवर्त्य: lcm(a, b) = a·b/gcd(a, b)
व्युत्क्रम: a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
रैखिक सर्वांगसमता: a·x ≡ b → x ≡ a⁻¹·b (mod n)
यूलर का टोशेंट: φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
फर्मा: aᵖ⁻¹ ≡ 1 (mod p)
RSA: n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n

विधि

पहले हर संख्या को n के मापांक में घटाएँ; शेषफल 0 से n − 1 के बीच होते हैं।
gcd के लिए यूक्लिड एल्गोरिथ्म से बार-बार भाग दें; अंतिम अशून्य शेषफल ही gcd है।
प्रतिलोम के लिए विस्तारित एल्गोरिथ्म चलाएँ और a का गुणांक रखें; ऋणात्मक हो तो n जोड़ें।
a·x ≡ b को हल करने के लिए a⁻¹ से गुणा करें; दो सर्वांगसमताओं को x = r₁ + m₁k लिखकर मिलाएँ।
घातों के लिए घातांक को द्विआधारी में लिखें और बार-बार वर्ग करें; RSA में d = e⁻¹ mod φ(n) होता है, जहाँ φ(n) = (p − 1)(q − 1)।

ग्राफ़ सिद्धांत

हैंडशेक लेमा: Σ deg(v) = 2|E|
पूर्ण ग्राफ़: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
नियमित ग्राफ़: |E| = n·k/2
वृक्ष और वन: |E| = n − 1, |E| = n − c
वृक्ष के पत्ते: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर: परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
K_n में हैमिल्टन परिपथ: (n − 1)!/2
डाइक्स्ट्रा अद्यतन: d(v) = min(d(v), d(u) + w(u, v))
लंबाई L की वॉक: (Mᴸ)_ij

विधि

हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।

IPv4 सबनेटिंग

प्रति सबनेट होस्ट: 2^{(32 − prefix)} − 2 (/31: 2, /32: 1)
ब्लॉक आकार: 256 − (mask octet)
नेटवर्क पता: IP AND मास्क
ब्रॉडकास्ट पता: IP OR (NOT mask): सभी होस्ट बिट 1
n उधार लिए बिट से सबनेट: 2ⁿ

2अभ्यास प्रश्न

1.संख्या पद्धतियाँमध्यम

−68 को 8-बिट दो के पूरक पैटर्न के रूप में लिखें। पैटर्न को अचिह्नित द्विआधारी संख्या के रूप में पढ़ें: दशमलव में इसका मान U क्या है?

N = −688 bit

U =

2.संख्या पद्धतियाँकठिन

एक असंपीड़ित छवि 256 × 256 पिक्सेल की है, प्रति पिक्सेल 8 बिट। यह KiB में (1 KiB = 1024 बाइट) कितनी मेमोरी M लेती है?

256 × 256 px8 bit/px1 KiB = 1024 B

M = KiB

3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम

कौन-सा सूत्र (a ∨ b) → c के तार्किक रूप से तुल्य है? उस पर क्लिक करें।

(a ∨ b) → c

1(a ∧ b) → c
2(a → c) ∨ (b → c)
3(a → c) ∧ (b → c)
4a ∨ (b → c)

4.प्रस्ताविक तर्क और उपपत्तियाँकठिन

निषेध को पूरी तरह भीतर ले जाने पर कौन-सा कथन ¬∃x F(x) के तुल्य है? उस पर क्लिक करें।

¬∃x F(x)

1∃x ¬F(x)
2∃x F(x)
3∀x F(x)
4∀x ¬F(x)

5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम

F(A, B, C, D) = Σm(0, 1, 5, 8, 9, 11, 13) का न्यूनतम गुणनफलों का योग (SOP) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कुल कितने लिटरल L हैं (प्राइम वाला चर एक लिटरल गिना जाता है)?

F(A, B, C, D) = Σm(0, 1, 5, 8, 9, 11, 13)

L =

6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन

एक 3-बिट द्विआधारी डाउन काउंटर 5 (दशमलव, Q = 101) से शुरू होता है। 25 क्लॉक पल्स के बाद वह कौन-सी गिनती Q (दशमलव में) दिखाएगा?

Q₀ = 525n = 3

Q =

7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

38x ≡ 45 (mod 89) हल करें। हल x दें, जहाँ 0 < x < 89।

38x ≡ 45 (mod 89)

x =

8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन

{0, 1, …, 63} में 62x ≡ 6 (mod 64) के कितने हल N हैं?

62x ≡ 6 (mod 64)

N =

9.एल्गोरिदम और जटिलतामध्यम

एक्टिविटी सिलेक्शन समस्या में कौन-सा ग्रीडी नियम हमेशा अधिकतम संख्या में न-अतिव्यापी गतिविधियाँ देता है?

Aपहले सबसे कम अतिव्यापन वाली गतिविधि चुनें, फिर संगत गतिविधियों के साथ दोहराएँ
Bसबसे जल्दी शुरू होने वाली गतिविधि चुनें
Cसबसे जल्दी समाप्त होने वाली गतिविधि चुनें, फिर संगत गतिविधियों के साथ दोहराएँ
Dपहले सबसे छोटी गतिविधि चुनें

10.एल्गोरिदम और जटिलताकठिन

क्लास P की कौन-सी परिभाषा सही है?

Aसमस्याएँ जिनके समाधान जाँचे तो जा सकते हैं पर बहुपदी समय में कभी खोजे नहीं जा सकते
Bसमस्याएँ जो समानांतर रूप से हल हो सकती हैं
Cनिर्णय समस्याएँ जो एक नियतात्मक (deterministic) एल्गोरिदम द्वारा बहुपदी समय में हल हो सकती हैं
Dसमस्याएँ जिन्हें हर कंप्यूटर पर घातांकी समय चाहिए

11.डेटा संरचनाएँमध्यम

डेप्थ-फ़र्स्ट सर्च (पुनरावृत्त संस्करण) किस डेटा संरचना का उपयोग करती है?

Aक्यू
Bकेवल हैश टेबल
Cहीप
Dस्टैक

12.डेटा संरचनाएँकठिन

कौन-सी संरचना ऐरे में आकार k की हर विंडो का अधिकतम कुल O(n) में निकालने देती है?

Aविंडो के तत्वों की सिंगली लिंक्ड लिस्ट
Bमान के घटते क्रम में इंडेक्स रखने वाला डीक
Cहर विंडो के लिए फिर से बनाया गया मिन-हीप
Dखिसकाकर अपडेट किया जाने वाला सॉर्टेड ऐरे

13.ग्राफ़ सिद्धांतमध्यम

एक वृक्ष में घात 3 वाले 3 शीर्ष, घात 4 वाले 3 शीर्ष है, और उसके बाकी सभी शीर्ष पत्ते (घात 1) हैं। उसमें कितने पत्ते L हैं?

3 × deg 33 × deg 4

L =

14.ग्राफ़ सिद्धांतकठिन

लंबाई 2 की कितनी वॉक B से A तक जाती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।

M = संलग्नता आव्यूहL = 2

N =

15.डेटाबेस और SQLमध्यम

द्वितीय नॉर्मल फ़ॉर्म (2NF) क्या हटाता है?

Aकिसी अन्य नॉन-की कॉलम के माध्यम से नॉन-की कॉलमों के बीच सकर्मक (transitive) निर्भरताएँ
Bफ़ॉरेन की
Cसभी NULL मान
Dकंपोज़िट की के किसी भाग पर नॉन-की कॉलमों की आंशिक निर्भरताएँ

16.डेटाबेस और SQLकठिन

किसी क्वेरी के लिए कवरिंग इंडेक्स (covering index) क्या है?

Aऐसा इंडेक्स जो हर टेबल के हर कॉलम को कवर करता है
Bऐसा इंडेक्स जो हर रात फिर से बनाया जाता है
Cऐसा इंडेक्स जिसमें क्वेरी को आवश्यक सभी कॉलम हों, ताकि स्वयं टेबल पढ़ने की आवश्यकता न हो
Dकेवल प्राइमरी की पर इंडेक्स

17.कंप्यूटर नेटवर्कमध्यम

किसी होस्ट पर डिफ़ॉल्ट गेटवे की क्या भूमिका है?

Aयह वह राउटर है जिसका उपयोग अन्य नेटवर्कों के ट्रैफ़िक के लिए होता है
Bयह DNS सर्वर है
Cयह MAC पते आवंटित करता है
Dयह वह स्विच पोर्ट है जिससे होस्ट जुड़ा है

18.कंप्यूटर नेटवर्ककठिन

TCP/IP मॉडल में कौन-सी परत पोर्ट नंबर जोड़ती है?

Aएप्लिकेशन परत
Bलिंक परत
Cट्रांसपोर्ट परत
Dइंटरनेट परत

19.IPv4 सबनेटिंगमध्यम

नेटवर्क 192.168.10.0/24 को कम से कम 3 बराबर सबनेट में बाँटना है। यदि आप जितनी कम हो सकें उतनी बिटें उधार लें, तो हर सबनेट में कितने उपयोगी होस्ट H होंगे?

192.168.10.0/243 subnets

H =

20.IPv4 सबनेटिंगकठिन

एक राउटर के पास इन नेटवर्कों के लिए रूट हैं: 10.44.153.0/24, 10.44.154.0/24, 10.44.155.0/24, 10.44.156.0/24, 10.44.157.0/24, 10.44.158.0/24, 10.44.159.0/24। इन सबको कवर करने वाले एकल सारांश रूट की सबसे लंबी उपसर्ग लंबाई p क्या है?

10.44.153.0/24 … 10.44.159.0/24

p =

3विलयन

1.संख्या पद्धतियाँ

उत्तर: U = 188

स्थानीय मान संख्या पद्धतियाँ: हर अंक का मान उसके मान गुणा आधार की एक घात होता है। द्विआधारी में स्थान 1, 2, 4, 8, 16, … के होते हैं; षोडशआधारी में 1, 16, 256, …, जहाँ A–F का अर्थ 10–15 है। 8-बिट दो के पूरक में सबसे बाईं बिट +128 के बजाय −128 की होती है; ऋणात्मक संख्याएँ इसी तरह संग्रहीत होती हैं।

उलटें और एक जोड़ें

68 = 0100 0100

उलटा हुआ: 1011 1011

+1 → 1011 1100

अचिह्नित रूप में पढ़ें

1011 1100₂ = 256 − 68 = 188

उत्तर

U = 188

2.संख्या पद्धतियाँ

उत्तर: M = 64 KiB

बिट और बाइट

256·256·8 = 524288 bit = 65536 B

KiB में बदलें

65536/1024 = 64 KiB

उत्तर

M = 64 KiB

3.प्रस्ताविक तर्क और उपपत्तियाँ

उत्तर: (a → c) ∧ (b → c)

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 1 होती है, विरोधोक्ति हर पंक्ति में 0, और आपातिक कथन इनमें से कुछ नहीं होता। उपयोगी नियम: डी मॉर्गन, ¬(a ∧ b) ≡ ¬a ∨ ¬b और ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (प्रतिधनात्मक); ¬(a → b) ≡ a ∧ ¬b; और वितरण नियम, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)।

नियम

(a ∨ b) → c में जब भी a या b में से कोई भी सत्य हो तब c चाहिए: (a → c) ∧ (b → c)।

(a ∨ b) → c ≡ (a → c) ∧ (b → c)

सत्यमान सारणी से जाँच

a = 1, b = 1, c = 1: 1 | 1 1 1 1

a = 1, b = 1, c = 0: 0 | 0 0 0 1

a = 1, b = 0, c = 1: 1 | 1 1 1 1

a = 1, b = 0, c = 0: 0 | 1 1 0 1

a = 0, b = 1, c = 1: 1 | 1 1 1 1

a = 0, b = 1, c = 0: 0 | 1 1 0 0

a = 0, b = 0, c = 1: 1 | 1 1 1 1

a = 0, b = 0, c = 0: 1 | 1 1 1 1

उत्तर

(a → c) ∧ (b → c)

पट्टी के बाद के स्तंभ विकल्प हैं, दिखाए गए क्रम में।

4.प्रस्ताविक तर्क और उपपत्तियाँ

उत्तर: ∀x ¬F(x)

परिमाणक और तर्क: ¬∀x P(x) ≡ ∃x ¬P(x) और ¬∃x P(x) ≡ ∀x ¬P(x)। निषेध को भीतर ले जाएँ, उसके रास्ते में आने वाले हर परिमाणक को बदलें, और भीतरी सूत्र का निषेध प्रस्ताविक नियमों से करें, जैसे ¬(a → b) ≡ a ∧ ¬b। तर्क वैध होता है जब उन सभी पंक्तियों में निष्कर्ष 1 हो जिनमें सभी आधार-वाक्य 1 हों। सत्य आधार-वाक्यों और असत्य निष्कर्ष वाली एक भी पंक्ति प्रति-उदाहरण है और दिखाती है कि तर्क अवैध है।

निषेध को भीतर ले जाएँ

¬∃x F(x) ≡ ∀x ¬F(x)

उत्तर

∀x ¬F(x)

बाकी विकल्प या तो किसी परिमाणक को अपरिवर्तित रखते हैं, या परिमाणकों का क्रम बदल देते हैं, या भीतरी सूत्र का निषेध गलत करते हैं।

5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉप

उत्तर: L = 7

कार्नो मानचित्र: खाने ग्रे कोड (00, 01, 11, 10) में क्रमबद्ध होते हैं, इसलिए पड़ोसी खाने, किनारों के आर-पार वाले भी, ठीक एक चर में भिन्न होते हैं। 1 को 1, 2, 4, 8 या 16 खानों के आयतों में समूहित करें, जितने बड़े और जितने कम समूह हो सकें, जब तक हर 1 ढक न जाए। हर समूह एक गुणन पद है: वे चर जो उसके भीतर स्थिर रहते हैं। 2ᵏ खानों का समूह k चर खो देता है। डोंट-केयर (X) का उपयोग समूह बड़े करने के लिए किया जा सकता है पर उन्हें ढकना ज़रूरी नहीं है। इसके बजाय 0 को समूहित करने से न्यूनतम POS रूप मिलता है।

1 को समूहित करें

हर समूह 2ᵏ खानों का आयत होता है; किनारे के खाने विपरीत किनारे के खानों के पड़ोसी होते हैं।

C′D

B′C′

AB′D

न्यूनतम SOP रूप

F = C′D + B′C′ + AB′D

L = 7

उत्तर

L = 7

6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉप

उत्तर: Q = 4

फ़्लिप-फ़्लॉप और काउंटर: फ़्लिप-फ़्लॉप केवल सक्रिय क्लॉक कोर पर बदलता है। D अपना निवेश कॉपी करता है (Q⁺ = D); T तब टॉगल करता है जब T = 1; JK 00 पर स्थिर रहता है, 01 पर रीसेट करता है, 10 पर सेट करता है और 11 पर टॉगल करता है। n-बिट द्विआधारी काउंटर की 2ⁿ अवस्थाएँ होती हैं और वह 2ⁿ के मापांक में गिनता है; mod-N काउंटर 0, 1, …, N − 1 तक जाकर फिर 0 पर लौटता है, और उसे ऐसे सबसे छोटे n फ़्लिप-फ़्लॉप चाहिए जिसमें 2ⁿ ≥ N हो। रिपल काउंटर का हर चरण आवृत्ति को आधा कर देता है, इसलिए mod-N काउंटर का अंतिम निर्गत f_clk/N पर चलता है। n फ़्लिप-फ़्लॉप वाले जॉनसन काउंटर की 2n अवस्थाएँ होती हैं, रिंग काउंटर की n।

पूरे चक्र

हर 8 पल्स काउंटर को उसी अवस्था में वापस ले आते हैं।

25 = 3·8 + 1

शेष पल्स के बाद गिनती

Q = (5 − 1) mod 8 = 4

Q = 100₂

उत्तर

Q = 4

7.संख्या सिद्धांत और मॉड्यूलर अंकगणित

उत्तर: x = 41

प्रतिलोम और सर्वांगसमताएँ: a का n के मापांक में प्रतिलोम ठीक तब होता है जब gcd(a, n) = 1। विस्तारित यूक्लिडीय एल्गोरिथ्म 1 = s·n + t·a लिखता है, और तब a⁻¹ ≡ t (mod n)। gcd(a, n) = 1 वाली सर्वांगसमता a·x ≡ b (mod n) का हल x ≡ a⁻¹·b है। सहअभाज्य मापांकों वाली दो सर्वांगसमताओं x ≡ r₁ (mod m₁) और x ≡ r₂ (mod m₂) का m₁·m₂ के मापांक में एक हल होता है (चीनी शेषफल प्रमेय)। यूलर का φ(n) 1 से n तक की उन संख्याओं को गिनता है जो n से सहअभाज्य हैं: φ(n) = n·∏(1 − 1/p)।

38 का प्रतिलोम

r = 89, t = 0

r = 38, q = 2, t = 1

r = 13, q = 2, t = −2

r = 12, q = 1, t = 5

r = 1, q = 12, t = −7

38⁻¹ ≡ 82 (mod 89)

हल करें

x ≡ 82·45 = 3690 ≡ 41 (mod 89)

जाँच: 38·41 = 1558 ≡ 45 (mod 89)

उत्तर

x = 41

8.संख्या सिद्धांत और मॉड्यूलर अंकगणित

उत्तर: N = 2

gcd से भाग दें

gcd(62, 64) = 2

31x ≡ 3 (mod 32)

घटी हुई सर्वांगसमता हल करें

31⁻¹ ≡ 31 (mod 32) → x ≡ 29 (mod 32)

64 के मापांक में हल

x ∈ {29, 61}

वृक्ष के लिए हैंडशेक लेमा

L + 21 = 2(L + 6) − 2

L = 11

उत्तर

L = 11

शॉर्टकट: L = 2 + Σ (d − 2), घात d ≥ 3 वाले शीर्षों पर।

14.ग्राफ़ सिद्धांत

उत्तर: N = 1

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। K_n में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

संलग्नता आव्यूह

A: 0 1 1 0 0

B: 1 0 1 1 1

C · ट्रांसपोर्ट परत

19.IPv4 सबनेटिंग

उत्तर: H = 62

IPv4 सबनेटिंग: एक पते में 32 बिट होती हैं। उपसर्ग /p बताता है कि शुरुआती कितनी बिटें नेटवर्क की पहचान करती हैं; शेष 32 − p बिटें होस्ट को क्रमांकित करती हैं। एक सबनेट में 2³²⁻ᵖ पते होते हैं, पर पहला (नेटवर्क पता) और अंतिम (ब्रॉडकास्ट पता) होस्ट को नहीं दिए जा सकते, इसलिए 2³²⁻ᵖ − 2 होस्ट आते हैं। अपवाद: /31 (पॉइंट-टू-पॉइंट लिंक, RFC 3021) अपने दोनों 2 पतों का उपयोग होस्ट के लिए करता है, और /32 केवल एक पता है (एक होस्ट या लूपबैक)।

उधार ली जाने वाली बिटें

2² = 4 ≥ 3 → b = 2, /26

प्रति सबनेट होस्ट

2⁶ − 2 = 62

उत्तर

H = 62

20.IPv4 सबनेटिंग

उत्तर: p = 21

रूट सारांशीकरण: सारांश रूट a.b.c.0/p उन सभी नेटवर्कों को कवर करता है जिनके पहले p बिट मेल खाते हैं। पहले और अंतिम नेटवर्क के भिन्न ऑक्टेट को बाइनरी में लिखें; साझा अग्रणी बिटों की संख्या, उससे पहले के ऑक्टेटों के बिट जोड़कर, सबसे लंबा सारांश उपसर्ग है।

बिटों की तुलना करें

153 = 10011001

159 = 10011111

साझा अग्रणी बिट: 5

उपसर्ग लंबाई

p = 16 + 5 = 21

उत्तर

p = /21

सारांश रूट: 10.44.152.0/21 (यह 1 ऐसे नेटवर्क भी कवर करता है जो सूची में नहीं हैं)।

ExamProblems · examproblems.com/courses/computer-science-fundamentals