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

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

N = −178 bit

U =

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

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

0111 1001AND0101 0101

R =

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

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

r ↔ q

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

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

निषेध को पूरी तरह भीतर ले जाने पर कौन-सा कथन ¬∀x ∀y (R(x, y) → R(y, x)) के तुल्य है? उस पर क्लिक करें।

¬∀x ∀y (R(x, y) → R(y, x))

1∀x ∀y (R(x, y) ∧ ¬R(y, x))
2∃x ∃y (¬R(x, y) ∧ ¬R(y, x))
3∃x ∃y (R(x, y) → ¬R(y, x))
4∃x ∃y (R(x, y) ∧ ¬R(y, x))

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

F = AB + A′BC′ + ABC को उसके न्यूनतम गुणनफलों के योग रूप में सरल करें। सरल किए गए व्यंजक में कितने लिटरल L हैं?

F = AB + A′BC′ + ABC

L =

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

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

F(A, B, C, D) = Σm(0, 3, 6, 9, 10, 11, 15) + d(2, 4, 5, 13)

N =

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

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

a = 57n = 71

57⁻¹ mod 71 =

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

40⁴⁸ mod 47 ज्ञात करने के लिए बार-बार वर्ग करने की विधि का उपयोग करें।

a = 40k = 48n = 47

40⁴⁸ mod 47 =

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

एमॉर्टाइज़्ड विश्लेषण (amortised analysis) क्या मापता है?

Aसबसे अच्छे इनपुट पर एल्गोरिदम की लागत
Bपूरे अनुक्रम में कहीं भी अकेले सबसे महँगे ऑपरेशन की लागत
Cऑपरेशनों के वर्स्ट-केस अनुक्रम पर प्रति ऑपरेशन औसत लागत
Dयादृच्छिक इनपुट पर अपेक्षित लागत

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

कोई समस्या NP-complete होती है यदि वह:

ANP में है और हर NP समस्या बहुपद समय में उसमें रिड्यूस होती है
Bबहुपद समय में हल की जा सकती है
Cहल करना असंभव है
DNP से बाहर है लेकिन सभी NP समस्याओं से कठिन है, जैसे हॉल्टिंग समस्या

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

कौन-सी टकराव समाधान (collision resolution) विधि टकराने वाली कुंजियों को उसी बकेट में एक सूची में संग्रहीत करती है?

Aडबल हैशिंग (Double hashing)
Bलीनियर प्रोबिंग (Linear probing)
Cसेपरेट चेनिंग (Separate chaining)
Dक्वाड्रैटिक प्रोबिंग (Quadratic probing)

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

एडजेसेंसी मैट्रिक्स के रूप में संग्रहीत V शीर्षों वाले ग्राफ़ पर ब्रेड्थ-फ़र्स्ट सर्च का रनिंग टाइम क्या है?

AO(E log V)
BO(V)
CO(V²)
DO(V + E)

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

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

|V| = 5|E| = 6

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

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

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

|V| = 6|E| = 8

W =

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

एक टेबल में केवल एक क्लस्टर्ड इंडेक्स क्यों हो सकता है?

ASQL मानक किसी टेबल पर एक से अधिक इंडेक्स की अनुमति नहीं देता
Bक्लस्टर्ड इंडेक्स केवल प्राइमरी की पर हो सकते हैं
Cपंक्तियाँ भौतिक रूप से केवल एक क्रम में संग्रहित की जा सकती हैं
Dक्लस्टर्ड इंडेक्स बहुत अधिक मेमोरी उपयोग करते हैं

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

x NULL है और y = 1 है। शर्त (x > 5 OR y = 1) का मान क्या है?

AUNKNOWN
BNULL, इसलिए पंक्ति हमेशा अस्वीकार होती है
CFALSE
DTRUE

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

जब कोई क्लाइंट DHCP से पता प्राप्त करता है, तो संदेशों का सामान्य क्रम क्या है?

AOffer, Discover, Acknowledge, Request
BDiscover, Request, Offer, Acknowledge
CDiscover, Offer, Request, Acknowledge
DRequest, Offer, Discover, Acknowledge

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

स्लाइडिंग-विंडो प्रोटोकॉल में, एक फ़्रेम खोने के बाद Go-Back-N, Selective Repeat से कैसे भिन्न है?

AGo-Back-N केवल खोया फ़्रेम फिर से भेजता है; Selective Repeat वह फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है
Bकोई भी खोए फ़्रेम कभी फिर से नहीं भेजता
CGo-Back-N खोया फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है; Selective Repeat केवल खोया फ़्रेम
Dदोनों शुरुआत से पूरी विंडो फिर से भेजते हैं

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

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

255.255.255.240

H =

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

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

A: 6B: 76C: 38D: 9

x =

3विलयन

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

उत्तर: U = 239

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

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

17 = 0001 0001

उलटा हुआ: 1110 1110

+1 → 1110 1111

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

1110 1111₂ = 256 − 17 = 239

उत्तर

U = 239

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

उत्तर: R = 81

बिट-दर-बिट

AND केवल वहीं 1 देता है जहाँ दोनों बिट 1 हों।

0111 1001

AND 0101 0101

= 0101 0001

परिणाम का मान

0101 0001₂ = 81

उत्तर

R = 81

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

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

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

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

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

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

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

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

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

उत्तर

(r → q) ∧ (q → r)

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

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

उत्तर: ∃x ∃y (R(x, y) ∧ ¬R(y, x))

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

निषेध को भीतर ले जाएँ

¬∀x ∀y (R(x, y) → R(y, x)) ≡ ∃x ∃y (R(x, y) ∧ ¬R(y, x))

उत्तर

∃x ∃y (R(x, y) ∧ ¬R(y, x))

बाकी विकल्प या तो किसी परिमाणक को अपरिवर्तित रखते हैं, या परिमाणकों का क्रम बदल देते हैं, या भीतरी सूत्र का निषेध गलत करते हैं।

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

उत्तर: L = 4

बूलीय बीजगणित: व्यंजकों को सरल करने वाले नियम हैं X + X′ = 1 और X·X′ = 0, X + X = X, अवशोषण X + X·Y = X, संयोजन नियम X·Y + X·Y′ = X, X + X′Y = X + Y और सहमति प्रमेय XY + X′Z + YZ = XY + X′Z। डी मॉर्गन के नियम (X·Y)′ को X′ + Y′ में और (X + Y)′ को X′·Y′ में बदलते हैं। कार्नो मानचित्र इन नियमों को चित्रात्मक रूप से लगाता है: दो पड़ोसी खानों का हर समूह XY + XY′ = X का एक उपयोग है।

व्यंजक के मिनटर्म

AB → m(6, 7)

A′BC′ → m(2)

ABC → m(7)

समूहित करें और पढ़ें

F = BC′ + AB

लिटरल गिनें

L = 4

उत्तर

L = 4

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

उत्तर: N = 3

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

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

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

B′C, A′D′, AD

न्यूनतम आवरण

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

N = 3

उत्तर

N = 3

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

उत्तर: 57⁻¹ mod 71 = 5

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

r = 71, t = 0

r = 57, q = 1, t = 1

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

r = 1, q = 14, t = 5

व्युत्क्रम

1 ≡ 5·57 (mod 71)

x = 5

जाँच: 57·5 = 285 = 4·71 + 1

उत्तर

57⁻¹ mod 71 = 5

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

उत्तर: 40⁴⁸ mod 47 = 2

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

द्विआधारी घातांक

48 = 110000₂ = 32 + 16

बार-बार वर्ग करना

40¹ ≡ 40 (mod 47)

40² ≡ 2 (mod 47)

40⁴ ≡ 4 (mod 47)

C · O(V²)

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

उत्तर: यूलर परिपथ

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

घात

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

विषम शीर्ष

यूलर परिपथ

उत्तर

यूलर परिपथ

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

उत्तर: W = 38

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

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

CE (1): लें

DF (4): लें

EF (7): लें

BE (9): लें

BD (14): छोड़ें, चक्र बनता है

C · Go-Back-N खोया फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है; Selective Repeat केवल खोया फ़्रेम

19.IPv4 सबनेटिंग

उत्तर: H = 14

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.240 = /28

उपयोगी होस्ट

2⁴ − 2 = 14

उत्तर

H = 14

20.IPv4 सबनेटिंग

उत्तर: x = 192

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

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

B: 76 होस्ट → 2⁷ = 128 (/25)

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

D: 9 होस्ट → 2⁴ = 16 (/28)

A: 6 होस्ट → 2³ = 8 (/29)

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

B: .0 – .127

C: .128 – .191

D: .192 – .207

A: .208 – .215

उत्तर

x = 192

LAN D: 192.168.79.192/28।

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