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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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.संख्या पद्धतियाँमध्यम

बिट इस तरह सेट करें कि वे 8-बिट 2 के पूरक में −80 संग्रहीत करें। चिह्नरहित संख्या के रूप में पढ़ने पर पैटर्न का मान U क्या है?

N = −808 bit

U =

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

बिट को 0100 0101 XOR 0011 1100 के 8-बिट परिणाम पर सेट करें। दशमलव में परिणाम का मान R क्या है?

0100 0101XOR0011 1100

R =

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

इसकी सत्यमान सारणी की 8 पंक्तियों में से कितनी में (q ↔ (p → r)) ∨ (q ↔ ¬p) सत्य है? इस संख्या को N कहें।

(q ↔ (p → r)) ∨ (q ↔ ¬p)

N =

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

सत्यमान सारणी की 16 पंक्तियों में से कितनी (d ↔ (b → a)) → ((¬c ∧ d) ∧ (c ∧ b)) को सत्य बनाती हैं? इस संख्या को N कहें।

(d ↔ (b → a)) → ((¬c ∧ d) ∧ (c ∧ b))

N =

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

एक 4-से-1 मल्टीप्लेक्सर के चयन निवेश S₁ = A और S₀ = B हैं, और उसके डेटा निवेश I₀ = 0, I₁ = C′, I₂ = 1, I₃ = 1 से जुड़े हैं। A, B और C के 8 संयोजनों में से कितनों के लिए निर्गत F = 1 है? N ज्ञात करें।

I₀ = 0I₁ = C′I₂ = 1I₃ = 1

N =

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

एक तुल्यकालिक mod-5 काउंटर 0, 1, …, 4 गिनता है और फिर 0 पर लौटता है। यह 0 से शुरू होता है। 8 क्लॉक पल्स के बाद वह कौन-सी गिनती Q (दशमलव में) दिखाएगा?

Q₀ = 08N = 5

Q =

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

यूलर का टोशेंट φ(25) ज्ञात करें, यानी 1 से 25 तक के वे पूर्णांक जो 25 से सहअभाज्य हैं।

n = 25 = 5²

φ(25) =

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

एक RSA कुंजी अभाज्य p = 11 और q = 41 तथा सार्वजनिक घातांक e = 23 का उपयोग करती है। निजी घातांक d ज्ञात करें (0 < d < φ(n))।

p = 11q = 41e = 23

d =

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

एक सरल रिकर्सिव फ़ैक्टोरियल फ़ंक्शन fact(n) = n × fact(n − 1) कितना स्टैक स्पेस उपयोग करता है?

AO(n)
BO(1)
CO(log n)
DO(n²)

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

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

Aनिर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं
Bसमस्याएँ जो बहुपदी समय में हल नहीं हो सकतीं
Cसमस्याएँ जिन्हें कोई एल्गोरिदम हल नहीं कर सकता
Dसमस्याएँ जो बहुपदी नहीं हैं

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

एक क्यू दो स्टैक से बनाई गई है: "in" स्टैक पर push करें, और "out" स्टैक से pop करें, ख़ाली होने पर उसे "in" से फिर भरें। प्रति ऑपरेशन एमॉर्टाइज़्ड लागत क्या है?

AO(n)
BO(log n)
CO(n²)
DO(1)

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

एक AVL नोड असंतुलित है क्योंकि उसके बाएँ चाइल्ड का दायाँ सबट्री बहुत ऊँचा हो गया (left-right स्थिति)। कौन-सा सुधार लागू होता है?

Aबाएँ चाइल्ड पर दायाँ रोटेशन, फिर नोड पर बायाँ रोटेशन
Bनोड पर एक एकल बायाँ रोटेशन
Cबाएँ चाइल्ड पर बायाँ रोटेशन, फिर नोड पर दायाँ रोटेशन
Dनोड पर एक एकल दायाँ रोटेशन

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

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

4 × deg 32 × deg 44 × deg 5

L =

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

भारित ग्राफ़ के न्यूनतम स्पैनिंग ट्री का कुल भार W ज्ञात करें।

|V| = 6|E| = 8

W =

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

कौन-सा स्टेटमेंट टेबल की सभी पंक्तियाँ हटाता है, उसकी संरचना रखता है और WHERE क्लॉज़ नहीं ले सकता?

ADROP TABLE
BWHERE क्लॉज़ के साथ DELETE FROM
CALTER TABLE
DTRUNCATE TABLE

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

कौन-सा आइसोलेशन लेवल डर्टी रीड रोकता है लेकिन नॉन-रिपीटेबल रीड की अनुमति देता है?

ARepeatable read
BRead uncommitted
CSerializable
DRead committed

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

कौन-सा DNS रिकॉर्ड प्रकार होस्ट नाम को IPv6 पते से जोड़ता है?

ACNAME
BA
CMX
DAAAA

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

TCP हर कनेक्शन के लिए अप्रत्याशित प्रारंभिक अनुक्रम संख्या (initial sequence number) क्यों चुनता है?

Aहर सेगमेंट के पेलोड को एन्क्रिप्ट करने के लिए
Bपुराने सेगमेंटों से भ्रम से बचने और जाली सेगमेंट डालना कठिन बनाने के लिए
Cडेटा को अधिक कुशलता से संपीड़ित करने के लिए
Dउस कनेक्शन के सेगमेंटों के लिए गंतव्य तक का सबसे अच्छा मार्ग चुनने के लिए

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

नेटवर्क 10.4.236.0/22 को उपसर्ग /29 वाले समान सबनेट में बाँटा गया है। कितने सबनेट N हैं?

10.4.236.0/22/29

N =

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

एक होस्ट का पता 10.20.171.201/29 है। उसके नेटवर्क पते का चौथा ऑक्टेट x क्या है?

10.20.171.201/29

x =

3विलयन

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

उत्तर: U = 176

बिट सेट करना: हर बिट दो की एक घात के बराबर है (128, 64, …, 1)। एक हेक्स अंक ठीक चार बिट होता है, और 8-बिट 2 के पूरक में सबसे बाएँ बिट का मान −128 होता है। बिटवाइज़ संक्रियाएँ हर बिट स्थान पर अलग-अलग काम करती हैं।

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

80 = 0101 0000

उलटा हुआ: 1010 1111

+1 → 1011 0000

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

1011 0000₂ = 256 − 80 = 176

उत्तर

U = 176

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

उत्तर: R = 121

बिट-दर-बिट

XOR वहाँ 1 देता है जहाँ दोनों बिट अलग हों।

0100 0101

XOR 0011 1100

= 0111 1001

परिणाम का मान

0111 1001₂ = 121

उत्तर

R = 121

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

उत्तर: N = 5

सत्यमान सारणियाँ: n अलग-अलग चरों वाले सूत्र की 2ⁿ पंक्तियाँ होती हैं, सत्यमानों के हर संयोजन के लिए एक (1 = सत्य, 0 = असत्य)। भीतर से बाहर की ओर काम करें और हर उप-सूत्र को अपना स्तंभ दें। ¬a मान उलट देता है; a ∧ b केवल तब 1 होता है जब दोनों 1 हों; a ∨ b केवल तब 0 होता है जब दोनों 0 हों; a → b केवल तब 0 होता है जब a = 1 और b = 0; a ↔ b तब 1 होता है जब दोनों पक्ष बराबर हों।

सत्यमान सारणी पंक्ति-दर-पंक्ति

p = 1, q = 1, r = 1: p → r = 1, q ↔ (p → r) = 1, ¬p = 0, q ↔ ¬p = 0, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 1

p = 1, q = 1, r = 0: p → r = 0, q ↔ (p → r) = 0, ¬p = 0, q ↔ ¬p = 0, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 0

p = 1, q = 0, r = 1: p → r = 1, q ↔ (p → r) = 0, ¬p = 0, q ↔ ¬p = 1, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 1

p = 1, q = 0, r = 0: p → r = 0, q ↔ (p → r) = 1, ¬p = 0, q ↔ ¬p = 1, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 1

p = 0, q = 1, r = 1: p → r = 1, q ↔ (p → r) = 1, ¬p = 1, q ↔ ¬p = 1, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 1

p = 0, q = 1, r = 0: p → r = 1, q ↔ (p → r) = 1, ¬p = 1, q ↔ ¬p = 1, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 1

p = 0, q = 0, r = 1: p → r = 1, q ↔ (p → r) = 0, ¬p = 1, q ↔ ¬p = 0, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 0

p = 0, q = 0, r = 0: p → r = 1, q ↔ (p → r) = 0, ¬p = 1, q ↔ ¬p = 0, (q ↔ (p → r)) ∨ (q ↔ ¬p) = 0

मान 1 वाली पंक्तियाँ गिनें

(q ↔ (p → r)) ∨ (q ↔ ¬p): 1, 0, 1, 1, 1, 1, 0, 0

N = 5

उत्तर

N = 5

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

उत्तर: N = 8

स्तंभ

b → a; d ↔ (b → a); ¬c; ¬c ∧ d; c ∧ b; (¬c ∧ d) ∧ (c ∧ b); (d ↔ (b → a)) → ((¬c ∧ d) ∧ (c ∧ b))

a पर बाँटें

a = 1: 4

a = 0: 4

N = 4 + 4 = 8

उत्तर

N = 8

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

उत्तर: N = 5

मल्टीप्लेक्सर: 2ⁿ-से-1 मल्टीप्लेक्सर अपने डेटा निवेशों में से एक को निर्गत तक पहुँचाता है; चयन लाइनें, द्विआधारी संख्या के रूप में पढ़ी जाकर, तय करती हैं कि कौन-सा। चयन S₁S₀ = AB वाले 4-से-1 MUX के लिए F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃। डेटा निवेशों को 0, 1, C या C′ से जोड़ने पर MUX A, B और C का कोई भी फलन बना सकता है, जो एक ही चिप से लॉजिक बनाने का आम तरीका है।

निर्गत व्यंजक

F = A′BC′ + AB′ + AB

F = 1 वाली पंक्तियाँ

ABC = 010, 100, 101, 110, 111

N = 5

उत्तर

N = 5

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

उत्तर: Q = 3

फ़्लिप-फ़्लॉप और काउंटर: फ़्लिप-फ़्लॉप केवल सक्रिय क्लॉक कोर पर बदलता है। 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।

पूरे चक्र

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

8 = 1·5 + 3

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

Q = (0 + 3) mod 5 = 3

Q = 011₂

उत्तर

Q = 3

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

उत्तर: φ(25) = 20

प्रतिलोम और सर्वांगसमताएँ: 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)।

अभाज्य गुणनखंड

25 = 5²

टोशेंट

φ(25) = 25 − 5 = 20

उत्तर

φ(25) = 20

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

उत्तर: d = 87

मॉड्यूलर घात और RSA: aᵏ mod n बार-बार वर्ग करके निकालें: k को द्विआधारी में लिखें, वर्ग करें, हर चरण के बाद घटाएँ और जिन घातों का बिट 1 है उन्हें गुणा करें। फर्मा: अभाज्य p के लिए, जो a को विभाजित नहीं करता, aᵖ⁻¹ ≡ 1 (mod p), इसलिए घातांक को p − 1 के मापांक में घटाया जा सकता है। RSA: अभाज्य p और q चुनें, n = p·q और φ(n) = (p − 1)(q − 1); सार्वजनिक घातांक e, φ(n) से सहअभाज्य है, और निजी घातांक d = e⁻¹ mod φ(n) है। c = mᵉ mod n से एन्क्रिप्ट करें और m = cᵈ mod n से डिक्रिप्ट करें।

मापांक और टोशेंट

n = 11·41 = 451

φ(n) = 10·40 = 400

विस्तारित यूक्लिडीय एल्गोरिथ्म

r = 400, t = 0

r = 23, q = 17, t = 1

r = 9, q = 2, t = −17

r = 5, q = 1, t = 35

r = 4, q = 1, t = −52

r = 1, q = 4, t = 87

निजी घातांक

d = 87

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

L + 40 = 2(L + 10) − 2

L = 22

उत्तर

L = 22

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

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

उत्तर: W = 24

सबसे छोटे पथ और स्पैनिंग ट्री: डाइक्स्ट्रा का एल्गोरिथ्म हर चक्र में एक शीर्ष निर्धारित करता है: सबसे छोटी अस्थायी दूरी वाला अनिर्धारित शीर्ष। तब उसकी दूरी अंतिम होती है, और हर पड़ोसी v को d(v) = min(d(v), d(u) + w(u, v)) मिलता है। क्रुस्कल का एल्गोरिथ्म कोरों को हल्की से भारी की ओर लेकर और चक्र बनाने वाली हर कोर छोड़कर न्यूनतम स्पैनिंग ट्री बनाता है; प्रिम का एल्गोरिथ्म प्रारंभिक शीर्ष से एक वृक्ष बढ़ाता है और हमेशा उससे बाहर जाने वाली सबसे हल्की कोर जोड़ता है। n शीर्षों के स्पैनिंग ट्री में n − 1 कोरें होती हैं।

क्रुस्कल का एल्गोरिथ्म

BE (1): लें

EF (3): लें

AB (4): लें

B · पुराने सेगमेंटों से भ्रम से बचने और जाली सेगमेंट डालना कठिन बनाने के लिए

19.IPv4 सबनेटिंग

उत्तर: N = 128

IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).

उधार लिए गए बिट

29 − 22 = 7

सबनेटों की संख्या

N = 2⁷ = 128

उत्तर

N = 128

हर /29 सबनेट में 2³ − 2 = 6 उपयोगी होस्ट हैं।

20.IPv4 सबनेटिंग

उत्तर: x = 200

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

ब्लॉक आकार

2³ = 8

इस होस्ट का सबनेट

नेटवर्क: ⌊201/8⌋·8 = 200

ब्रॉडकास्ट: 200 + 8 − 1 = 207

उपयोगी होस्ट: 201 … 206

उत्तर

x = 200

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