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

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

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

बिट को 1000 1110 << 3 के 8-बिट परिणाम पर सेट करें। दशमलव में परिणाम का मान R क्या है?

1000 1110<< 3
R =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
¬q ∧ ¬r¬q ∨ ¬r¬q ∧ r¬q ∨ r

कौन-सा सूत्र ¬(q ∧ r) के तार्किक रूप से तुल्य है? उस पर क्लिक करें।

¬(q ∧ r)
  1. 1¬q ∧ ¬r
  2. 2¬q ∨ ¬r
  3. 3¬q ∧ r
  4. 4¬q ∨ r
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
∃x (¬F(x) ∧ ¬G(x))∀x (¬F(x) ∧ ¬G(x))∀x (F(x) → ¬G(x))∀x (F(x) ∧ ¬G(x))

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

¬∃x (F(x) ∧ G(x))
  1. 1∃x (¬F(x) ∧ ¬G(x))
  2. 2∀x (¬F(x) ∧ ¬G(x))
  3. 3∀x (F(x) → ¬G(x))
  4. 4∀x (F(x) ∧ ¬G(x))
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABCD0001111000011110111111

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

F = Σm(1, 3, 4, 9, 11, 15)
  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-मानचित्र और फ़्लिप-फ़्लॉपकठिन
DQ3​Q3​DQ2​Q2​DQ1​Q1​DQ0​Q0​CLKJOHNSON

एक 4-बिट जॉनसन काउंटर Q₃Q₂Q₁Q₀ 0000 से शुरू होता है। हर क्लॉक कोर पर बिट एक स्थान दाईं ओर खिसकते हैं (Q₃ → Q₂ → Q₁ → Q₀) और Q₃ को Q₀ का उलटा मिलता है। 6 क्लॉक कोरों के बाद अवस्था Q = Q₃Q₂Q₁Q₀ दशमलव संख्या में दें।

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

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

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

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

a = 71k = 89n = 82
7189 mod 82 =
9.एल्गोरिदम और जटिलतामध्यम

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

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

बाइनरी काउंटर को बढ़ाने (increment) की एमॉर्टाइज़्ड लागत क्या है, यह देखते हुए कि एक वृद्धि कई बिट पलट सकती है?

  1. Aप्रति वृद्धि O(n)
  2. Bप्रति वृद्धि O(log n)
  3. Cप्रति वृद्धि O(n log n)
  4. Dप्रति वृद्धि O(1)
11.डेटा संरचनाएँमध्यम

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

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

रेड-ब्लैक ट्री के नियम n कुंजियों वाले ट्री की ऊँचाई के बारे में क्या गारंटी देते हैं?

  1. Aऊँचाई अधिकतम n / 2 है
  2. Bऊँचाई अधिकतम log2 n + 1 है
  3. Cऊँचाई अधिकतम 2 log2(n + 1) है
  4. Dऊँचाई ठीक log2 n है
13.ग्राफ़ सिद्धांतमध्यम

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

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

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

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

किस ACID गुण का अर्थ है कि समवर्ती ट्रांज़ैक्शन एक-दूसरे के अधूरे परिवर्तन नहीं देखते?

  1. Aस्थायित्व (Durability)
  2. Bपृथक्करण (Isolation)
  3. Cपरमाणुता (Atomicity)
  4. Dउपलब्धता (Availability)
16.डेटाबेस और SQLकठिन

अज्ञात गहराई वाले संगठन वृक्ष में किसी मैनेजर के नीचे हर कर्मचारी को खोजने के लिए कौन-सी SQL सुविधा सबसे उपयुक्त है?

  1. Amanager_id पर GROUP BY
  2. Bmanager_id पर UNIQUE कंस्ट्रेंट
  3. Cemployees टेबल का manager_id पर एक अकेला सेल्फ़-जॉइन
  4. Dएक रिकर्सिव कॉमन टेबल एक्सप्रेशन (WITH RECURSIVE)
17.कंप्यूटर नेटवर्कमध्यम

RIP मार्ग चुनने के लिए कौन-सा मापदंड (metric) उपयोग करता है?

  1. Aलिंक बैंडविड्थ
  2. Bमापा गया विलंब
  3. Cव्यावसायिक नीति
  4. Dहॉप गणना (hop count)
18.कंप्यूटर नेटवर्ककठिन

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

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

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

192.168.10.0/245 subnets
H =
20.IPv4 सबनेटिंगकठिन
अंतिम ऑक्टेट = 108012816413201618140201नेटवर्कहोस्ट

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

10.20.243.108/30
x =

3विलयन

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

उत्तर: U = 206

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

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

50 = 0011 0010
उलटा हुआ: 1100 1101
+1 → 1100 1110

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

1100 1110₂ = 256 − 50 = 206

उत्तर

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

उत्तर: R = 112

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

बिट-दर-बिट

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

1000 1110 << 3
= 0111 0000

परिणाम का मान

0111 0000₂ = 112

उत्तर

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

उत्तर: ¬q ∨ ¬r

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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 ∧ b) ≡ ¬a ∨ ¬b। ∧, ∨ बन जाता है और दोनों भागों का निषेध होता है।
¬(q ∧ r) ≡ ¬q ∨ ¬r

सत्यमान सारणी से जाँच

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

उत्तर

¬q ∨ ¬r

पट्टी के बाद के स्तंभ विकल्प हैं, दिखाए गए क्रम में।

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

उत्तर: ∀x (F(x) → ¬G(x))

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

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

¬∃x (F(x) ∧ G(x)) ≡ ∀x (F(x) → ¬G(x))

उत्तर

∀x (F(x) → ¬G(x))

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

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

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

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

हर 1 के पड़ोसी

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

m4: m5, m6, m0, m12 → 0
ABCD0001111000011110111111

अकेला 1

m4 = A′BC′D′ → AB = 01, CD = 00

उत्तर

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

उत्तर: Q = 3

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

हर कोर के बाद की अवस्था

0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011

दशमलव मान

0011₂ = 3

उत्तर

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

उत्तर: φ(95) = 72

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

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

95 = 5·19

टोशेंट

φ(95) = φ(5)·φ(19) = 4·18 = 72

उत्तर

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

उत्तर: 7189 mod 82 = 29

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

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

89 = 10110012 = 64 + 16 + 8 + 1

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

711 ≡ 71 (mod 82)
712 ≡ 39 (mod 82)
714 ≡ 45 (mod 82)
718 ≡ 57 (mod 82)
7116 ≡ 51 (mod 82)
7132 ≡ 59 (mod 82)
7164 ≡ 37 (mod 82)

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

7189 ≡ 71·57·51·37 ≡ 29 (mod 82)

उत्तर

7189 mod 82 = 29
9.एल्गोरिदम और जटिलता

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

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

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

उत्तर

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

उत्तर: D · प्रति वृद्धि O(1)

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

n वृद्धियों में बिट i लगभग n / 2ⁱ बार पलटता है, इसलिए कुल 2n से कम पलटाव होते हैं, यानी प्रति वृद्धि औसत O(1)।

उत्तर

D · प्रति वृद्धि O(1)
11.डेटा संरचनाएँ

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

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

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

उत्तर

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

उत्तर: C · ऊँचाई अधिकतम 2 log2(n + 1) है

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

हर पथ में समान संख्या में काले नोड होते हैं और लाल नोड आसन्न नहीं हो सकते, इसलिए सबसे लंबा पथ सबसे छोटे का अधिकतम दोगुना है, जिससे ऊँचाई O(log n) होती है।

उत्तर

C · ऊँचाई अधिकतम 2 log2(n + 1) है
13.ग्राफ़ सिद्धांत

उत्तर: H = 3

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

गिनें

H = (4 − 1)!/2 = 6/2 = 3

उत्तर

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

उत्तर: कोर BD

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

क्रुस्कल का एल्गोरिथ्म

1. BC (1)
2. BD (8)
3. AC (9)
4. BE (14)

कोर संख्या 2

BD

उत्तर

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

उत्तर: B · पृथक्करण (Isolation)

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

पृथक्करण समवर्ती ट्रांज़ैक्शनों को अलग रखता है; आइसोलेशन लेवल तय करते हैं कि इसे कितनी कड़ाई से लागू किया जाए।

उत्तर

B · पृथक्करण (Isolation)
16.डेटाबेस और SQL

उत्तर: D · एक रिकर्सिव कॉमन टेबल एक्सप्रेशन (WITH RECURSIVE)

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

रिकर्सिव CTE एक एंकर क्वेरी से शुरू होता है और पिछले परिणाम को बार-बार टेबल से जोड़ता है, इसलिए यह किसी भी गहराई के पदानुक्रम संभाल लेता है।

उत्तर

D · एक रिकर्सिव कॉमन टेबल एक्सप्रेशन (WITH RECURSIVE)
17.कंप्यूटर नेटवर्क

उत्तर: D · हॉप गणना (hop count)

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

RIP एक distance-vector प्रोटोकॉल है जो हॉप गिनता है, जिसमें 16 का अर्थ अप्राप्य (unreachable) है। यह इसे छोटे नेटवर्कों तक सीमित करता है।

उत्तर

D · हॉप गणना (hop count)
18.कंप्यूटर नेटवर्क

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

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

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

उत्तर

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

उत्तर: H = 30

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

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

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

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

25 − 2 = 30

उत्तर

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

उत्तर: x = 108

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

ब्लॉक आकार

22 = 4

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

नेटवर्क: ⌊108/4⌋·4 = 108
ब्रॉडकास्ट: 108 + 4 − 1 = 111
उपयोगी होस्ट: 109 … 110

उत्तर

x = 108

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