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

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

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

1111 00108 bit
N =
2.संख्या पद्धतियाँकठिन
8 bit1 px800 px600 pxM = ? KiB

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

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

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

(¬p → r) ∨ (r ∧ (¬p ↔ ¬q))
N =
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
pqrq → rp → rq → p111110101100011010001000

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

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

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

F = Σm(0, 4, 7, 10, 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-मानचित्र और फ़्लिप-फ़्लॉपकठिन
FFQ0​Q0​FFQ1​Q1​FFQ2​Q2​FFQ3​Q3​FFQ4​Q4​CLKMOD-24

एक mod-24 काउंटर को 24 भिन्न अवस्थाओं से गुज़रना है। उसे कम से कम कितने फ़्लिप-फ़्लॉप n चाहिए?

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

20x ≡ 27 (mod 71) हल करें। हल x दें, जहाँ 0 < x < 71।

20x ≡ 27 (mod 71)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन

30x ≡ 28 (mod 34) हल करें। सबसे छोटा धनात्मक हल x दें।

30x ≡ 28 (mod 34)
x =
9.एल्गोरिदम और जटिलतामध्यम

एक फ़ंक्शन n इटरेशन का एक लूप चलाता है और फिर, अलग से, n इटरेशन का एक और लूप। इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

टोपोलॉजिकल सॉर्टिंग केवल किसके लिए संभव है?

  1. Aअनडायरेक्टेड ग्राफ़
  2. Bऋणात्मक वेट वाले ग्राफ़
  3. Cडायरेक्टेड एसाइक्लिक ग्राफ़ (DAG)
  4. Dकम्प्लीट ग्राफ़
11.डेटा संरचनाएँमध्यम

एक क्यू दो स्टैक से बनाई गई है: "in" स्टैक पर push करें, और "out" स्टैक से pop करें, ख़ाली होने पर उसे "in" से फिर भरें। प्रति ऑपरेशन एमॉर्टाइज़्ड लागत क्या है?

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

सेगमेंट ट्री का उपयोग आमतौर पर किसके लिए किया जाता है?

  1. Aग्राफ़ के किनारे संग्रहीत करने के लिए
  2. Bरेंज क्वेरी (जैसे रेंज योग) और अपडेट का O(log n) में उत्तर देने के लिए
  3. Cहर प्रीफ़िक्स को अलग ट्री नोड में संग्रहीत करके स्ट्रिंग्स को वर्णानुक्रम में क्रमबद्ध करने के लिए
  4. Dस्टैक लागू करने के लिए
13.ग्राफ़ सिद्धांतमध्यम

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

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

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

प्रारंभ: Bk = 2
  1. 1कोर AB
  2. 2कोर AC
  3. 3कोर BC
  4. 4कोर BD
  5. 5कोर CE
  6. 6कोर DE
  7. 7कोर BE
15.डेटाबेस और SQLमध्यम

कौन-सी क्वेरी उन ग्राहकों को सूचीबद्ध करती है जिन्होंने कभी ऑर्डर नहीं दिया?

  1. ASELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id = NULL
  2. BSELECT c.name FROM customers c INNER JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
  3. CSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
  4. DSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NOT NULL
16.डेटाबेस और SQLकठिन

बिना उपयोगी इंडेक्स वाली दो बड़ी टेबलों के बीच समता जॉइन के लिए ऑप्टिमाइज़र अक्सर कौन-सा जॉइन एल्गोरिदम चुनता है?

  1. Aक्रॉस जॉइन
  2. Bहैश जॉइन
  3. Cप्राइमरी की पर बिटमैप जॉइन
  4. Dइंडेक्स लुकअप के साथ नेस्टेड लूप जॉइन
17.कंप्यूटर नेटवर्कमध्यम

VLAN का मुख्य उद्देश्य क्या है?

  1. Aस्विचों के बीच सारा ट्रैफ़िक एन्क्रिप्ट करना ताकि अन्य विभाग उसे न पढ़ सकें
  2. Bएक भौतिक स्विच्ड नेटवर्क को अलग-अलग ब्रॉडकास्ट डोमेन में बाँटना
  3. Cहर स्विच पोर्ट की गति बढ़ाना
  4. Dहर उपकरण को सार्वजनिक IP पता देना
18.कंप्यूटर नेटवर्ककठिन

बार-बार टकरावों के बाद क्लासिक Ethernet स्टेशन अपना प्रतीक्षा समय एक ऐसी सीमा से चुनते हैं जो हर बार दोगुनी होती है। क्यों?

  1. Aसाझा केबल पर सबसे ऊँचे MAC पते वाले स्टेशन को प्राथमिकता देने के लिए
  2. Bजब कई स्टेशन प्रतिस्पर्धा करें तो फिर से टकराने की संभावना कम करने के लिए
  3. Cकेबल को संकेत आगे तक ले जाने देने के लिए
  4. Dसभी स्टेशनों को एक घड़ी से समकालिक करने के लिए
19.IPv4 सबनेटिंगमध्यम
/24 → /2711111111111111111111111111100000नेटवर्क बिटहोस्ट बिट

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

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

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

172.20.43.195/23
x =

3विलयन

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

उत्तर: N = −14

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

मान जोड़ें

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

−128 + 64 + 32 + 16 + 2 = −14

उत्तर

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

उत्तर: M = 468.8 KiB

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

बिट और बाइट

800·600·8 = 3840000 bit = 480000 B

KiB में बदलें

480000/1024 = 468.75 KiB

उत्तर

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

उत्तर: N = 6

सत्यमान सारणियाँ: 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: ¬p = 0, ¬p → r = 1, ¬q = 0, ¬p ↔ ¬q = 1, r ∧ (¬p ↔ ¬q) = 1, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 1
p = 1, q = 1, r = 0: ¬p = 0, ¬p → r = 1, ¬q = 0, ¬p ↔ ¬q = 1, r ∧ (¬p ↔ ¬q) = 0, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 1
p = 1, q = 0, r = 1: ¬p = 0, ¬p → r = 1, ¬q = 1, ¬p ↔ ¬q = 0, r ∧ (¬p ↔ ¬q) = 0, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 1
p = 1, q = 0, r = 0: ¬p = 0, ¬p → r = 1, ¬q = 1, ¬p ↔ ¬q = 0, r ∧ (¬p ↔ ¬q) = 0, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 1
p = 0, q = 1, r = 1: ¬p = 1, ¬p → r = 1, ¬q = 0, ¬p ↔ ¬q = 0, r ∧ (¬p ↔ ¬q) = 0, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 1
p = 0, q = 1, r = 0: ¬p = 1, ¬p → r = 0, ¬q = 0, ¬p ↔ ¬q = 0, r ∧ (¬p ↔ ¬q) = 0, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 0
p = 0, q = 0, r = 1: ¬p = 1, ¬p → r = 1, ¬q = 1, ¬p ↔ ¬q = 1, r ∧ (¬p ↔ ¬q) = 1, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 1
p = 0, q = 0, r = 0: ¬p = 1, ¬p → r = 0, ¬q = 1, ¬p ↔ ¬q = 1, r ∧ (¬p ↔ ¬q) = 0, (¬p → r) ∨ (r ∧ (¬p ↔ ¬q)) = 0

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

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

उत्तर

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

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

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

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

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

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

p = 0, q = 1, r = 1

उत्तर

p = 0, q = 1, r = 1

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

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

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

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

हर 1 के पड़ोसी

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

m7: m6, m5, m3, m15 → 0
ABCD000111100001111011111

अकेला 1

m7 = A′BCD → AB = 01, CD = 11

उत्तर

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

उत्तर: n = 5

फ़्लिप-फ़्लॉप और काउंटर: फ़्लिप-फ़्लॉप केवल सक्रिय क्लॉक कोर पर बदलता है। 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।

फ़्लिप-फ़्लॉप की संख्या

2ⁿ ≥ 24 → n = 5 (2⁵ = 32)

उत्तर

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

उत्तर: x = 12

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

20 का प्रतिलोम

r = 71, t = 0
r = 20, q = 3, t = 1
r = 11, q = 1, t = −3
r = 9, q = 1, t = 4
r = 2, q = 4, t = −7
r = 1, q = 2, t = 32
20−1 ≡ 32 (mod 71)

हल करें

x ≡ 32·27 = 864 ≡ 12 (mod 71)
जाँच: 20·12 = 240 ≡ 27 (mod 71)

उत्तर

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

उत्तर: x = 10

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

gcd से भाग दें

gcd(30, 34) = 2
15x ≡ 14 (mod 17)

घटी हुई सर्वांगसमता हल करें

15−1 ≡ 8 (mod 17) → x ≡ 10 (mod 17)

34 के मापांक में हल

x ∈ {10, 27}
x = 10

उत्तर

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

उत्तर: B · O(n)

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

n + n = 2n, और स्थिर गुणक हटा दिए जाते हैं, इसलिए फ़ंक्शन O(n) है।

उत्तर

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

उत्तर: C · डायरेक्टेड एसाइक्लिक ग्राफ़ (DAG)

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

टोपोलॉजिकल क्रम तभी और केवल तभी मौजूद होता है जब डायरेक्टेड ग्राफ़ में कोई चक्र न हो; इसे DFS या Kahn के एल्गोरिदम से O(V + E) में खोजा जा सकता है।

उत्तर

C · डायरेक्टेड एसाइक्लिक ग्राफ़ (DAG)
11.डेटा संरचनाएँ

उत्तर: A · O(1)

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

हर तत्व कुल मिलाकर अधिकतम दो बार push और pop होता है, इसलिए भले ही एक बार फिर से भरने में O(n) लगे, अनुक्रम पर औसत O(1) है।

उत्तर

A · O(1)
12.डेटा संरचनाएँ

उत्तर: B · रेंज क्वेरी (जैसे रेंज योग) और अपडेट का O(log n) में उत्तर देने के लिए

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

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

उत्तर

B · रेंज क्वेरी (जैसे रेंज योग) और अपडेट का O(log n) में उत्तर देने के लिए
13.ग्राफ़ सिद्धांत

उत्तर: H = 12

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

गिनें

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

उत्तर

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

उत्तर: कोर DE

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

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

1. BD (8)
2. DE (3)
3. AB (14)
4. AC (1)

कोर संख्या 2

DE

उत्तर

कोर DE
15.डेटाबेस और SQL

उत्तर: C · SELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL

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

लेफ़्ट जॉइन सभी ग्राहकों को रखता है और मेल न होने पर ऑर्डर कॉलमों को NULL से भरता है; फिर IS NULL ठीक उन्हीं ग्राहकों को चुनता है।

उत्तर

C · SELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
16.डेटाबेस और SQL

उत्तर: B · हैश जॉइन

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

हैश जॉइन एक इनपुट पर हैश टेबल बनाता है और दूसरे से उसकी जाँच करता है, जो बिना इंडेक्स के बड़े equi-join के लिए अच्छा काम करता है।

उत्तर

B · हैश जॉइन
17.कंप्यूटर नेटवर्क

उत्तर: B · एक भौतिक स्विच्ड नेटवर्क को अलग-अलग ब्रॉडकास्ट डोमेन में बाँटना

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

VLAN पोर्टों को तार्किक रूप से समूहित करते हैं, इसलिए ब्रॉडकास्ट हर VLAN के भीतर रहते हैं। इससे सुरक्षा सुधरती है और ब्रॉडकास्ट ट्रैफ़िक सीमित होता है।

उत्तर

B · एक भौतिक स्विच्ड नेटवर्क को अलग-अलग ब्रॉडकास्ट डोमेन में बाँटना
18.कंप्यूटर नेटवर्क

उत्तर: B · जब कई स्टेशन प्रतिस्पर्धा करें तो फिर से टकराने की संभावना कम करने के लिए

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

हर अगला टकराव अधिक प्रतिस्पर्धा का संकेत देता है, इसलिए यादृच्छिक सीमा बढ़ती है और स्टेशनों के अलग-अलग स्लॉट चुनने की संभावना बढ़ती है। यह केंद्रीय नियंत्रण के बिना भार के अनुसार ढल जाता है।

उत्तर

B · जब कई स्टेशन प्रतिस्पर्धा करें तो फिर से टकराने की संभावना कम करने के लिए
19.IPv4 सबनेटिंग

उत्तर: H = 30

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

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

23 = 8 ≥ 6 → b = 3, /27

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

25 − 2 = 30

उत्तर

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

उत्तर: x = 43

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

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

21 = 2

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

नेटवर्क: 172.20.42.0
ब्रॉडकास्ट: 172.20.43.255

उत्तर

x = 43

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