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

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

N = −1038 bit

U =

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

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

1110 1111XOR0010 0110

R =

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

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

(c → a) → (a → c)

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

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

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

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

N =

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

F(A, B, C, D) = Σm(2, 5, 13, 15) का न्यूनतम योगों का गुणनफल (POS) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कितने योग पद (गुणक) N हैं?

F(A, B, C, D) = Σm(2, 5, 13, 15)

N =

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

F(A, B, C, D) = Σm(1, 6, 9, 12, 14, 15) + d(3, 13) के लिए, जहाँ d डोंट-केयर स्थितियों को दर्शाता है, अनिवार्य प्रमुख प्रभाव्यों (एसेंशियल प्राइम इम्प्लिकेंट) की संख्या N ज्ञात करें।

F(A, B, C, D) = Σm(1, 6, 9, 12, 14, 15) + d(3, 13)

N =

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

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

a = 33n = 53

33⁻¹ mod 53 =

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

एक RSA कुंजी में p = 13, q = 29 और e = 13 हैं। सिफरटेक्स्ट c = 178 को डिक्रिप्ट करें: संदेश m ज्ञात करें।

p = 13q = 29e = 13c = 178

m =

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

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

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

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

हेल्ड–कार्प डायनेमिक प्रोग्रामिंग एल्गोरिदम ट्रैवलिंग सेल्समैन समस्या को ठीक-ठीक हल करता है। n शहरों के लिए इसका रनिंग टाइम क्या है?

AO(n² 2ⁿ)
BO(2^n²)
CO(n³)
DO(n!)

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

बाइनरी सर्च ट्री में न्यूनतम कुंजी कैसे खोजते हैं?

Aकेवल रूट को देखें
Bहर लीफ़ पर जाकर उनकी तुलना करें
Cरूट से दाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई दायाँ चाइल्ड न रहे
Dरूट से बाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई बायाँ चाइल्ड न रहे

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

डेटाबेस इंडेक्स के लिए प्रायः साधारण B-ट्री के बजाय B+ ट्री का उपयोग क्यों करते हैं?

AB+ ट्री डेटा केवल रूट में संग्रहीत करते हैं
Bसभी रिकॉर्ड जुड़े हुए लीफ़ में होते हैं, जिससे रेंज स्कैन कुशल होते हैं
CB+ ट्री को संतुलित होने की आवश्यकता नहीं है
DB+ ट्री आंतरिक नोडों के रूप में बाइनरी नोड उपयोग करते हैं, जिससे डिस्क रीड घटते हैं

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

क्या संबद्ध ग्राफ़ में यूलर परिपथ है, परिपथ न होने वाला यूलर पथ है, या दोनों में से कुछ नहीं? अपना उत्तर क्लिक करें।

|V| = 5|E| = 6

1यूलर परिपथ
2यूलर पथ, परिपथ नहीं
3दोनों में से कुछ नहीं

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

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

|V| = 5|E| = 7

W =

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

छात्र कई कोर्स ले सकते हैं और कोर्स में कई छात्र होते हैं। इसे टेबलों में कैसे मॉडल किया जाता है?

Astudents और courses को एक टेबल में मिलाकर
Bstudents टेबल में course_id फ़ॉरेन की कॉलम से, जो courses को इंगित करता है
Cएक कॉलम में संग्रहित course id की सूची से
Dstudents और courses दोनों की फ़ॉरेन की रखने वाली एक जंक्शन टेबल से

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

SELECT name, dept, AVG(salary) OVER (PARTITION BY dept) FROM emp क्या लौटाता है?

Aएक त्रुटि क्योंकि name, GROUP BY में नहीं है
Bकेवल वे कर्मचारी जो अपने विभाग के औसत से अधिक कमाते हैं
Cहर कर्मचारी पंक्ति, उसके विभाग के औसत salary के साथ
Dप्रति विभाग एक पंक्ति, उसके औसत salary के साथ

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

255.255.255.0 का सबनेट मास्क CIDR संकेतन में किसके बराबर है?

A/24
B/16
C/32
D/8

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

अतिरिक्त (redundant) स्विच लिंक वाले नेटवर्क में ब्रॉडकास्ट लूप को कौन-सी प्रणाली रोकती है?

ASpanning Tree Protocol
BDHCP snooping
CNAT
DARP caching

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

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

192.168.10.0/248 subnets

H =

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

एक होस्ट का पता 172.20.101.109/21 है। इसके नेटवर्क पते का तीसरा ऑक्टेट x क्या है?

172.20.101.109/21

x =

3विलयन

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

उत्तर: U = 153

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

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

103 = 0110 0111

उलटा हुआ: 1001 1000

+1 → 1001 1001

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

1001 1001₂ = 256 − 103 = 153

उत्तर

U = 153

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

उत्तर: R = 201

बिट-दर-बिट

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

1110 1111

XOR 0010 0110

= 1100 1001

परिणाम का मान

1100 1001₂ = 201

उत्तर

R = 201

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, a → c = 1, (c → a) → (a → c) = 1

a = 1, c = 0: c → a = 1, a → c = 0, (c → a) → (a → c) = 0

a = 0, c = 1: c → a = 0, a → c = 1, (c → a) → (a → c) = 1

a = 0, c = 0: c → a = 1, a → c = 1, (c → a) → (a → c) = 1

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

(c → a) → (a → c): 1, 0, 1, 1

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

उत्तर

आपातिक कथन

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 होता है जब दोनों पक्ष बराबर हों।

स्तंभ

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

a पर बाँटें

a = 1: 6

a = 0: 4

N = 6 + 4 = 10

उत्तर

N = 10

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

उत्तर: N = 4

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

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

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

(B′ + D)

(B + C)

(A + C′ + D′)

(A′ + B)

न्यूनतम POS रूप

F = (B′ + D)(B + C)(A + C′ + D′)(A′ + B)

N = 4

उत्तर

N = 4

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

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

उत्तर: N = 2

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

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

B′C′D, BCD′, AC′D, AB, A′B′D

अनिवार्य प्रमुख प्रभाव्य

BCD′, AB

N = 2

उत्तर

N = 2

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

उत्तर: 33⁻¹ mod 53 = 45

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

r = 53, t = 0

r = 33, q = 1, t = 1

r = 20, q = 1, t = −1

r = 13, q = 1, t = 2

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

r = 6, q = 1, t = 5

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

व्युत्क्रम

1 ≡ −8·33 (mod 53)

x = 45

जाँच: 33·45 = 1485 = 28·53 + 1

उत्तर

33⁻¹ mod 53 = 45

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

उत्तर: m = 22

मॉड्यूलर घात और 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 = 377, φ(n) = 336

d = 13⁻¹ mod 336 = 181

बार-बार वर्ग करके डिक्रिप्ट करें

181 = 128 + 32 + 16 + 4 + 1

178¹ ≡ 178 (mod 377)

178² ≡ 16 (mod 377)

178⁴ ≡ 256 (mod 377)

178⁸ ≡ 315 (mod 377)

178¹⁶ ≡ 74 (mod 377)

178³² ≡ 198 (mod 377)

178⁶⁴ ≡ 373 (mod 377)

178¹²⁸ ≡ 16 (mod 377)

178¹⁸¹ ≡ 178·256·74·198·16 ≡ 22 (mod 377)

संदेश

m = 22

घात

deg(A) = 2, deg(B) = 4, deg(C) = 2, deg(D) = 2, deg(E) = 2

विषम शीर्ष

यूलर परिपथ

उत्तर

यूलर परिपथ

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

उत्तर: W = 35

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

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

AB (3): लें

DE (6): लें

A · Spanning Tree Protocol

19.IPv4 सबनेटिंग

उत्तर: H = 30

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

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

2³ = 8 ≥ 8 → b = 3, /27

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

2⁵ − 2 = 30

उत्तर

H = 30

20.IPv4 सबनेटिंग

उत्तर: x = 96

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

तीसरे ऑक्टेट में ब्लॉक आकार

2³ = 8

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

नेटवर्क: 172.20.96.0

ब्रॉडकास्ट: 172.20.103.255

उत्तर

x = 96

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