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

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

N = −678 bit
U =
2.संख्या पद्धतियाँकठिन
बिट सेट करने के लिए उन पर क्लिक करें012806403201608040201

बिट को 0100 0110 >> 1 के 8-बिट परिणाम पर सेट करें। दशमलव में परिणाम का मान R क्या है?

0100 0110>> 1
R =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
abca → c(¬b ∧ ¬c) ↔ (a → c)(¬b → a) → ((¬b ∧ ¬c) ↔ (a → c))111?110?101?100?011?010?001?000?

इसकी सत्यमान सारणी की 8 पंक्तियों में से कितनी में (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) सत्य है? इस संख्या को N कहें।

(¬b → a) → ((¬b ∧ ¬c) ↔ (a → c))
N =
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
prr ∨ pr¬p11100100

आधार-वाक्य r ∨ p; r और निष्कर्ष ¬p वाला तर्क अवैध है। सत्यमान सारणी की उस पंक्ति पर क्लिक करें जो प्रति-उदाहरण है।

r ∨ pr∴ ¬p
  1. 1p = 1, r = 1
  2. 2p = 1, r = 0
  3. 3p = 0, r = 1
  4. 4p = 0, r = 0
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABCD000111100001111011111

इस कार्नो मानचित्र में ठीक एक 1 का कोई पड़ोसी 1 नहीं है, इसलिए वह न्यूनतम SOP रूप में एक खाने का समूह (चार लिटरल का पूर्ण मिनटर्म) बना रहता है। मानचित्र के किनारों के आर-पार के पड़ोसी भी गिने जाते हैं। उस खाने पर क्लिक करें।

F = Σm(0, 3, 6, 8, 11)
  1. 1AB = 00, CD = 00
  2. 2AB = 00, CD = 01
  3. 3AB = 00, CD = 11
  4. 4AB = 00, CD = 10
  5. 5AB = 01, CD = 00
  6. 6AB = 01, CD = 01
  7. 7AB = 01, CD = 11
  8. 8AB = 01, CD = 10
  9. 9AB = 11, CD = 00
  10. 10AB = 11, CD = 01
  11. 11AB = 11, CD = 11
  12. 12AB = 11, CD = 10
  13. 13AB = 10, CD = 00
  14. 14AB = 10, CD = 01
  15. 15AB = 10, CD = 11
  16. 16AB = 10, CD = 10
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
CLKJK12345678

एक धनात्मक-कोर-ट्रिगर्ड JK फ़्लिप-फ़्लॉप Q = 0 से शुरू होता है और दिखाए गए निवेश पाता है। उस पहली क्लॉक कोर पर क्लिक करें जिस पर Q 1 से वापस 0 होता है।

Q₀ = 0JK
  1. 1क्लॉक कोर 1
  2. 2क्लॉक कोर 2
  3. 3क्लॉक कोर 3
  4. 4क्लॉक कोर 4
  5. 5क्लॉक कोर 5
  6. 6क्लॉक कोर 6
  7. 7क्लॉक कोर 7
  8. 8क्लॉक कोर 8
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

19x ≡ 6 (mod 43) हल करें। हल x दें, जहाँ 0 < x < 43।

19x ≡ 6 (mod 43)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
mc = me​ mod ncm = cd​ mod nm(n, e) = (259, 17)d = ?

एक RSA कुंजी अभाज्य p = 7 और q = 37 तथा सार्वजनिक घातांक e = 17 का उपयोग करती है। निजी घातांक d ज्ञात करें (0 < d < φ(n))।

p = 7q = 37e = 17
d =
9.एल्गोरिदम और जटिलतामध्यम

कौन-सा सॉर्टिंग एल्गोरिदम स्थिर (stable) है?

  1. Aक्विकसॉर्ट (सामान्य इन-प्लेस संस्करण)
  2. Bहीप सॉर्ट
  3. Cसेलेक्शन सॉर्ट (सामान्य संस्करण)
  4. Dमर्ज सॉर्ट
10.एल्गोरिदम और जटिलताकठिन

P और NP के बारे में कौन-सा कथन सही है?

  1. AP की हर समस्या NP में भी है
  2. BNP का अर्थ है "not polynomial"
  3. Cयह सिद्ध हो चुका है कि P ≠ NP
  4. DNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
11.डेटा संरचनाएँमध्यम

V शीर्षों और E किनारों वाले ग्राफ़ के लिए एडजेसेंसी लिस्ट कितनी मेमोरी लेती है?

  1. AO(V²)
  2. BO(V + E)
  3. CO(V × E)
  4. DO(E²)
12.डेटा संरचनाएँकठिन

एक सर्वर अपना हैश फ़ंक्शन यूनिवर्सल फ़ैमिली से यादृच्छिक रूप से क्यों चुन सकता है?

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

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

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

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

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

कॉलमों पर इंडेक्स क्यों बनाए जाते हैं?

  1. Aउन कॉलमों पर इंसर्ट और अपडेट को तेज़ करने के लिए
  2. Bउन कॉलमों पर खोज और जॉइन को तेज़ करने के लिए
  3. Cडिस्क स्थान बचाने के लिए
  4. DNULL मानों को रोकने के लिए
16.डेटाबेस और SQLकठिन

टू-फ़ेज़ लॉकिंग (2PL) क्या सुनिश्चित करता है?

  1. Aकि डेडलॉक कभी नहीं हो सकते
  2. Bकि किसी लॉक की आवश्यकता नहीं होती
  3. Cकि ट्रांज़ैक्शन कभी प्रतीक्षा नहीं करते
  4. Dकॉन्फ़्लिक्ट-सीरियलाइज़ेबल शेड्यूल
17.कंप्यूटर नेटवर्कमध्यम

लाइव वीडियो कॉल के लिए अक्सर UDP को क्यों प्राथमिकता दी जाती है?

  1. Aसभी वीडियो के लिए UDP अनिवार्य है
  2. BUDP डेटा को स्वचालित रूप से एन्क्रिप्ट करता है
  3. CUDP हर पैकेट के पहुँचने की गारंटी देता है, इसलिए तस्वीर कभी नहीं रुकती
  4. Dहर खोए हुए पैकेट को दोबारा भेजने से ज़्यादा कम देरी महत्वपूर्ण है
18.कंप्यूटर नेटवर्ककठिन

TCP fast retransmit क्या करता है?

  1. Aटाइमआउट की प्रतीक्षा किए बिना, तीन डुप्लिकेट ACK के बाद एक सेगमेंट फिर से भेजता है
  2. Bसुरक्षित रहने के लिए हर सेगमेंट दो बार भेजता है
  3. Cहर हानि के बाद विंडो को दोगुना करता है
  4. Dज्ञात होस्टों से दोबारा जुड़ते समय three-way handshake छोड़ देता है, ताकि डेटा जल्दी फिर से भेजा जा सके
19.IPv4 सबनेटिंगमध्यम
/16 → /2311111111111111111111111000000000नेटवर्क बिटहोस्ट बिट

नेटवर्क 172.30.0.0/16 को उपसर्ग /23 वाले समान सबनेट में बाँटा गया है। कितने सबनेट N हैं?

172.30.0.0/16/23
N =
20.IPv4 सबनेटिंगकठिन

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

A: 37B: 20C: 54D: 10
x =

3विलयन

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

उत्तर: U = 189

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

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

67 = 0100 0011
उलटा हुआ: 1011 1100
+1 → 1011 1101

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

1011 1101₂ = 256 − 67 = 189

उत्तर

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

उत्तर: R = 35

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

बिट-दर-बिट

1 से दाईं ओर शिफ़्ट करने पर हर बिट 1 स्थान दाईं ओर खिसकता है; दाएँ सिरे से गिरे बिट खो जाते हैं और बाईं ओर शून्य आ जाते हैं।

0100 0110 >> 1
= 0010 0011

परिणाम का मान

0010 0011₂ = 35

उत्तर

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

उत्तर: N = 3

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

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

a = 1, b = 1, c = 1: ¬b = 0, ¬b → a = 1, ¬c = 0, ¬b ∧ ¬c = 0, a → c = 1, (¬b ∧ ¬c) ↔ (a → c) = 0, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 0
a = 1, b = 1, c = 0: ¬b = 0, ¬b → a = 1, ¬c = 1, ¬b ∧ ¬c = 0, a → c = 0, (¬b ∧ ¬c) ↔ (a → c) = 1, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 1
a = 1, b = 0, c = 1: ¬b = 1, ¬b → a = 1, ¬c = 0, ¬b ∧ ¬c = 0, a → c = 1, (¬b ∧ ¬c) ↔ (a → c) = 0, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 0
a = 1, b = 0, c = 0: ¬b = 1, ¬b → a = 1, ¬c = 1, ¬b ∧ ¬c = 1, a → c = 0, (¬b ∧ ¬c) ↔ (a → c) = 0, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 0
a = 0, b = 1, c = 1: ¬b = 0, ¬b → a = 1, ¬c = 0, ¬b ∧ ¬c = 0, a → c = 1, (¬b ∧ ¬c) ↔ (a → c) = 0, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 0
a = 0, b = 1, c = 0: ¬b = 0, ¬b → a = 1, ¬c = 1, ¬b ∧ ¬c = 0, a → c = 1, (¬b ∧ ¬c) ↔ (a → c) = 0, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 0
a = 0, b = 0, c = 1: ¬b = 1, ¬b → a = 0, ¬c = 0, ¬b ∧ ¬c = 0, a → c = 1, (¬b ∧ ¬c) ↔ (a → c) = 0, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 1
a = 0, b = 0, c = 0: ¬b = 1, ¬b → a = 0, ¬c = 1, ¬b ∧ ¬c = 1, a → c = 1, (¬b ∧ ¬c) ↔ (a → c) = 1, (¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)) = 1

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

(¬b → a) → ((¬b ∧ ¬c) ↔ (a → c)): 0, 1, 0, 0, 0, 0, 1, 1
N = 3

उत्तर

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

उत्तर: p = 1, r = 1

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

आधार-वाक्य और निष्कर्ष पंक्ति-दर-पंक्ति

p = 1, r = 1: 1 1 | 0
p = 1, r = 0: 1 0 | 0
p = 0, r = 1: 1 1 | 1
p = 0, r = 0: 0 0 | 1

प्रति-उदाहरण

p = 1, r = 1

उत्तर

p = 1, r = 1

इस रूप का तर्क वैध नियम जैसा दिखता है, पर यह दिखाने के लिए कि वह वैध नहीं है, एक पंक्ति काफ़ी है।

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

उत्तर: AB = 01, CD = 10

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

हर 1 के पड़ोसी

पड़ोसी 1 वाला 1 दो या अधिक के समूह में शामिल हो सकता है।

m6: m7, m4, m2, m14 → 0
ABCD000111100001111011111

अकेला 1

m6 = A′BCD′ → AB = 01, CD = 10

उत्तर

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

उत्तर: क्लॉक कोर 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 = 0, K = 1 → Q = 0
2: J = 1, K = 1 → Q = 1
3: J = 1, K = 0 → Q = 1
4: J = 1, K = 1 → Q = 0
5: J = 0, K = 0 → Q = 0
6: J = 0, K = 0 → Q = 0
7: J = 1, K = 1 → Q = 1
8: J = 1, K = 0 → Q = 1

1 से 0 का पहला परिवर्तन

क्लॉक कोर 4

उत्तर

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

उत्तर: x = 32

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

19 का प्रतिलोम

r = 43, t = 0
r = 19, q = 2, t = 1
r = 5, q = 3, t = −2
r = 4, q = 1, t = 7
r = 1, q = 4, t = −9
19−1 ≡ 34 (mod 43)

हल करें

x ≡ 34·6 = 204 ≡ 32 (mod 43)
जाँच: 19·32 = 608 ≡ 6 (mod 43)

उत्तर

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

उत्तर: d = 89

मॉड्यूलर घात और 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 = 7·37 = 259
φ(n) = 6·36 = 216

विस्तारित यूक्लिडीय एल्गोरिथ्म

r = 216, t = 0
r = 17, q = 12, t = 1
r = 12, q = 1, t = −12
r = 5, q = 2, t = 13
r = 2, q = 2, t = −38
r = 1, q = 2, t = 89

निजी घातांक

d = 89
जाँच: 17·89 = 1513 = 7·216 + 1

उत्तर

d = 89
9.एल्गोरिदम और जटिलता

उत्तर: D · मर्ज सॉर्ट

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

मर्ज सॉर्ट स्थिर होता है जब बराबरी की स्थिति में मर्ज करते समय पहले बाएँ आधे से तत्व लिया जाए। इन-प्लेस क्विकसॉर्ट, हीप सॉर्ट और सेलेक्शन सॉर्ट आमतौर पर स्थिर नहीं होते।

उत्तर

D · मर्ज सॉर्ट
10.एल्गोरिदम और जटिलता

उत्तर: A · P की हर समस्या NP में भी है

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

P ⊆ NP: यदि आप किसी समस्या को जल्दी हल कर सकते हैं, तो आप समाधान को भी जल्दी सत्यापित कर सकते हैं। P = NP है या नहीं, यह अभी भी खुला प्रश्न है।

उत्तर

A · P की हर समस्या NP में भी है
11.डेटा संरचनाएँ

उत्तर: B · O(V + E)

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

हर शीर्ष की एक लिस्ट है और हर किनारा एक बार (डायरेक्टेड) या दो बार (अनडायरेक्टेड) आता है, जिससे O(V + E) मिलता है।

उत्तर

B · O(V + E)
12.डेटा संरचनाएँ

उत्तर: D · ताकि यह बहुत असंभाव्य हो कि कोई हमलावर ऐसी कई कुंजियाँ चुन सके जो सभी टकराएँ

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

यूनिवर्सल हैशिंग के साथ किसी भी कुंजी समुच्चय के लिए कोलिज़न की अपेक्षित संख्या कम होती है, क्योंकि हमलावर नहीं जानता कि कौन-सा फ़ंक्शन चुना गया।

उत्तर

D · ताकि यह बहुत असंभाव्य हो कि कोई हमलावर ऐसी कई कुंजियाँ चुन सके जो सभी टकराएँ
13.ग्राफ़ सिद्धांत

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

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

घात

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

विषम शीर्ष

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

उत्तर

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

उत्तर: d(D) = 20

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

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

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

A (0): B: 3, C: 13
B (3): C: 7, G: 11
C (7): E: 9
E (9): D: 22, F: 11
F (11): D: 20
G (11)
D (20)

सबसे छोटा पथ

A → B → C → E → F → D
d(D) = 20

उत्तर

d(D) = 20
15.डेटाबेस और SQL

उत्तर: B · उन कॉलमों पर खोज और जॉइन को तेज़ करने के लिए

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

इंडेक्स (अक्सर B-tree) लुकअप को तेज़ करते हैं, लेकिन स्थान लेते हैं और उन इंसर्ट व अपडेट को धीमा करते हैं जिन्हें इन्हें बनाए रखना पड़ता है।

उत्तर

B · उन कॉलमों पर खोज और जॉइन को तेज़ करने के लिए
16.डेटाबेस और SQL

उत्तर: D · कॉन्फ़्लिक्ट-सीरियलाइज़ेबल शेड्यूल

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

2PL सीरियलाइज़ेबिलिटी की गारंटी देता है, लेकिन डेडलॉक संभव रहते हैं और उनका पता लगाना या उन्हें रोकना पड़ता है।

उत्तर

D · कॉन्फ़्लिक्ट-सीरियलाइज़ेबल शेड्यूल
17.कंप्यूटर नेटवर्क

उत्तर: D · हर खोए हुए पैकेट को दोबारा भेजने से ज़्यादा कम देरी महत्वपूर्ण है

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

खोए हुए पैकेट दोबारा भेजने से देरी बढ़ेगी; रियल-टाइम मीडिया कुछ हानि सहन कर लेता है, इसलिए RTP जैसे UDP-आधारित प्रोटोकॉल उपयोग किए जाते हैं।

उत्तर

D · हर खोए हुए पैकेट को दोबारा भेजने से ज़्यादा कम देरी महत्वपूर्ण है
18.कंप्यूटर नेटवर्क

उत्तर: A · टाइमआउट की प्रतीक्षा किए बिना, तीन डुप्लिकेट ACK के बाद एक सेगमेंट फिर से भेजता है

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

तीन डुप्लिकेट ACK एक ही खोए सेगमेंट का प्रबल संकेत देते हैं, इसलिए TCP उसे तुरंत फिर से भेजता है। यह पुनःप्रेषण टाइमर की प्रतीक्षा करने से कहीं तेज़ी से पुनर्प्राप्ति करता है।

उत्तर

A · टाइमआउट की प्रतीक्षा किए बिना, तीन डुप्लिकेट ACK के बाद एक सेगमेंट फिर से भेजता है
19.IPv4 सबनेटिंग

उत्तर: N = 128

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

उधार लिए गए बिट

23 − 16 = 7

सबनेटों की संख्या

N = 27 = 128

उत्तर

N = 128

हर /23 सबनेट में 29 − 2 = 510 उपयोगी होस्ट हैं।

20.IPv4 सबनेटिंग

उत्तर: x = 128

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

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

C: 54 होस्ट → 26 = 64 (/26)
A: 37 होस्ट → 26 = 64 (/26)
B: 20 होस्ट → 25 = 32 (/27)
D: 10 होस्ट → 24 = 16 (/28)

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

C: .0 – .63
A: .64 – .127
B: .128 – .159
D: .160 – .175

उत्तर

x = 128

LAN B: 192.168.187.128/27।

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