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

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

N = −158 bit

U =

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

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

0010 0101OR0111 0111

R =

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

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

(b ∧ (b → a)) → a

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

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

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

r → q¬q

1¬r ∧ q
2r
3q
4¬r

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

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

F(A, B, C, D) = Σm(0, 2, 3, 4, 9, 11, 13, 14)

N =

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

F(A, B, C, D) = Σm(4, 8, 11, 14) + d(2, 5, 7) का न्यूनतम SOP रूप ज्ञात करें, जहाँ d डोंट-केयर स्थितियों को दर्शाता है। उसमें कितने गुणन पद N हैं?

F(A, B, C, D) = Σm(4, 8, 11, 14) + d(2, 5, 7)

N =

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

4x ≡ 1 (mod 11) हल करें। हल x दें, जहाँ 0 < x < 11।

4x ≡ 1 (mod 11)

x =

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

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

p = 31q = 41e = 23c = 243

m =

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

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

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

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

क्या 2²ⁿ, O(2ⁿ) में है?

Aहाँ, क्योंकि दोनों घातांकी हैं
Bनहीं, क्योंकि 2²ⁿ, 2ⁿ से धीमा बढ़ता है
Cनहीं, क्योंकि 2²ⁿ = 4ⁿ और 4ⁿ / 2ⁿ = 2ⁿ असीमित रूप से बढ़ता है
Dहाँ, क्योंकि Big O में घातांक के स्थिर गुणक हमेशा अनदेखे किए जाते हैं

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

बाइनरी सर्च ट्री का in-order ट्रैवर्सल कुंजियों को किस क्रम में देखता है?

Aस्तर क्रम (level order) में
Bआरोही क्रमबद्ध क्रम में
Cहमेशा अवरोही क्रम में
Dइंसर्शन के क्रम में

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

बाइनरी सर्च ट्री से दो चाइल्ड वाले नोड को हटाना आमतौर पर कैसे किया जाता है?

Aउसे रूट से अदला-बदली करके
Bपूरे सबट्री को हटाकर
Cउसके नीचे के सबट्री को शुरू से दोबारा बनाकर और उसमें मौजूद हर कुंजी को फिर से डालकर
Dउसे उसके in-order उत्तराधिकारी (या पूर्ववर्ती) से बदलकर और फिर उस नोड को हटाकर

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

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

4 × deg 5

L =

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

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

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

N =

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

प्रथम नॉर्मल फ़ॉर्म (1NF) की आवश्यकता क्या है?

Aकोई फ़ॉरेन की न हो
Bप्रत्येक कॉलम में परमाणु (atomic) मान हों और कोई दोहराए जाने वाले समूह न हों
Cप्रत्येक नॉन-की कॉलम पूरी की पर निर्भर हो और की के अलावा किसी पर नहीं
Dहर टेबल में ठीक एक कॉलम हो

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

customers LEFT JOIN orders के बाद प्रति ग्राहक ऑर्डर गिनने के लिए COUNT(*) के बजाय COUNT(o.id) का उपयोग क्यों करें?

ACOUNT(*) बिना ऑर्डर वाले ग्राहकों के लिए NULL से भरी पंक्ति को 1 गिनता है
BCOUNT(o.id) केवल विशिष्ट ग्राहक गिनता है
CCOUNT(*) NULL मानों वाली पंक्तियों को अनदेखा करता है
Dजॉइन के बाद COUNT(*) की अनुमति नहीं है

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

TLS, HTTPS के लिए कौन-से सुरक्षा गुण प्रदान करता है?

Aदेखी जा रही साइट पर सभी मैलवेयर और फ़िशिंग से सुरक्षा
Bकेवल तेज़ लोडिंग
Cउपयोगकर्ता की गुमनामी
Dगोपनीयता, अखंडता और सर्वर प्रमाणीकरण

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

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

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

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

एक सबनेट मास्क 255.255.255.224 का उपयोग करता है। इसमें कितने उपयोगी होस्ट पते H हैं?

255.255.255.224

H =

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

नेटवर्क 192.168.177.0/24 को इन LAN के लिए VLSM से बाँटा जाता है: A: 84 होस्ट, B: 11 होस्ट, C: 62 होस्ट, D: 30 होस्ट। सबनेट .0 से ऊपर की ओर आवंटित किए जाते हैं, सबसे अधिक होस्ट वाला LAN पहले, हर एक को सबसे छोटा फ़िट होने वाला सबनेट। LAN D के नेटवर्क पते का चौथा ऑक्टेट x क्या है?

A: 84B: 11C: 62D: 30

x =

3विलयन

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

उत्तर: U = 241

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

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

15 = 0000 1111

उलटा हुआ: 1111 0000

+1 → 1111 0001

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

1111 0001₂ = 256 − 15 = 241

उत्तर

U = 241

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

उत्तर: R = 119

बिट-दर-बिट

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

0010 0101

OR 0111 0111

= 0111 0111

परिणाम का मान

0111 0111₂ = 119

उत्तर

R = 119

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, b = 1: b → a = 1, b ∧ (b → a) = 1, (b ∧ (b → a)) → a = 1

a = 1, b = 0: b → a = 1, b ∧ (b → a) = 0, (b ∧ (b → a)) → a = 1

a = 0, b = 1: b → a = 0, b ∧ (b → a) = 0, (b ∧ (b → a)) → a = 1

a = 0, b = 0: b → a = 1, b ∧ (b → a) = 0, (b ∧ (b → a)) → a = 1

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

(b ∧ (b → a)) → a: 1, 1, 1, 1

हर पंक्ति में 1: पुनरुक्ति।

उत्तर

पुनरुक्ति

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

उत्तर: ¬r

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

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

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

निष्कर्ष

¬r (मोडस टोलेंस)

उत्तर

¬r

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

उत्तर: N = 5

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

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

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

B′CD

A′C′D′

AC′D

A′B′D′

ABCD′

न्यूनतम SOP रूप

F = B′CD + A′C′D′ + AC′D + A′B′D′ + ABCD′

N = 5

उत्तर

N = 5

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

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

उत्तर: N = 4

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

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

A′BC′, AB′C′D′, AB′CD, ABCD′

न्यूनतम आवरण

F = A′BC′ + AB′C′D′ + AB′CD + ABCD′

N = 4

उत्तर

N = 4

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

उत्तर: x = 3

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

4 का प्रतिलोम

r = 11, t = 0

r = 4, q = 2, t = 1

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

r = 1, q = 3, t = 3

4⁻¹ ≡ 3 (mod 11)

हल करें

x ≡ 3·1 = 3 ≡ 3 (mod 11)

जाँच: 4·3 = 12 ≡ 1 (mod 11)

उत्तर

x = 3

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

उत्तर: m = 68

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

d = 23⁻¹ mod 1200 = 887

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

887 = 512 + 256 + 64 + 32 + 16 + 4 + 2 + 1

243¹ ≡ 243 (mod 1271)

243² ≡ 583 (mod 1271)

243⁴ ≡ 532 (mod 1271)

243⁸ ≡ 862 (mod 1271)

243¹⁶ ≡ 780 (mod 1271)

243³² ≡ 862 (mod 1271)

243⁶⁴ ≡ 780 (mod 1271)

243¹²⁸ ≡ 862 (mod 1271)

243²⁵⁶ ≡ 780 (mod 1271)

243⁵¹² ≡ 862 (mod 1271)

243⁸⁸⁷ ≡ 243·583·532·780·862·780·780·862 ≡ 68 (mod 1271)

संदेश

m = 68

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

L + 20 = 2(L + 4) − 2

L = 14

उत्तर

L = 14

शॉर्टकट: 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 0 0 0 0

B: 1 0 1 0 1 0

C: 0 1 0 0 1 0

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

19.IPv4 सबनेटिंग

उत्तर: H = 30

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

उपसर्ग लंबाई

255.255.255.224 = /27

उपयोगी होस्ट

2⁵ − 2 = 30

उत्तर

H = 30

20.IPv4 सबनेटिंग

उत्तर: x = 192

VLSM: हर LAN को सबसे छोटा सबनेट मिलता है जिसके लिए 2ʰ − 2 ≥ उसकी होस्ट संख्या, अर्थात उपसर्ग 32 − h। सबसे बड़े सबनेट पहले आवंटित करने से हर ब्लॉक अपने आकार के गुणज पर संरेखित रहता है, इसलिए नेटवर्क पते ब्लॉक आकार जोड़ते जाने से मिलते हैं।

प्रति LAN ब्लॉक आकार

A: 84 होस्ट → 2⁷ = 128 (/25)

C: 62 होस्ट → 2⁶ = 64 (/26)

D: 30 होस्ट → 2⁵ = 32 (/27)

B: 11 होस्ट → 2⁴ = 16 (/28)

आवंटन, सबसे बड़ा पहले

A: .0 – .127

C: .128 – .191

D: .192 – .223

B: .224 – .239

उत्तर

x = 192

LAN D: 192.168.177.192/27।

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