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

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

N = −428 bit

U =

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

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

0011 0111XOR1111 0000

R =

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

आप (a ∧ c) → ¬b को प्रतिधनात्मक द्वारा सिद्ध करना चाहते हैं। इसके बजाय कौन-सा निहितार्थ सिद्ध करेंगे? उस पर क्लिक करें।

(a ∧ c) → ¬b

1¬b → (a ∧ c)
2¬(a ∧ c) → ¬¬b
3¬¬b → ¬(a ∧ c)
4(a ∧ c) ∧ ¬¬b

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

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

b → aa → c

1c → b
2¬b → ¬c
3b ∧ c
4b → c

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

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

I₀ = CI₁ = CI₂ = CI₃ = 0

N =

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

एक जॉनसन (ट्विस्टेड-रिंग) काउंटर 5 D फ़्लिप-फ़्लॉप से बना है, जिसमें उलटा अंतिम निर्गत पहले निवेश में लौटाया जाता है, और वह सभी शून्य से शुरू होता है। वह कितनी भिन्न अवस्थाओं N से गुज़रता है?

n = 5

N =

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

सबसे छोटा धनात्मक पूर्णांक x ज्ञात करें जिसके लिए x ≡ 3 (mod 4) और x ≡ 9 (mod 11)।

x ≡ 3 (mod 4)x ≡ 9 (mod 11)

x =

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

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

p = 23q = 43e = 19c = 52

m =

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

V शीर्षों और E किनारों वाले ग्राफ़ पर बेलमैन–फ़ोर्ड एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?

AO(V × E)
BO(E log V)
CO(V + E)
DO(V³ × E)

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

करात्सुबा गुणन T(n) = 3T(n/2) + O(n) को संतुष्ट करता है। इसका हल क्या है?

AΘ(n³)
BΘ(n log n)
CΘ(n^{log₂ 3}), लगभग n^1.585
DΘ(n²)

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

"{[()]}" में कोष्ठक संतुलित हैं या नहीं, यह जाँचने के लिए कौन-सी डेटा संरचना उपयोग होती है?

Aस्टैक
Bबाइनरी सर्च ट्री
Cक्यू
Dहैश टेबल

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

क्रमबद्ध लिंक्ड लिस्ट की तुलना में स्किप लिस्ट का मुख्य लाभ क्या है?

Aयह कुंजियों को बिना क्रम के संग्रहीत करती है
Bयह कोई अतिरिक्त मेमोरी नहीं लेती
Cगारंटीकृत O(1) खोज, क्योंकि हर नोड बाकी हर नोड का पॉइंटर रखता है
Dआगे के पॉइंटरों के कई स्तरों का उपयोग करके अपेक्षित O(log n) खोज

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

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

|V| = 6|E| = 7

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

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

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

प्रारंभ: Ck = 3

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

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

GRANT SELECT ON employees TO alice क्या करता है?

Aemployees टेबल को alice तक कॉपी करता है
Balice को डेटाबेस का स्वामी बनाता है
Calice को employees टेबल की पंक्तियाँ अपडेट और हटाने की अनुमति देता है
Dउपयोगकर्ता alice को employees टेबल पढ़ने की अनुमति देता है

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

कौन-सा आइसोलेशन लेवल डर्टी रीड रोकता है लेकिन नॉन-रिपीटेबल रीड की अनुमति देता है?

ASerializable
BRepeatable read
CRead committed
DRead uncommitted

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

कौन-सा होस्ट 10.1.2.3 के समान /16 सबनेट में है?

A10.2.2.3
B10.1.200.5
C11.1.2.3
D10.0.2.3

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

Diffie-Hellman कुंजी विनिमय अपने आप में क्या प्राप्त करता है, और इसकी कमज़ोरी क्या है?

Aयह सार्वजनिक चैनल पर एक साझा रहस्य पर सहमति करता है, पर अकेले यह man-in-the-middle के लिए खुला है
Bयह वेबसाइटों के प्रमाणपत्रों पर हस्ताक्षर करता है, पर केवल छोटी कुंजियों के साथ काम करता है
Cयह सार्वजनिक चैनल पर बड़े डेटा को सीधे एन्क्रिप्ट करता है, पर बड़ी फ़ाइलों और वीडियो के लिए बहुत धीमा है
Dयह पासवर्ड से दोनों उपयोगकर्ताओं का प्रमाणीकरण करता है, पर इसे केंद्रीय सर्वर चाहिए

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

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

255.255.240.0

H =

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

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

10.20.240.195/29

x =

3विलयन

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

उत्तर: U = 214

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

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

42 = 0010 1010

उलटा हुआ: 1101 0101

+1 → 1101 0110

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

1101 0110₂ = 256 − 42 = 214

उत्तर

U = 214

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

उत्तर: R = 199

बिट-दर-बिट

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

0011 0111

XOR 1111 0000

= 1100 0111

परिणाम का मान

1100 0111₂ = 199

उत्तर

R = 199

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

उत्तर: ¬¬b → ¬(a ∧ c)

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

प्रतिधनात्मक

¬b → ¬a = ¬¬b → ¬(a ∧ c)

उत्तर

¬¬b → ¬(a ∧ c)

प्रतिधनात्मक मूल कथन के तुल्य है, इसलिए उसे सिद्ध करने से कथन सिद्ध हो जाता है।

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

उत्तर: b → c

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

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

a = 1, b = 1, c = 1: c → b = 1, ¬b → ¬c = 1, b ∧ c = 1, b → c = 1

a = 1, b = 0, c = 1: c → b = 0, ¬b → ¬c = 0, b ∧ c = 0, b → c = 1

a = 0, b = 0, c = 1: c → b = 0, ¬b → ¬c = 0, b ∧ c = 0, b → c = 1

a = 0, b = 0, c = 0: c → b = 1, ¬b → ¬c = 1, b ∧ c = 0, b → c = 1

निष्कर्ष

b → c (काल्पनिक न्यायवाक्य)

उत्तर

b → c

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

उत्तर: N = 3

मल्टीप्लेक्सर: 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 = A′B′C + A′BC + AB′C

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

ABC = 001, 011, 101

N = 3

उत्तर

N = 3

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

उत्तर: N = 10

फ़्लिप-फ़्लॉप और काउंटर: फ़्लिप-फ़्लॉप केवल सक्रिय क्लॉक कोर पर बदलता है। D अपना निवेश कॉपी करता है (Q⁺ = D); T तब टॉगल करता है जब T = 1; JK 00 पर स्थिर रहता है, 01 पर रीसेट करता है, 10 पर सेट करता है और 11 पर टॉगल करता है। n-बिट द्विआधारी काउंटर की 2ⁿ अवस्थाएँ होती हैं और वह 2ⁿ के मापांक में गिनता है; mod-N काउंटर 0, 1, …, N − 1 तक जाकर फिर 0 पर लौटता है, और उसे ऐसे सबसे छोटे n फ़्लिप-फ़्लॉप चाहिए जिसमें 2ⁿ ≥ N हो। रिपल काउंटर का हर चरण आवृत्ति को आधा कर देता है, इसलिए mod-N काउंटर का अंतिम निर्गत f_clk/N पर चलता है। n फ़्लिप-फ़्लॉप वाले जॉनसन काउंटर की 2n अवस्थाएँ होती हैं, रिंग काउंटर की n।

5 फ़्लिप-फ़्लॉप के लिए अनुक्रम

00000 → 10000 → 11000 → 11100 → 11110 → 11111 → 01111 → 00111 → 00011 → 00001

अवस्थाओं की संख्या

N = 10

उत्तर

N = 10

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

उत्तर: x = 31

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

पहली सर्वांगसमता

x = 3 + 4k

दूसरी सर्वांगसमता

3 + 4k ≡ 9 (mod 11) → 4k ≡ 6 (mod 11)

k ≡ 3·6 ≡ 7 (mod 11)

परिणाम

x = 3 + 4·7 = 31

x = 31

जाँच: 31 mod 4 = 3, 31 mod 11 = 9

उत्तर

x = 31

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

उत्तर: m = 831

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

d = 19⁻¹ mod 924 = 535

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

535 = 512 + 16 + 4 + 2 + 1

52¹ ≡ 52 (mod 989)

52² ≡ 726 (mod 989)

52⁴ ≡ 928 (mod 989)

52⁸ ≡ 754 (mod 989)

52¹⁶ ≡ 830 (mod 989)

52³² ≡ 556 (mod 989)

52⁶⁴ ≡ 568 (mod 989)

52¹²⁸ ≡ 210 (mod 989)

52²⁵⁶ ≡ 584 (mod 989)

52⁵¹² ≡ 840 (mod 989)

52⁵³⁵ ≡ 52·726·928·830·840 ≡ 831 (mod 989)

संदेश

m = 831

घात

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

विषम शीर्ष

यूलर परिपथ

उत्तर

यूलर परिपथ

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

उत्तर: कोर BE

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

प्रिम का एल्गोरिथ्म

1. AC (14)

2. AB (1)

3. BE (8)

4. DE (2)

Diffie-Hellman दो पक्षों को वही रहस्य निकालने देता है जिसकी गणना छिपकर सुनने वाले नहीं कर सकते। बीच में बैठा हमलावर हर पक्ष के साथ अलग विनिमय चला सकता है, जब तक कि मानों पर हस्ताक्षर न हों या उनका अन्यथा प्रमाणीकरण न हो।

उत्तर

A · यह सार्वजनिक चैनल पर एक साझा रहस्य पर सहमति करता है, पर अकेले यह man-in-the-middle के लिए खुला है

19.IPv4 सबनेटिंग

उत्तर: H = 4094

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.240.0 = /20

उपयोगी होस्ट

2¹² − 2 = 4094

उत्तर

H = 4094

20.IPv4 सबनेटिंग

उत्तर: x = 192

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

ब्लॉक आकार

2³ = 8

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

नेटवर्क: ⌊195/8⌋·8 = 192

ब्रॉडकास्ट: 192 + 8 − 1 = 199

उपयोगी होस्ट: 193 … 198

उत्तर

x = 192

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