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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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.संख्या पद्धतियाँमध्यम
दो के पूरक में स्थानीय मान0−12816403211618041211

8-बिट पैटर्न 0101 1011 दो के पूरक में एक चिह्नित पूर्णांक संग्रहीत करता है। दशमलव में इसका मान N क्या है?

0101 10118 bit
N =
2.संख्या पद्धतियाँकठिन
8 bit1 px1024 px768 pxM = ? KiB

एक असंपीड़ित छवि 1024 × 768 पिक्सेल की है, प्रति पिक्सेल 8 बिट। यह KiB में (1 KiB = 1024 बाइट) कितनी मेमोरी M लेती है?

1024 × 768 px8 bit/px1 KiB = 1024 B
M = KiB
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
pqr(p ∨ r) ↔ q(q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q))111?110?101?100?011?010?001?000?

इसकी सत्यमान सारणी की 8 पंक्तियों में से कितनी में ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) सत्य है? इस संख्या को N कहें।

¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q))
N =
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
∃x ¬A(x)∀x A(x)∀x ¬A(x)∃x A(x)

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

¬∃x A(x)
  1. 1∃x ¬A(x)
  2. 2∀x A(x)
  3. 3∀x ¬A(x)
  4. 4∃x A(x)
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
MUXC′I0​CI1​1I2​1I3​ABS1​S0​F

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

I₀ = C′I₁ = CI₂ = 1I₃ = 1
N =
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
CLKJK123456

एक धनात्मक-कोर-ट्रिगर्ड JK फ़्लिप-फ़्लॉप Q = 0 से शुरू होता है और 6 आरोही क्लॉक कोरों पर दिखाए गए निवेश पाता है। Q कितनी बार N अवस्था बदलता है?

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

यूलर का टोशेंट φ(343) ज्ञात करें, यानी 1 से 343 तक के वे पूर्णांक जो 343 से सहअभाज्य हैं।

n = 343 = 73
φ(343) =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन

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

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

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

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

log(n!) के लिए कौन-सी सीमा सही है?

  1. AΘ(n²)
  2. BΘ(n)
  3. CΘ(log n)
  4. DΘ(n log n)
11.डेटा संरचनाएँमध्यम

बाइनरी मिन-हीप में extract-min कैसे काम करता है?

  1. Aनए न्यूनतम के लिए सभी लीफ़ खोजें
  2. Bअंतिम तत्व को रूट पर ले जाकर नीचे sift करें
  3. Cरूट हटाकर सभी तत्वों को एक स्थान बाएँ खिसकाएँ
  4. Dऐरे का अंतिम तत्व हटाएँ
12.डेटा संरचनाएँकठिन

आपको O(k) मेमोरी से n संख्याओं की एक धारा (stream) से k सबसे छोटे मान रखने हैं। कौन-सा तरीका O(n log k) समय में काम करता है?

  1. Aअंतिम k मानों की FIFO क्यू
  2. Bआकार k का मैक्स-हीप, छोटा मान आने पर उसका रूट बदलते हुए
  3. Cसभी n मान रखने वाला मिन-हीप, जिससे अंत में k सबसे छोटे मान निकाले जाते हैं
  4. Dसभी n मानों का सॉर्टेड ऐरे
13.ग्राफ़ सिद्धांतमध्यम

एक संबद्ध ग्राफ़ में 15 शीर्ष और 19 कोरें हैं। स्पैनिंग ट्री बचाने के लिए कितनी कोरें k हटानी होंगी?

|V| = 15|E| = 19
k =
14.ग्राफ़ सिद्धांतकठिन
413106499811ABCDEFG

भारित ग्राफ़ में A से G तक के सबसे छोटे पथ की लंबाई d(G) डाइक्स्ट्रा के एल्गोरिथ्म से ज्ञात करें।

प्रारंभ: Aअंत: G
d(G) =
15.डेटाबेस और SQLमध्यम

टेबल a में 3 पंक्तियाँ और टेबल b में 4 पंक्तियाँ हैं। SELECT * FROM a CROSS JOIN b कितनी पंक्तियाँ लौटाता है?

  1. A4
  2. B3
  3. C12
  4. D7
16.डेटाबेस और SQLकठिन

ऑन-कॉल दो डॉक्टर दोनों जाँचते हैं कि दूसरा अभी भी ऑन-कॉल है, फिर दोनों एक ही समय पर साइन-ऑफ़ करते हैं। स्नैपशॉट आइसोलेशन यहाँ अब भी कौन-सी विसंगति होने दे सकता है?

  1. Aडर्टी रीड
  2. Bराइट स्क्यू (write skew)
  3. Cएक ट्रांज़ैक्शन के भीतर नॉन-रिपीटेबल रीड
  4. Dडर्टी राइट
17.कंप्यूटर नेटवर्कमध्यम

कौन-सा TCP फ़्लैग संकेत देता है कि प्रेषक ने डेटा भेजना समाप्त कर दिया है?

  1. AFIN
  2. BURG
  3. CPSH
  4. DSYN
18.कंप्यूटर नेटवर्ककठिन

IPv4 की तुलना में IPv6 में विखंडन (fragmentation) कैसे भिन्न है?

  1. AIPv6 ट्रांसपोर्ट परत पर TCP के भीतर विखंडन करता है
  2. Bराउटर IPv6 पैकेटों को कभी विखंडित नहीं करते; केवल स्रोत path MTU discovery का उपयोग करके कर सकता है
  3. CIPv6 576 बाइट से बड़े पैकेटों की अनुमति नहीं देता
  4. DIPv6 राउटर आगे भेजने से पहले 64 बाइट से बड़े हर पैकेट को मार्ग में विखंडित करते हैं
19.IPv4 सबनेटिंगमध्यम
/24 → /2611111111111111111111111111000000नेटवर्क बिटहोस्ट बिट

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

192.168.10.0/244 subnets
H =
20.IPv4 सबनेटिंगकठिन
तीसरा ऑक्टेट = 41012806413201618040211नेटवर्कहोस्ट

एक होस्ट का पता 172.20.41.10/18 है। इसके सबनेट के ब्रॉडकास्ट पते का तीसरा ऑक्टेट x क्या है?

172.20.41.10/18
x =

3विलयन

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

उत्तर: N = 91

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

मान जोड़ें

बाकी बिटें अपने सामान्य धनात्मक मान रखती हैं।

64 + 16 + 8 + 2 + 1 = 91

उत्तर

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

उत्तर: M = 768 KiB

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

बिट और बाइट

1024·768·8 = 6291456 bit = 786432 B

KiB में बदलें

786432/1024 = 768 KiB

उत्तर

M = 768 KiB
3.प्रस्ताविक तर्क और उपपत्तियाँ

उत्तर: N = 2

सत्यमान सारणियाँ: n अलग-अलग चरों वाले सूत्र की 2ⁿ पंक्तियाँ होती हैं, सत्यमानों के हर संयोजन के लिए एक (1 = सत्य, 0 = असत्य)। भीतर से बाहर की ओर काम करें और हर उप-सूत्र को अपना स्तंभ दें। ¬a मान उलट देता है; a ∧ b केवल तब 1 होता है जब दोनों 1 हों; a ∨ b केवल तब 0 होता है जब दोनों 0 हों; a → b केवल तब 0 होता है जब a = 1 और b = 0; a ↔ b तब 1 होता है जब दोनों पक्ष बराबर हों।

सत्यमान सारणी पंक्ति-दर-पंक्ति

p = 1, q = 1, r = 1: ¬r = 0, p ∨ ¬r = 1, q ↔ (p ∨ ¬r) = 1, p ∨ r = 1, (p ∨ r) ↔ q = 1, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 1, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 0
p = 1, q = 1, r = 0: ¬r = 1, p ∨ ¬r = 1, q ↔ (p ∨ ¬r) = 1, p ∨ r = 1, (p ∨ r) ↔ q = 1, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 1, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 0
p = 1, q = 0, r = 1: ¬r = 0, p ∨ ¬r = 1, q ↔ (p ∨ ¬r) = 0, p ∨ r = 1, (p ∨ r) ↔ q = 0, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 0, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 1
p = 1, q = 0, r = 0: ¬r = 1, p ∨ ¬r = 1, q ↔ (p ∨ ¬r) = 0, p ∨ r = 1, (p ∨ r) ↔ q = 0, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 0, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 1
p = 0, q = 1, r = 1: ¬r = 0, p ∨ ¬r = 0, q ↔ (p ∨ ¬r) = 0, p ∨ r = 1, (p ∨ r) ↔ q = 1, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 1, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 0
p = 0, q = 1, r = 0: ¬r = 1, p ∨ ¬r = 1, q ↔ (p ∨ ¬r) = 1, p ∨ r = 0, (p ∨ r) ↔ q = 0, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 1, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 0
p = 0, q = 0, r = 1: ¬r = 0, p ∨ ¬r = 0, q ↔ (p ∨ ¬r) = 1, p ∨ r = 1, (p ∨ r) ↔ q = 0, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 1, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 0
p = 0, q = 0, r = 0: ¬r = 1, p ∨ ¬r = 1, q ↔ (p ∨ ¬r) = 0, p ∨ r = 0, (p ∨ r) ↔ q = 1, (q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q) = 1, ¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)) = 0

मान 1 वाली पंक्तियाँ गिनें

¬((q ↔ (p ∨ ¬r)) ∨ ((p ∨ r) ↔ q)): 0, 0, 1, 1, 0, 0, 0, 0
N = 2

उत्तर

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

उत्तर: ∀x ¬A(x)

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

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

¬∃x A(x) ≡ ∀x ¬A(x)

उत्तर

∀x ¬A(x)

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

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

उत्तर: N = 6

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

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

ABC = 000, 011, 100, 101, 110, 111
N = 6

उत्तर

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

उत्तर: N = 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।

हर कोर के बाद Q

JK फ़्लिप-फ़्लॉप: 00 स्थिर रखता है, 01 रीसेट करता है (Q = 0), 10 सेट करता है (Q = 1), 11 टॉगल करता है।

1: J = 1, K = 1 → Q = 1
2: J = 1, K = 1 → Q = 0
3: J = 1, K = 0 → Q = 1
4: J = 1, K = 1 → Q = 0
5: J = 0, K = 1 → Q = 0
6: J = 0, K = 0 → Q = 0

परिवर्तन गिनें

0 → 1 → 0 → 1 → 0 → 0 → 0
N = 4

उत्तर

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

उत्तर: φ(343) = 294

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

अभाज्य गुणनखंड

343 = 73

टोशेंट

φ(343) = 343 − 49 = 294

उत्तर

φ(343) = 294
8.संख्या सिद्धांत और मॉड्यूलर अंकगणित

उत्तर: 1578 mod 23 = 8

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

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

78 = 10011102 = 64 + 8 + 4 + 2

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

151 ≡ 15 (mod 23)
152 ≡ 18 (mod 23)
154 ≡ 2 (mod 23)
158 ≡ 4 (mod 23)
1516 ≡ 16 (mod 23)
1532 ≡ 3 (mod 23)
1564 ≡ 9 (mod 23)

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

1578 ≡ 18·2·4·9 ≡ 8 (mod 23)

उत्तर

1578 mod 23 = 8
9.एल्गोरिदम और जटिलता

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

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

हर चरण पर समस्या आधी होती है और प्रति चरण स्थिर कार्य होता है, इसलिए लगभग log₂ n चरण होते हैं।

उत्तर

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

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

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

log(n!) ≤ n log n, और सबसे बड़े n / 2 गुणक log(n!) ≥ (n / 2) log(n / 2) देते हैं; इसीलिए तुलना-आधारित सॉर्टिंग को Ω(n log n) चाहिए।

उत्तर

D · Θ(n log n)
11.डेटा संरचनाएँ

उत्तर: B · अंतिम तत्व को रूट पर ले जाकर नीचे sift करें

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

अंतिम तत्व रूट का रिक्त स्थान भरता है और हीप गुण पूरा होने तक अपने छोटे चाइल्ड से स्वैप होता है, जिसमें O(log n) लगता है।

उत्तर

B · अंतिम तत्व को रूट पर ले जाकर नीचे sift करें
12.डेटा संरचनाएँ

उत्तर: B · आकार k का मैक्स-हीप, छोटा मान आने पर उसका रूट बदलते हुए

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

मैक्स-हीप का रूट रखा गया सबसे बड़ा मान है; कोई भी छोटा नया मान उसे O(log k) में बदल देता है, इसलिए हीप में हमेशा अब तक के k सबसे छोटे मान रहते हैं।

उत्तर

B · आकार k का मैक्स-हीप, छोटा मान आने पर उसका रूट बदलते हुए
13.ग्राफ़ सिद्धांत

उत्तर: k = 5

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

स्पैनिंग ट्री की कोरें

15 − 1 = 14

हटाई जाने वाली कोरें

k = 19 − 14 = 5

उत्तर

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

उत्तर: d(G) = 13

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

डाइक्स्ट्रा चक्र-दर-चक्र

हर पंक्ति: निर्धारित शीर्ष, उसकी अंतिम दूरी, और वे पड़ोसी जिनकी दूरी सुधरती है।

A (0): B: 4, C: 13
B (4): D: 14, G: 13
C (13): E: 19
G (13)
D (14): E: 18, F: 23
E (18)
F (23)

सबसे छोटा पथ

A → B → G
d(G) = 13

उत्तर

d(G) = 13
15.डेटाबेस और SQL

उत्तर: C · 12

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

क्रॉस जॉइन कार्तीय गुणनफल देता है, 3 × 4 = 12 पंक्तियाँ।

उत्तर

C · 12
16.डेटाबेस और SQL

उत्तर: B · राइट स्क्यू (write skew)

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

स्नैपशॉट आइसोलेशन में दोनों ट्रांज़ैक्शन पुरानी स्थिति देखते हैं और अलग-अलग पंक्तियाँ बदलते हैं, इसलिए कोई लेखन संघर्ष नहीं पकड़ा जाता; serializable आइसोलेशन इसे रोकता है।

उत्तर

B · राइट स्क्यू (write skew)
17.कंप्यूटर नेटवर्क

उत्तर: A · FIN

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

जब किसी पक्ष के पास और डेटा नहीं होता तो वह FIN भेजता है, और दूसरा पक्ष उसकी पावती देता है। SYN कनेक्शन खोलने के लिए है; RST कनेक्शन को रद्द करता है।

उत्तर

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

उत्तर: B · राउटर IPv6 पैकेटों को कभी विखंडित नहीं करते; केवल स्रोत path MTU discovery का उपयोग करके कर सकता है

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

IPv6 राउटर बहुत बड़े पैकेट को गिरा देता है और ICMPv6 Packet Too Big लौटाता है। फिर स्रोत छोटे पैकेट भेजता है या fragment extension header का उपयोग करता है।

उत्तर

B · राउटर IPv6 पैकेटों को कभी विखंडित नहीं करते; केवल स्रोत path MTU discovery का उपयोग करके कर सकता है
19.IPv4 सबनेटिंग

उत्तर: H = 62

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

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

22 = 4 ≥ 4 → b = 2, /26

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

26 − 2 = 62

उत्तर

H = 62
20.IPv4 सबनेटिंग

उत्तर: x = 63

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

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

26 = 64

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

नेटवर्क: 172.20.0.0
ब्रॉडकास्ट: 172.20.63.255

उत्तर

x = 63

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