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

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

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

N = −408 bit

U =

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

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

0011 0100OR1100 0010

R =

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

कौन-सा सूत्र q ↔ r के तार्किक रूप से तुल्य है? उस पर क्लिक करें।

q ↔ r

1q ∧ r
2(q → r) ∨ (r → q)
3(q → r) ∧ (¬r → ¬q)
4(q → r) ∧ (r → q)

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

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

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

N =

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

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

F(A, B, C, D) = Σm(2, 3, 4, 5, 8, 9, 10, 11, 12)

L =

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

F(A, B, C, D) = Σm(0, 1, 2, 3, 6, 10, 12, 13) + d(7, 8, 14, 15) का न्यूनतम SOP रूप ज्ञात करें, जहाँ d डोंट-केयर स्थितियों को दर्शाता है। उसमें कितने लिटरल L हैं?

F(A, B, C, D) = Σm(0, 1, 2, 3, 6, 10, 12, 13) + d(7, 8, 14, 15)

L =

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

83 के मापांक में 15 का प्रतिलोम ज्ञात करें: वह संख्या x जिसके लिए 0 < x < 83 और 15·x ≡ 1 (mod 83)।

a = 15n = 83

15⁻¹ mod 83 =

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

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

p = 5q = 41e = 17

d =

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

n तत्वों के ऐरे के लिए मर्ज सॉर्ट के रिकर्शन में कितने स्तर होते हैं?

Aलगभग √n
Bलगभग n
Cलगभग log₂ n
Dलगभग n / 2

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

बाइनरी काउंटर को बढ़ाने (increment) की एमॉर्टाइज़्ड लागत क्या है, यह देखते हुए कि एक वृद्धि कई बिट पलट सकती है?

Aप्रति वृद्धि O(n)
Bप्रति वृद्धि O(n log n)
Cप्रति वृद्धि O(1)
Dप्रति वृद्धि O(log n)

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

AVL ट्री और रेड-ब्लैक ट्री किस बात की गारंटी देते हैं?

Aकिसी भी नोड के दो चाइल्ड नहीं होते
Bपुनर्संतुलन द्वारा O(log n) ऊँचाई
Cहर स्थिति में स्थिर समय में खोज
Dकुंजियाँ इंसर्शन के क्रम में संग्रहीत होती हैं

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

union by rank या path compression के बिना, n तत्वों वाली union-find संरचना में एक find की वर्स्ट-केस लागत क्या है?

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

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

एक संबद्ध ग्राफ़ में 11 शीर्ष और 13 कोरें हैं। स्पैनिंग ट्री बचाने के लिए कितनी कोरें k हटानी होंगी?

|V| = 11|E| = 13

k =

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

क्रुस्कल का एल्गोरिथ्म न्यूनतम स्पैनिंग ट्री बनाता है। उस कोर पर क्लिक करें जिसे वह कोर संख्या 3 के रूप में जोड़ता है; छोड़ी गई कोरें नहीं गिनी जातीं।

k = 3

1कोर AB
2कोर AC
3कोर BC
4कोर BD
5कोर CE
6कोर DE
7कोर BE

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

LEFT JOIN क्या लौटाता है?

Aवे पंक्तियाँ जो किसी भी टेबल में मेल नहीं खातीं
Bकेवल दाईं टेबल की सभी पंक्तियाँ
Cबाईं टेबल की सभी पंक्तियाँ और दाईं टेबल की मेल खाने वाली पंक्तियाँ, जहाँ मेल न हो वहाँ NULL के साथ
Dदोनों टेबलों की केवल मेल खाने वाली पंक्तियाँ

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

3NF की तुलना में टेबलों को BCNF में विघटित करने की एक ज्ञात कमी क्या है?

Aकुछ फ़ंक्शनल डिपेंडेंसी अब एक अकेली टेबल के भीतर जाँची नहीं जा सकतीं
BBCNF, 3NF से अधिक अतिरेक (redundancy) की अनुमति देता है
CBCNF टेबलों में प्राइमरी की नहीं हो सकती
Dवापस जोड़ने पर विघटन हमेशा डेटा खो देता है

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

एक /24 IPv4 नेटवर्क में कितने उपयोग योग्य होस्ट पते होते हैं?

A255
B254
C256
D252

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

इंटरनेट पर BGP मुख्य रूप से क्या करता है?

Aनामों को पतों में resolve करता है
Bस्वायत्त प्रणालियों (autonomous systems) के बीच रूटिंग जानकारी का आदान-प्रदान करता है
Cराउटरों के बीच डेटा एन्क्रिप्ट करता है
Dइंटरनेट प्रदाताओं के माध्यम से घरेलू उपयोगकर्ताओं को IP पते आवंटित करता है

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

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

172.31.0.0/16/19

N =

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

एक होस्ट का पता 10.20.136.47/30 है। उसके सबनेट के अंतिम उपयोगी होस्ट पते का चौथा ऑक्टेट x क्या है?

10.20.136.47/30

x =

3विलयन

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

उत्तर: U = 216

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

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

40 = 0010 1000

उलटा हुआ: 1101 0111

+1 → 1101 1000

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

1101 1000₂ = 256 − 40 = 216

उत्तर

U = 216

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

उत्तर: R = 246

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

बिट-दर-बिट

OR वहाँ 1 देता है जहाँ कम से कम एक बिट 1 हो।

0011 0100

OR 1100 0010

= 1111 0110

परिणाम का मान

1111 0110₂ = 246

उत्तर

R = 246

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

उत्तर: (q → r) ∧ (r → q)

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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 का अर्थ है कि निहितार्थ दोनों दिशाओं में सत्य है: (a → b) ∧ (b → a)।

q ↔ r ≡ (q → r) ∧ (r → q)

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

q = 1, r = 1: 1 | 1 1 1 1

q = 1, r = 0: 0 | 0 1 0 0

q = 0, r = 1: 0 | 0 1 1 0

q = 0, r = 0: 1 | 0 1 1 1

उत्तर

(q → r) ∧ (r → q)

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

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

उत्तर: N = 10

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

स्तंभ

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

a पर बाँटें

a = 1: 7

a = 0: 3

N = 7 + 3 = 10

उत्तर

N = 10

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

उत्तर: L = 10

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

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

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

B′C

BC′D′

AB′

A′BC′

न्यूनतम SOP रूप

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

L = 10

उत्तर

L = 10

उसी आकार का एक और समूहन संभव है; उसमें पदों और लिटरलों की संख्या वही है।

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

उत्तर: L = 6

प्रमुख प्रभाव्य

1 और X से बनने वाले सबसे बड़े समूह।

CD′, B′D′, BC, AD′, A′C, A′B′, AB

न्यूनतम आवरण

F = CD′ + A′B′ + AB

L = 6

उत्तर

L = 6

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

उत्तर: 15⁻¹ mod 83 = 72

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

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

हर शेषफल r को r ≡ t·15 (mod 83) के रूप में लिखा जाता है।

r = 83, t = 0

r = 15, q = 5, t = 1

r = 8, q = 1, t = −5

r = 7, q = 1, t = 6

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

व्युत्क्रम

1 ≡ −11·15 (mod 83)

x = 72

जाँच: 15·72 = 1080 = 13·83 + 1

उत्तर

15⁻¹ mod 83 = 72

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

उत्तर: d = 113

मॉड्यूलर घात और 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 = 5·41 = 205

φ(n) = 4·40 = 160

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

r = 160, t = 0

r = 17, q = 9, t = 1

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

r = 3, q = 2, t = 19

r = 1, q = 3, t = −47

निजी घातांक

d = 113

स्पैनिंग ट्री की कोरें

11 − 1 = 10

हटाई जाने वाली कोरें

k = 13 − 10 = 3

उत्तर

k = 3

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

उत्तर: कोर CE

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

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

1. BD (1)

2. AC (2)

3. CE (4)

4. BE (6)

BGP अंतर-डोमेन रूटिंग प्रोटोकॉल है; स्वायत्त प्रणालियाँ पहुँच योग्य प्रीफ़िक्स का विज्ञापन करती हैं और नीतियों के आधार पर मार्ग चुनती हैं।

उत्तर

B · स्वायत्त प्रणालियों (autonomous systems) के बीच रूटिंग जानकारी का आदान-प्रदान करता है

19.IPv4 सबनेटिंग

उत्तर: N = 8

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).

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

19 − 16 = 3

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

N = 2³ = 8

उत्तर

N = 8

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

20.IPv4 सबनेटिंग

उत्तर: x = 46

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

ब्लॉक आकार

2² = 4

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

नेटवर्क: ⌊47/4⌋·4 = 44

ब्रॉडकास्ट: 44 + 4 − 1 = 47

उपयोगी होस्ट: 45 … 46

उत्तर

x = 46

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