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

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

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

16-बिट दो के पूरक में संग्रहीत की जा सकने वाली सबसे छोटी (सबसे ऋणात्मक) पूर्णांक N क्या है?

16 bit
N =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
pqrr → ¬p¬(r → ¬p)(p ∧ (r ↔ ¬q)) ∨ ¬(r → ¬p)111?110?101?100?011?010?001?000?

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

(p ∧ (r ↔ ¬q)) ∨ ¬(r → ¬p)
N =
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
aba → b¬a¬b11100100

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

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

F(A, B, C) = Σm(0, 3, 5, 7) का न्यूनतम गुणनफलों का योग (SOP) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कुल कितने लिटरल L हैं (प्राइम वाला चर एक लिटरल गिना जाता है)?

F(A, B, C) = Σm(0, 3, 5, 7)
L =
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
CLKD12345678

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

Q₀ = 0D
  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.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

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

x ≡ 6 (mod 8)x ≡ 11 (mod 13)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
mc = me​ mod n418m = cd​ mod n?(n, e) = (1147, 7)d

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

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

1, 3 और 4 के सिक्कों और 6 की राशि के साथ, ग्रीडी "पहले सबसे बड़ा सिक्का" विधि इष्टतम की तुलना में कितने सिक्के उपयोग करती है?

  1. Aग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 3 है
  2. Bग्रीडी 2 सिक्के उपयोग करती है; इष्टतम 2 है
  3. Cग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है
  4. Dग्रीडी 4 सिक्के उपयोग करती है; इष्टतम 3 है
10.एल्गोरिदम और जटिलताकठिन

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

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

यदि कुंजियाँ क्रमबद्ध क्रम में डाली जाएँ, तो n नोड वाले बाइनरी सर्च ट्री की सबसे खराब स्थिति में ऊँचाई क्या होगी?

  1. Alog₂ n
  2. B1
  3. Cn (यह लिंक्ड लिस्ट बन जाता है)
  4. D√n
12.डेटा संरचनाएँकठिन

एक डायनेमिक ऐरे भर जाने पर दोगुना होता है। कई कार्यान्वयन उसे आधा भरा होने के बजाय केवल एक-चौथाई भरा होने पर ही क्यों छोटा करते हैं?

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

पूर्ण ग्राफ़ K5 में कितने भिन्न हैमिल्टन परिपथ H हैं? जो परिपथ केवल प्रारंभिक शीर्ष या दिशा में भिन्न हों, उन्हें एक ही गिना जाता है।

K5
H =
14.ग्राफ़ सिद्धांतकठिन
12133121215157ABCDEF

डाइक्स्ट्रा का एल्गोरिथ्म A से चलता है। उस शीर्ष पर क्लिक करें जो चक्र 4 में निर्धारित (स्थायी) होता है; A स्वयं चक्र 1 है।

प्रारंभ: Aचक्र 4
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
15.डेटाबेस और SQLमध्यम

कौन-सी क्वेरी प्रति ग्राहक ऑर्डरों की संख्या लौटाती है?

  1. ASELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id
  2. BSELECT customer_id, COUNT(*) FROM orders ORDER BY customer_id
  3. CSELECT DISTINCT COUNT(*) FROM orders
  4. DSELECT customer_id FROM orders WHERE COUNT(*) > 0
16.डेटाबेस और SQLकठिन

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

  1. AUNKNOWN
  2. BTRUE
  3. CNULL, इसलिए पंक्ति हमेशा अस्वीकार होती है
  4. DFALSE
17.कंप्यूटर नेटवर्कमध्यम

एक संकेत फ़ाइबर में लगभग 2 × 10⁸ m/s की गति से 2000 km चलता है। प्रसार विलंब (propagation delay) क्या है?

  1. A0.1 ms
  2. B10 ms
  3. C1 ms
  4. D100 ms
18.कंप्यूटर नेटवर्ककठिन

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

  1. Aकोई भी खोए फ़्रेम कभी फिर से नहीं भेजता
  2. Bदोनों शुरुआत से पूरी विंडो फिर से भेजते हैं
  3. CGo-Back-N खोया फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है; Selective Repeat केवल खोया फ़्रेम
  4. DGo-Back-N केवल खोया फ़्रेम फिर से भेजता है; Selective Repeat वह फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है
19.IPv4 सबनेटिंगमध्यम
/?11111111111111111111110000000000नेटवर्क बिटहोस्ट बिट

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

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

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

10.20.101.118/30
x =

3विलयन

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

उत्तर: U = 240

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

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

16 = 0001 0000
उलटा हुआ: 1110 1111
+1 → 1111 0000

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

1111 0000₂ = 256 − 16 = 240

उत्तर

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

उत्तर: N = −32768

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

सबसे ऋणात्मक मान

−215 = −32768

उत्तर

N = −32768
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 होता है जब दोनों पक्ष बराबर हों।

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

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

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

(p ∧ (r ↔ ¬q)) ∨ ¬(r → ¬p): 1, 1, 1, 0, 0, 0, 0, 0
N = 3

उत्तर

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

उत्तर: a = 0, b = 1

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

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

a = 1, b = 1: 1 0 | 0
a = 1, b = 0: 0 0 | 1
a = 0, b = 1: 1 1 | 0
a = 0, b = 0: 1 1 | 1

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

a = 0, b = 1

उत्तर

a = 0, b = 1

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

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

उत्तर: L = 7

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

ABC00011110011001130204151706

1 को समूहित करें

हर समूह 2ᵏ खानों का आयत होता है; किनारे के खाने विपरीत किनारे के खानों के पड़ोसी होते हैं।

BC
AC
A′B′C′

न्यूनतम SOP रूप

F = BC + AC + A′B′C′
L = 7

उत्तर

L = 7
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

D फ़्लिप-फ़्लॉप हर आरोही कोर पर D को कॉपी करता है: Q⁺ = D।

1: D = 1 → Q = 1
2: D = 1 → Q = 1
3: D = 1 → Q = 1
4: D = 0 → Q = 0
5: D = 1 → Q = 1
6: D = 0 → Q = 0
7: D = 0 → Q = 0
8: D = 0 → Q = 0

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

क्लॉक कोर 4

उत्तर

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

उत्तर: x = 102

प्रतिलोम और सर्वांगसमताएँ: 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 = 6 + 8k

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

6 + 8k ≡ 11 (mod 13) → 8k ≡ 5 (mod 13)
k ≡ 5·5 ≡ 12 (mod 13)

परिणाम

x = 6 + 8·12 = 102
x = 102
जाँच: 102 mod 8 = 6, 102 mod 13 = 11

उत्तर

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

उत्तर: m = 492

मॉड्यूलर घात और 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 = 1147, φ(n) = 1080
d = 7−1 mod 1080 = 463

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

463 = 256 + 128 + 64 + 8 + 4 + 2 + 1
4181 ≡ 418 (mod 1147)
4182 ≡ 380 (mod 1147)
4184 ≡ 1025 (mod 1147)
4188 ≡ 1120 (mod 1147)
41816 ≡ 729 (mod 1147)
41832 ≡ 380 (mod 1147)
41864 ≡ 1025 (mod 1147)
418128 ≡ 1120 (mod 1147)
418256 ≡ 729 (mod 1147)
418463 ≡ 418·380·1025·1120·1025·1120·729 ≡ 492 (mod 1147)

संदेश

m = 492
जाँच: 4927 mod 1147 = 418

उत्तर

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

उत्तर: C · ग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है

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

ग्रीडी 4 + 1 + 1 = 3 सिक्के लेती है, पर 3 + 3 में केवल 2 लगते हैं, इसलिए इस सिक्का प्रणाली के लिए ग्रीडी इष्टतम नहीं है; डायनेमिक प्रोग्रामिंग है।

उत्तर

C · ग्रीडी 3 सिक्के उपयोग करती है; इष्टतम 2 है
10.एल्गोरिदम और जटिलता

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

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

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

उत्तर

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

उत्तर: C · n (यह लिंक्ड लिस्ट बन जाता है)

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

क्रमबद्ध इंसर्शन से n ऊँचाई वाला विकृत (degenerate) ट्री बनता है, जिससे खोज O(n) हो जाती है। संतुलित ट्री इसे रोकते हैं।

उत्तर

C · n (यह लिंक्ड लिस्ट बन जाता है)
12.डेटा संरचनाएँ

उत्तर: B · सीमा के पास push और pop बारी-बारी से होने पर बार-बार आकार बदलने से बचने के लिए

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

आधे पर छोटा करने से ऐसे अनुक्रम में हर ऑपरेशन पर आकार बदल सकता है; 1/4 और पूर्ण के बीच का अंतर एमॉर्टाइज़्ड लागत को O(1) रखता है।

उत्तर

B · सीमा के पास push और pop बारी-बारी से होने पर बार-बार आकार बदलने से बचने के लिए
13.ग्राफ़ सिद्धांत

उत्तर: H = 12

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

गिनें

H = (5 − 1)!/2 = 24/2 = 12

उत्तर

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

उत्तर: D

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

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

1. A (0): B: 12, C: 13
2. B (12): D: 24
3. C (13): E: 25
4. D (24): F: 39
5. E (25): F: 32
6. F (32)

चक्र 4

D

उत्तर

D
15.डेटाबेस और SQL

उत्तर: A · SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id

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

GROUP BY customer_id प्रत्येक ग्राहक के लिए एक समूह बनाता है, और COUNT(*) प्रत्येक समूह की पंक्तियाँ गिनता है।

उत्तर

A · SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id
16.डेटाबेस और SQL

उत्तर: B · TRUE

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

x > 5 UNKNOWN है, पर TRUE के साथ OR हर हाल में TRUE है, इसलिए पंक्ति रखी जाती है; इसी तरह UNKNOWN AND FALSE, FALSE होगा।

उत्तर

B · TRUE
17.कंप्यूटर नेटवर्क

उत्तर: B · 10 ms

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

2 × 10⁶ m / 2 × 10⁸ m/s = 0.01 s = 10 ms। प्रसार विलंब दूरी और माध्यम पर निर्भर करता है, पैकेट के आकार पर नहीं।

उत्तर

B · 10 ms
18.कंप्यूटर नेटवर्क

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

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

Go-Back-N प्राप्तकर्ता क्रम से बाहर फ़्रेमों को हटा देता है, इसलिए प्रेषक को हानि के बाद सब कुछ दोहराना पड़ता है। Selective Repeat उन्हें बफ़र करता है और केवल गायब फ़्रेम माँगता है।

उत्तर

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

उत्तर: p = 22

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

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

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

उपसर्ग लंबाई

p = 32 − 10 = 22

उत्तर

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

उत्तर: x = 116

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

ब्लॉक आकार

22 = 4

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

नेटवर्क: ⌊118/4⌋·4 = 116
ब्रॉडकास्ट: 116 + 4 − 1 = 119
उपयोगी होस्ट: 117 … 118

उत्तर

x = 116

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