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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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 के पूरक में −63 संग्रहीत करें। चिह्नरहित संख्या के रूप में पढ़ने पर पैटर्न का मान U क्या है?

N = −638 bit

U =

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

बिट को 0001 1001 XOR 0110 0000 के 8-बिट परिणाम पर सेट करें। दशमलव में परिणाम का मान R क्या है?

0001 1001XOR0110 0000

R =

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

क्या ((c ∨ a) ∧ c) → ¬a पुनरुक्ति, विरोधोक्ति या आपातिक कथन है? अपना उत्तर क्लिक करें।

((c ∨ a) ∧ c) → ¬a

1पुनरुक्ति
2विरोधोक्ति
3आपातिक कथन

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

आधार-वाक्य (r ∧ q) → p; r; ¬p दिए गए हैं। इनसे कौन-सा निष्कर्ष निकलता है? उस पर क्लिक करें।

(r ∧ q) → pr¬p

1p
2¬q
3q ∧ ¬p
4q

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

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

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

N =

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

F(A, B, C, D) = Σm(1, 2, 3, 4, 11) + d(5, 9) का न्यूनतम SOP रूप ज्ञात करें, जहाँ d डोंट-केयर स्थितियों को दर्शाता है। उसमें कितने लिटरल L हैं?

F(A, B, C, D) = Σm(1, 2, 3, 4, 11) + d(5, 9)

L =

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

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

a = 47n = 71

47⁻¹ mod 71 =

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

23 अभाज्य है। 17³⁸¹³² mod 23 ज्ञात करने के लिए फर्मा के लघु प्रमेय का उपयोग करें।

p = 23k = 38132

17³⁸¹³² mod 23 =

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

रिकरेंस T(n) = T(n − 1) + O(n) का हल क्या है?

AO(2ⁿ)
BO(n²)
CO(n)
DO(n log n)

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

बॉटम-अप विधि से n अनसॉर्टेड तत्वों से बाइनरी हीप बनाने की टाइम कॉम्प्लेक्सिटी क्या है?

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

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

एक सड़क नेटवर्क में 100,000 जंक्शन हैं, हर एक लगभग 4 अन्य से जुड़ा है। कौन-सा निरूपण सबसे उपयुक्त है?

Aशीर्षों का एक सॉर्टेड ऐरे
Bएडजेसेंसी लिस्ट
Cएडजेसेंसी मैट्रिक्स
Dकिनारों का बाइनरी हीप

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

सर्कुलर बफ़र में front == rear का अर्थ ख़ाली या भरा दोनों हो सकता है। इन्हें अलग पहचानने का एक सामान्य तरीका क्या है?

Aजब भी front, rear के बराबर हो बफ़र साफ़ कर दें, ताकि स्थिति ख़ाली रहे
Bfront और rear को एक ही वेरिएबल में संग्रहीत करें
Cएक अलग तत्व-गिनती रखें, या हमेशा एक स्लॉट ख़ाली छोड़ें
Dबफ़र का आकार दो की घात रखें

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

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

|V| = 20|E| = 30

k =

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

डाइक्स्ट्रा का एल्गोरिथ्म A से चलता है। उस शीर्ष पर क्लिक करें जो चक्र 3 में निर्धारित (स्थायी) होता है; A स्वयं चक्र 1 है।

प्रारंभ: Aचक्र 3

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

कौन-सी क्वेरी हर विभाग में सबसे अधिक salary लौटाती है?

ASELECT MAX(dept), salary FROM emp GROUP BY salary
BSELECT dept, MAX(salary) FROM emp ORDER BY dept
CSELECT dept, MAX(salary) FROM emp GROUP BY dept
DSELECT dept, salary FROM emp WHERE salary = MAX(salary)

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

कोरिलेटेड सबक्वेरी (correlated subquery) वह होती है जो:

Aबाहरी क्वेरी से पहले केवल एक बार चलती है और अपना परिणाम हर पंक्ति के लिए कैश कर लेती है
Bकेवल एग्रीगेट फ़ंक्शन का उपयोग करती है
Cफ़ॉरेन की से दो टेबलों को जोड़ती है
Dबाहरी क्वेरी के कॉलमों को संदर्भित करती है और प्रत्येक बाहरी पंक्ति के लिए मूल्यांकित होती है

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

TCP थ्री-वे हैंडशेक का उद्देश्य क्या है?

Aडेटा को एन्क्रिप्ट करना
Bकिसी होस्ट को डेटा भेजे जाने से पहले उसका IP पता खोजना
Cकनेक्शन को जल्दी बंद करना
Dकनेक्शन स्थापित करना और अनुक्रम संख्याओं को सिंक्रनाइज़ करना

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

एक ही स्विच पर VLAN 10 और VLAN 20 के होस्ट संचार नहीं कर पाते। क्या आवश्यक है?

Aदोनों VLANs से जुड़ा एक हब
Bदोनों होस्टों पर एक ही MAC पता
CVLANs के बीच रूटिंग के लिए एक राउटर या परत 3 स्विच
Dहोस्टों के बीच एक लंबी केबल

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

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

192.168.10.0/2416 subnets

H =

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

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

10.20.186.174/26

x =

3विलयन

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

उत्तर: U = 193

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

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

63 = 0011 1111

उलटा हुआ: 1100 0000

+1 → 1100 0001

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

1100 0001₂ = 256 − 63 = 193

उत्तर

U = 193

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

उत्तर: R = 121

बिट-दर-बिट

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

0001 1001

XOR 0110 0000

= 0111 1001

परिणाम का मान

0111 1001₂ = 121

उत्तर

R = 121

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

उत्तर: आपातिक कथन

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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 = 1, c = 1: c ∨ a = 1, (c ∨ a) ∧ c = 1, ¬a = 0, ((c ∨ a) ∧ c) → ¬a = 0

a = 1, c = 0: c ∨ a = 1, (c ∨ a) ∧ c = 0, ¬a = 0, ((c ∨ a) ∧ c) → ¬a = 1

a = 0, c = 1: c ∨ a = 1, (c ∨ a) ∧ c = 1, ¬a = 1, ((c ∨ a) ∧ c) → ¬a = 1

a = 0, c = 0: c ∨ a = 0, (c ∨ a) ∧ c = 0, ¬a = 1, ((c ∨ a) ∧ c) → ¬a = 1

वर्गीकृत करें

((c ∨ a) ∧ c) → ¬a: 0, 1, 1, 1

4 पंक्तियों में से 3 में 1, बाकी में 0: एक आकस्मिकता (contingency)।

उत्तर

आपातिक कथन

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

उत्तर: ¬q

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

वे पंक्तियाँ जिनमें सभी आधार-वाक्य सत्य हैं

p = 0, q = 0, r = 1: p = 0, ¬q = 1, q ∧ ¬p = 0, q = 0

निष्कर्ष

¬q (संयोजन के साथ मोडस टोलेंस)

उत्तर

¬q

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

उत्तर: N = 1

मल्टीप्लेक्सर: 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 = ABC′

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

ABC = 110

N = 1

उत्तर

N = 1

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

उत्तर: L = 8

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

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

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

B′D, A′C′D, A′B′C, A′BC′

न्यूनतम आवरण

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

L = 8

उत्तर

L = 8

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

उत्तर: 47⁻¹ mod 71 = 68

प्रतिलोम और सर्वांगसमताएँ: 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·47 (mod 71) के रूप में लिखा जाता है।

r = 71, t = 0

r = 47, q = 1, t = 1

r = 24, q = 1, t = −1

r = 23, q = 1, t = 2

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

व्युत्क्रम

1 ≡ −3·47 (mod 71)

x = 68

जाँच: 47·68 = 3196 = 45·71 + 1

उत्तर

47⁻¹ mod 71 = 68

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

उत्तर: 17³⁸¹³² mod 23 = 12

मॉड्यूलर घात और 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 से डिक्रिप्ट करें।

C · एक अलग तत्व-गिनती रखें, या हमेशा एक स्लॉट ख़ाली छोड़ें

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

उत्तर: k = 11

यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; K_n में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।

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

20 − 1 = 19

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

k = 30 − 19 = 11

उत्तर

k = 11

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

उत्तर: C

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

डाइक्स्ट्रा चक्र-दर-चक्र

1. A (0): B: 3, C: 4

2. B (3): D: 18, G: 8

3. C (4): E: 13

4. G (8): E: 11

5. E (11): D: 14, F: 15

6. D (14)

VLAN परत 2 पर पृथक होते हैं, इसलिए उनके बीच का ट्रैफ़िक रूट करना पड़ता है, उदाहरण के लिए ट्रंक पर राउटर ("router on a stick") या परत 3 स्विच द्वारा।

उत्तर

C · VLANs के बीच रूटिंग के लिए एक राउटर या परत 3 स्विच

19.IPv4 सबनेटिंग

उत्तर: H = 14

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

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

2⁴ = 16 ≥ 16 → b = 4, /28

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

2⁴ − 2 = 14

उत्तर

H = 14

20.IPv4 सबनेटिंग

उत्तर: x = 128

ब्लॉक आकार

2⁶ = 64

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

नेटवर्क: ⌊174/64⌋·64 = 128

ब्रॉडकास्ट: 128 + 64 − 1 = 191

उपयोगी होस्ट: 129 … 190

उत्तर

x = 128

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