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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 20 अभ्यास प्रश्न, पूरे हल पीछे दिए गए हैं।

नए प्रश्नकोर्स पर वापस जाएँ

प्रिंट विंडो में “PDF के रूप में सहेजें” चुनें, ताकि एक प्रति आपके डिवाइस पर रहे।

1सूत्र और विधियाँ

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

स्थानीय मान
बाइनरी 2k, ऑक्टल 8k, हेक्स 16k
दशमलव में
Σ dk·bk
दशमलव से
आधार से भाग दें, शेषफल नीचे से ऊपर पढ़ें
हेक्स ↔ बाइनरी
एक हेक्स अंक = 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

विधि

  1. अलग-अलग चरों को गिनें: सत्यमान सारणी में 2ⁿ पंक्तियाँ होती हैं, जो सभी के 1 होने से शुरू होती हैं।
  2. हर उप-सूत्र को अपना अलग स्तंभ दें और स्तंभों को भीतर से बाहर की ओर भरें।
  3. हर संयोजक का नियम लगाएँ: → केवल 1 → 0 के लिए 0 होता है, ↔ तब 1 होता है जब दोनों पक्ष समान हों।
  4. तुल्यता के लिए अंतिम स्तंभों की पंक्ति-दर-पंक्ति तुलना करें; किसी तर्क के लिए केवल उन्हीं पंक्तियों को देखें जिनमें हर आधार-वाक्य 1 हो।
  5. परिमाणक वाले कथन का निषेध करने के लिए ¬ को भीतर ले जाएँ, ∀ और ∃ आपस में बदलें, और भीतरी सूत्र का निषेध करें।

डिजिटल लॉजिक: गेट, 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′I0 + A′BI1 + AB′I2 + ABI3
फ़्लिप-फ़्लॉप
D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
काउंटर
n-बिट: 2ⁿ अवस्थाएँ; mod-N: सबसे छोटा n जिसमें 2ⁿ ≥ N; fout = fclk/N
रिपल काउंटर
fmax = 1/(n·tpd)
रिंग और जॉनसन काउंटर
n और 2n अवस्थाएँ

विधि

  1. परिपथ के लिए निवेशों से निर्गत तक एक-एक गेट करके काम करें और हर तार पर मान लिखें, या उसका व्यंजक लिखें और सत्यमान सारणी भरें।
  2. सरलीकरण के लिए 1 (और डोंट-केयर को X के रूप में) को ग्रे-कोड पंक्तियों और स्तंभों वाले कार्नो मानचित्र में रखें: 00, 01, 11, 10।
  3. 1 को 1, 2, 4, 8 या 16 खानों के जितने कम और जितने बड़े संभव हों उतने समूहों से ढकें, किनारों से लिपटते हुए; हर समूह एक गुणन पद है जो उन चरों से बना है जो स्थिर रहते हैं। POS रूप के लिए 0 को समूहित करें।
  4. फ़्लिप-फ़्लॉप और काउंटरों के लिए हर सक्रिय क्लॉक कोर पर निवेश पढ़ें, हर कोर के बाद अवस्था लिखें, और याद रखें कि 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

विधि

  1. पहले हर संख्या को n के मापांक में घटाएँ; शेषफल 0 से n − 1 के बीच होते हैं।
  2. gcd के लिए यूक्लिड एल्गोरिथ्म से बार-बार भाग दें; अंतिम अशून्य शेषफल ही gcd है।
  3. प्रतिलोम के लिए विस्तारित एल्गोरिथ्म चलाएँ और a का गुणांक रखें; ऋणात्मक हो तो n जोड़ें।
  4. a·x ≡ b को हल करने के लिए a⁻¹ से गुणा करें; दो सर्वांगसमताओं को x = r₁ + m₁k लिखकर मिलाएँ।
  5. घातों के लिए घातांक को द्विआधारी में लिखें और बार-बार वर्ग करें; RSA में d = e⁻¹ mod φ(n) होता है, जहाँ φ(n) = (p − 1)(q − 1)।

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

हैंडशेक लेमा
Σ deg(v) = 2|E|
पूर्ण ग्राफ़
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
नियमित ग्राफ़
|E| = n·k/2
वृक्ष और वन
|E| = n − 1, |E| = n − c
वृक्ष के पत्ते
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर
परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
Kn में हैमिल्टन परिपथ
(n − 1)!/2
डाइक्स्ट्रा अद्यतन
d(v) = min(d(v), d(u) + w(u, v))
लंबाई L की वॉक
(Mᴸ)ij

विधि

  1. हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
  2. यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
  3. वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
  4. डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
  5. न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।

IPv4 सबनेटिंग

प्रति सबनेट होस्ट
2(32 − prefix) − 2 (/31: 2, /32: 1)
ब्लॉक आकार
256 − (mask octet)
नेटवर्क पता
IP AND मास्क
ब्रॉडकास्ट पता
IP OR (NOT mask): सभी होस्ट बिट 1
n उधार लिए बिट से सबनेट
2n

2अभ्यास प्रश्न

1.संख्या पद्धतियाँमध्यम
8-बिट दो का पूरक0−12806403201608040201

बिट इस तरह सेट करें कि वे 8-बिट 2 के पूरक में −114 संग्रहीत करें। चिह्नरहित संख्या के रूप में पढ़ने पर पैटर्न का मान U क्या है?

N = −1148 bit
U =
2.संख्या पद्धतियाँकठिन
24 बिट, चिह्नरहित, N = ?????????????????????????

24 बिटों में समाने वाला सबसे बड़ा अचिह्नित पूर्णांक N क्या है?

24 bit
N =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
¬¬c ∧ a¬c ∧ ¬a¬¬c → ¬a¬¬c ∧ ¬a

आप ¬c → a को विरोधाभास द्वारा सिद्ध करना चाहते हैं। शुरू में कौन-सा कथन मानेंगे? उस पर क्लिक करें।

¬c → a
  1. 1¬¬c ∧ a
  2. 2¬c ∧ ¬a
  3. 3¬¬c → ¬a
  4. 4¬¬c ∧ ¬a
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
p ∧ qqp¬q

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

p ∨ q¬p
  1. 1p ∧ q
  2. 2q
  3. 3p
  4. 4¬q
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABC000111100101324576

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

F = BC′ + AB + A′BC′
L =
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
TQ0​Q0​TQ1​Q1​TQ2​Q2​CLKMOD-5

एक तुल्यकालिक mod-5 काउंटर 0, 1, …, 4 गिनता है और फिर 0 पर लौटता है। यह 4 से शुरू होता है। 15 क्लॉक पल्स के बाद वह कौन-सी गिनती Q (दशमलव में) दिखाएगा?

Q0 = 415N = 5
Q =
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

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

a = 13n = 37
13−1 mod 37 =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन

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

a = 15k = 107n = 53
15107 mod 53 =
9.एल्गोरिदम और जटिलतामध्यम

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

  1. AO(log n)
  2. BO(n²)
  3. CO(n)
  4. DO(n log n)
10.एल्गोरिदम और जटिलताकठिन

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

  1. AO(n² 2ⁿ)
  2. BO(2n²)
  3. CO(n³)
  4. DO(n!)
11.डेटा संरचनाएँमध्यम

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

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

ऐरे के हर तत्व के लिए आप उसके दाईं ओर का अगला बड़ा तत्व कुल O(n) समय में चाहते हैं। कौन-सी संरचना मदद करती है?

  1. Aसभी तत्वों की हैश टेबल
  2. Bतत्वों के हर युग्म को रखने वाली क्यू
  3. Cएक स्टैक जो उत्तर की प्रतीक्षा कर रहे तत्वों को रखता है
  4. Dहर तत्व के लिए फिर से बनाया गया बाइनरी सर्च ट्री
13.ग्राफ़ सिद्धांतमध्यम
ABCDEयूलर परिपथयूलर पथ, परिपथ नहींदोनों में से कुछ नहीं

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

|V| = 5|E| = 5
  1. 1यूलर परिपथ
  2. 2यूलर पथ, परिपथ नहीं
  3. 3दोनों में से कुछ नहीं
14.ग्राफ़ सिद्धांतकठिन
ABCDE

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

M = संलग्नता आव्यूहL = 2
N =
15.डेटाबेस और SQLमध्यम

डेटाबेस ट्रिगर क्या है?

  1. Aऐसी क्वेरी जिसे उपयोगकर्ता हाथ से चलाता है
  2. Bडेटाबेस का निर्धारित बैकअप
  3. Cखोज तेज़ करने वाला एक प्रकार का इंडेक्स
  4. Dऐसा कोड जो किसी टेबल पर INSERT, UPDATE या DELETE जैसी निर्दिष्ट घटना होने पर स्वतः चलता है
16.डेटाबेस और SQLकठिन

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

  1. ARead committed
  2. BRead uncommitted
  3. CRepeatable read
  4. DSerializable
17.कंप्यूटर नेटवर्कमध्यम

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

  1. A/24
  2. B/16
  3. C/32
  4. D/8
18.कंप्यूटर नेटवर्ककठिन

DNS क्वेरी सामान्यतः UDP का उपयोग करती हैं। DNS आमतौर पर इसके बजाय TCP का उपयोग कब करता है?

  1. Aकेवल IP पतों के रिवर्स लुकअप के लिए
  2. Bवेब ब्राउज़र से भेजी गई हर क्वेरी के लिए
  3. CUDP के लिए बहुत बड़ी प्रतिक्रियाओं और ज़ोन ट्रांसफ़र के लिए
  4. Dकेवल जब डोमेन नाम दस अक्षरों से लंबा हो
19.IPv4 सबनेटिंगमध्यम
/?11111111111111111111110000000000नेटवर्क बिटहोस्ट बिट

एक विभाग को एक ही सबनेट में 672 होस्ट पते चाहिए। पर्याप्त होने वाली सबसे लंबी उपसर्ग लंबाई p (सबसे छोटा सबनेट) क्या है?

672 hosts
p =
20.IPv4 सबनेटिंगकठिन
अंतिम ऑक्टेट = 177112806413211608040211नेटवर्कहोस्ट

एक होस्ट का पता 10.20.220.177/27 है। उसके सबनेट के अंतिम उपयोगी होस्ट पते का चौथा ऑक्टेट x क्या है?

10.20.220.177/27
x =

3विलयन

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

उत्तर: U = 142

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

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

114 = 0111 0010
उलटा हुआ: 1000 1101
+1 → 1000 1110

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

1000 1110₂ = 256 − 114 = 142

उत्तर

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

उत्तर: N = 1.678 × 10⁷

स्थानीय मान संख्या पद्धतियाँ: हर अंक का मान उसके मान गुणा आधार की एक घात होता है। द्विआधारी में स्थान 1, 2, 4, 8, 16, … के होते हैं; षोडशआधारी में 1, 16, 256, …, जहाँ A–F का अर्थ 10–15 है। 8-बिट दो के पूरक में सबसे बाईं बिट +128 के बजाय −128 की होती है; ऋणात्मक संख्याएँ इसी तरह संग्रहीत होती हैं।

सबसे बड़ा मान

224 − 1 = 16777215

उत्तर

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

उत्तर: ¬c ∧ ¬a

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

निहितार्थ का निषेध

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

उत्तर

¬c ∧ ¬a

यदि मान्यता विरोधाभास की ओर ले जाए, तो निहितार्थ सत्य होना चाहिए।

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

उत्तर: q

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

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

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

निष्कर्ष

q (वियोजक न्यायवाक्य)

उत्तर

q
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 का एक उपयोग है।

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

BC′ → m(2, 6)
AB → m(6, 7)
A′BC′ → m(2)
ABC00011110010001031204051716

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

F = BC′ + AB

लिटरल गिनें

L = 4

उत्तर

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

उत्तर: Q = 4

फ़्लिप-फ़्लॉप और काउंटर: फ़्लिप-फ़्लॉप केवल सक्रिय क्लॉक कोर पर बदलता है। 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 काउंटर का अंतिम निर्गत fclk/N पर चलता है। n फ़्लिप-फ़्लॉप वाले जॉनसन काउंटर की 2n अवस्थाएँ होती हैं, रिंग काउंटर की n।

पूरे चक्र

हर 5 पल्स काउंटर को उसी अवस्था में वापस ले आते हैं।

15 = 3·5 + 0

शेष पल्स के बाद गिनती

Q = (4 + 0) mod 5 = 4
Q = 100₂

उत्तर

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

उत्तर: 13−1 mod 37 = 20

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

r = 37, t = 0
r = 13, q = 2, t = 1
r = 11, q = 1, t = −2
r = 2, q = 5, t = 3
r = 1, q = 2, t = −17

व्युत्क्रम

1 ≡ −17·13 (mod 37)
x = 20
जाँच: 13·20 = 260 = 7·37 + 1

उत्तर

13−1 mod 37 = 20
8.संख्या सिद्धांत और मॉड्यूलर अंकगणित

उत्तर: 15107 mod 53 = 36

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

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

107 = 11010112 = 64 + 32 + 8 + 2 + 1

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

151 ≡ 15 (mod 53)
152 ≡ 13 (mod 53)
154 ≡ 10 (mod 53)
158 ≡ 47 (mod 53)
1516 ≡ 36 (mod 53)
1532 ≡ 24 (mod 53)
1564 ≡ 46 (mod 53)

आवश्यक घातों को गुणा करें

15107 ≡ 15·13·47·24·46 ≡ 36 (mod 53)

उत्तर

15107 mod 53 = 36
9.एल्गोरिदम और जटिलता

उत्तर: D · O(n log n)

यह उत्तर क्यों है

मास्टर प्रमेय (master theorem) से (a = 2, b = 2, f(n) = n), T(n) = Θ(n log n)।

उत्तर

D · O(n log n)
10.एल्गोरिदम और जटिलता

उत्तर: A · O(n² 2ⁿ)

यह उत्तर क्यों है

लगभग n 2ⁿ अवस्थाएँ हैं, हर एक की गणना O(n) में होती है; यह घातांकी है पर सभी (n − 1)! टूर आज़माने से कहीं तेज़ है।

उत्तर

A · O(n² 2ⁿ)
11.डेटा संरचनाएँ

उत्तर: D · सेपरेट चेनिंग (Separate chaining)

यह उत्तर क्यों है

चेनिंग प्रत्येक बकेट के लिए एक लिंक्ड लिस्ट (या अन्य संरचना) रखती है; ओपन एड्रेसिंग टेबल में ही कोई अन्य खाली स्थान खोजती है।

उत्तर

D · सेपरेट चेनिंग (Separate chaining)
12.डेटा संरचनाएँ

उत्तर: C · एक स्टैक जो उत्तर की प्रतीक्षा कर रहे तत्वों को रखता है

यह उत्तर क्यों है

बाएँ से दाएँ स्कैन करते हुए, वर्तमान से छोटे हर स्टैक्ड तत्व को pop करें (वर्तमान तत्व उनका उत्तर है), फिर उसे push करें; हर तत्व अधिकतम दो बार खिसकता है।

उत्तर

C · एक स्टैक जो उत्तर की प्रतीक्षा कर रहे तत्वों को रखता है
13.ग्राफ़ सिद्धांत

उत्तर: दोनों में से कुछ नहीं

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

घात

deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 1, deg(E) = 1

विषम शीर्ष

B, C, D, E → 4
दोनों में से कुछ नहीं

उत्तर

दोनों में से कुछ नहीं
14.ग्राफ़ सिद्धांत

उत्तर: N = 1

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। Kn में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

संलग्नता आव्यूह

A: 0 1 0 0 0
B: 1 0 1 1 1
C: 0 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0

उभयनिष्ठ पड़ोसी

(M²)AA = 0·0 + 1·1 + 0·0 + 0·0 + 0·0 = 1

उत्तर

N = 1
15.डेटाबेस और SQL

उत्तर: D · ऐसा कोड जो किसी टेबल पर INSERT, UPDATE या DELETE जैसी निर्दिष्ट घटना होने पर स्वतः चलता है

यह उत्तर क्यों है

ट्रिगर डेटा परिवर्तन से पहले या बाद में स्वतः निष्पादित होते हैं, उदाहरण के लिए ऑडिट लॉग लिखने या जटिल नियम लागू करने के लिए।

उत्तर

D · ऐसा कोड जो किसी टेबल पर INSERT, UPDATE या DELETE जैसी निर्दिष्ट घटना होने पर स्वतः चलता है
16.डेटाबेस और SQL

उत्तर: A · Read committed

यह उत्तर क्यों है

Read committed बिना कमिट किए बदलावों को छिपाता है; Repeatable read नॉन-रिपीटेबल रीड भी रोकता है; Serializable फ़ैंटम भी रोकता है।

उत्तर

A · Read committed
17.कंप्यूटर नेटवर्क

उत्तर: A · /24

यह उत्तर क्यों है

255 के तीन ऑक्टेट 24 एक-बिट होते हैं, इसलिए 255.255.255.0 = /24।

उत्तर

A · /24
18.कंप्यूटर नेटवर्क

उत्तर: C · UDP के लिए बहुत बड़ी प्रतिक्रियाओं और ज़ोन ट्रांसफ़र के लिए

यह उत्तर क्यों है

यदि UDP प्रतिक्रिया कट जाती है, तो resolver TCP पर पुनः प्रयास करता है। नेम सर्वरों के बीच ज़ोन ट्रांसफ़र भी TCP का उपयोग करते हैं क्योंकि उनमें बहुत डेटा होता है।

उत्तर

C · UDP के लिए बहुत बड़ी प्रतिक्रियाओं और ज़ोन ट्रांसफ़र के लिए
19.IPv4 सबनेटिंग

उत्तर: p = 22

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

आवश्यक होस्ट बिट

29 − 2 = 510 < 672
210 − 2 = 1022 ≥ 672 → h = 10

उपसर्ग लंबाई

p = 32 − 10 = 22

उत्तर

p = /22
20.IPv4 सबनेटिंग

उत्तर: x = 190

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

ब्लॉक आकार

25 = 32

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

नेटवर्क: ⌊177/32⌋·32 = 160
ब्रॉडकास्ट: 160 + 32 − 1 = 191
उपयोगी होस्ट: 161 … 190

उत्तर

x = 190

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