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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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-बिट दो का पूरक?−128?64?32?16?8?4?2?1

−119 को 8-बिट दो के पूरक पैटर्न के रूप में लिखें। पैटर्न को अचिह्नित द्विआधारी संख्या के रूप में पढ़ें: दशमलव में इसका मान U क्या है?

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

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

1101 1101OR1000 0111
R =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
a → (b ∨ c)¬a → ¬(b ∨ c)(b ∨ c) ∧ ¬a¬(b ∨ c) → ¬a

आप (b ∨ c) → a को प्रतिधनात्मक द्वारा सिद्ध करना चाहते हैं। इसके बजाय कौन-सा निहितार्थ सिद्ध करेंगे? उस पर क्लिक करें।

(b ∨ c) → a
  1. 1a → (b ∨ c)
  2. 2¬a → ¬(b ∨ c)
  3. 3(b ∨ c) ∧ ¬a
  4. 4¬(b ∨ c) → ¬a
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
pp ∧ qr¬r

आधार-वाक्य p ∨ q; p → r; q → r दिए गए हैं। इनसे कौन-सा निष्कर्ष निकलता है? उस पर क्लिक करें।

p ∨ qp → rq → r
  1. 1p
  2. 2p ∧ q
  3. 3r
  4. 4¬r
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABCD00011110000111101111111

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

F = Σm(3, 4, 7, 10, 11, 14, 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₀ का उलटा मिलता है। 9 क्लॉक कोरों के बाद अवस्था Q = Q₃Q₂Q₁Q₀ दशमलव संख्या में दें।

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

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

n = 34 = 2·17
φ(34) =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
67c = me​ mod n?m = cd​ mod nm(n, e) = (119, 5)d

संदेश m = 67 को RSA सार्वजनिक कुंजी (n, e) = (119, 5) से एन्क्रिप्ट करें। सिफरटेक्स्ट c ज्ञात करें।

n = 119e = 5m = 67
c =
9.एल्गोरिदम और जटिलतामध्यम

n तत्वों के ऐरे के लिए मर्ज सॉर्ट के रिकर्शन में कितने स्तर होते हैं?

  1. Aलगभग n
  2. Bलगभग n / 2
  3. Cलगभग log₂ n
  4. Dलगभग √n
10.एल्गोरिदम और जटिलताकठिन

डायनेमिक प्रोग्रामिंग से हल की गई 0/1 नैपसैक (knapsack) समस्या में O(nW) समय लगता है। इसे स्यूडो-पॉलिनोमियल (pseudo-polynomial) क्यों कहा जाता है?

  1. Aक्योंकि n हमेशा छोटा होता है
  2. Bक्योंकि एल्गोरिदम यादृच्छिक (randomised) है और उसका रनिंग टाइम हर इनपुट के साथ बदलता है
  3. Cक्योंकि यह केवल W = 0 के लिए काम करता है
  4. DW एक संख्या है, इसलिए समय W को लिखने में प्रयुक्त बिट्स की संख्या में घातांकी है
11.डेटा संरचनाएँमध्यम

एक बाइनरी ट्री का रूट 1 है, जिसका बायाँ चाइल्ड 2 और दायाँ चाइल्ड 3 है; नोड 2 के चाइल्ड 4 (बायाँ) और 5 (दायाँ) हैं। प्रीऑर्डर ट्रैवर्सल क्या है?

  1. A4 2 5 1 3
  2. B1 2 3 4 5
  3. C1 2 4 5 3
  4. D4 5 2 3 1
12.डेटा संरचनाएँकठिन

रेड-ब्लैक ट्री को कौन-सा गुण अवश्य पूरा करना चाहिए?

  1. Aरूट लाल होना चाहिए
  2. Bहर लाल नोड के चाइल्ड लाल होने चाहिए, इसलिए लाल नोड्स पत्तियों तक अटूट शृंखला बनाते हैं
  3. Cकिसी नोड से उसकी वंशज पत्तियों तक के हर पथ में काले नोड्स की संख्या समान होती है
  4. Dहर नोड लाल होना चाहिए
13.ग्राफ़ सिद्धांतमध्यम

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

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

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

प्रारंभ: Ek = 2
  1. 1कोर AB
  2. 2कोर AC
  3. 3कोर BC
  4. 4कोर BD
  5. 5कोर CE
  6. 6कोर DE
  7. 7कोर DF
  8. 8कोर EF
  9. 9कोर GB
  10. 10कोर GC
  11. 11कोर GD
  12. 12कोर GE
15.डेटाबेस और SQLमध्यम

किसी पंक्ति के लिए WHERE EXISTS (subquery) कब सत्य होता है?

  1. Aजब सबक्वेरी ठीक एक पंक्ति लौटाए
  2. Bजब सबक्वेरी कम से कम एक पंक्ति लौटाए
  3. Cजब सबक्वेरी शून्य से बड़ी संख्या लौटाए
  4. Dजब सबक्वेरी कोई NULL मान न लौटाए
16.डेटाबेस और SQLकठिन

समवर्ती ट्रांज़ैक्शनों के शेड्यूल को सीरियलाइज़ेबल कब कहा जाता है?

  1. Aजब उसका प्रभाव उन्हीं ट्रांज़ैक्शनों के किसी क्रमिक (serial) निष्पादन के समतुल्य हो
  2. Bजब हर ट्रांज़ैक्शन को एक क्रम संख्या दी जाती है
  3. Cजब ट्रांज़ैक्शन केवल एक CPU पर चलते हैं
  4. Dजब कोई ट्रांज़ैक्शन कभी डेटा नहीं पढ़ता
17.कंप्यूटर नेटवर्कमध्यम

इनमें से कौन-सी निजी IPv4 पता सीमा (range) है?

  1. A192.168.0.0/16
  2. B100.0.0.0/8
  3. C200.1.1.0/24
  4. D8.8.8.0/24
18.कंप्यूटर नेटवर्ककठिन

TCP window scale विकल्प क्यों शुरू किया गया?

  1. A16-बिट विंडो फ़ील्ड विंडो को 65,535 बाइट तक सीमित करता है, जो तेज़ लंबी दूरी के मार्गों के लिए बहुत छोटा है
  2. B32-बिट विंडो फ़ील्ड बहुत बड़ा था और भेजे गए हर TCP सेगमेंट में हेडर की जगह बर्बाद करता था
  3. Cइसके बिना TCP लंबी दूरी के लिंकों पर खोए सेगमेंटों का पता नहीं लगा सकता था
  4. DUDP को भीड़ भरे मार्गों पर अपनी प्रेषण दर नियंत्रित करने का तरीका चाहिए था
19.IPv4 सबनेटिंगमध्यम
255.255.255.25211111111111111111111111111111100नेटवर्क बिटहोस्ट बिट

एक सबनेट मास्क 255.255.255.252 का उपयोग करता है। इसमें कितने उपयोगी होस्ट पते H हैं?

255.255.255.252
H =
20.IPv4 सबनेटिंगकठिन
तीसरा ऑक्टेट 48 … 50012806413211608040201साझाभिन्न

एक राउटर के पास इन नेटवर्कों के लिए रूट हैं: 10.184.48.0/24, 10.184.49.0/24, 10.184.50.0/24। इन सबको कवर करने वाले एकल सारांश रूट की सबसे लंबी उपसर्ग लंबाई p क्या है?

10.184.48.0/24 … 10.184.50.0/24
p =

3विलयन

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

उत्तर: U = 137

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

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

119 = 0111 0111
उलटा हुआ: 1000 1000
+1 → 1000 1001

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

1000 1001₂ = 256 − 119 = 137

उत्तर

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

उत्तर: R = 223

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

बिट-दर-बिट

OR वहाँ 1 देता है जहाँ कम से कम एक बिट 1 हो।

1101 1101
OR 1000 0111
= 1101 1111

परिणाम का मान

1101 1111₂ = 223

उत्तर

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

उत्तर: ¬a → ¬(b ∨ c)

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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 ∨ c, b = a

प्रतिधनात्मक

¬b → ¬a = ¬a → ¬(b ∨ c)

उत्तर

¬a → ¬(b ∨ c)

प्रतिधनात्मक मूल कथन के तुल्य है, इसलिए उसे सिद्ध करने से कथन सिद्ध हो जाता है।

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

उत्तर: r

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

वे पंक्तियाँ जिनमें सभी आधार-वाक्य सत्य हैं

p = 1, q = 1, r = 1: p = 1, p ∧ q = 1, r = 1, ¬r = 0
p = 1, q = 0, r = 1: p = 1, p ∧ q = 0, r = 1, ¬r = 0
p = 0, q = 1, r = 1: p = 0, p ∧ q = 0, r = 1, ¬r = 0

निष्कर्ष

r (स्थिति-विभाजन द्वारा उपपत्ति)

उत्तर

r
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
ABCD00011110000111101111111

अकेला 1

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

उत्तर

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

उत्तर: Q = 8

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

दशमलव मान

1000₂ = 8

उत्तर

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

उत्तर: φ(34) = 16

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

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

34 = 2·17

टोशेंट

φ(34) = φ(17)·φ(2) = 16·1 = 16

उत्तर

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

उत्तर: c = 16

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

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

5 = 4 + 1
671 ≡ 67 (mod 119)
672 ≡ 86 (mod 119)
674 ≡ 18 (mod 119)
675 ≡ 67·18 ≡ 16 (mod 119)

सिफरटेक्स्ट

c = 16

उत्तर

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

उत्तर: C · लगभग log₂ n

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

n से 1 तक आधा करते जाने में लगभग log₂ n स्तर लगते हैं, और हर स्तर O(n) मर्जिंग कार्य करता है, जिससे O(n log n) मिलता है।

उत्तर

C · लगभग log₂ n
10.एल्गोरिदम और जटिलता

उत्तर: D · W एक संख्या है, इसलिए समय W को लिखने में प्रयुक्त बिट्स की संख्या में घातांकी है

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

रनिंग टाइम W के मान में बहुपद है लेकिन उसकी लंबाई (log W बिट्स) में घातांकी है; 0/1 नैपसैक NP-complete है।

उत्तर

D · W एक संख्या है, इसलिए समय W को लिखने में प्रयुक्त बिट्स की संख्या में घातांकी है
11.डेटा संरचनाएँ

उत्तर: C · 1 2 4 5 3

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

प्रीऑर्डर 1, फिर उसका बायाँ सबट्री (2, 4, 5), फिर 3 देखता है; अन्य विकल्प इनऑर्डर, पोस्टऑर्डर और लेवल-ऑर्डर हैं।

उत्तर

C · 1 2 4 5 3
12.डेटा संरचनाएँ

उत्तर: C · किसी नोड से उसकी वंशज पत्तियों तक के हर पथ में काले नोड्स की संख्या समान होती है

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

रेड-ब्लैक नियम: नोड लाल या काले होते हैं, रूट काला होता है, लाल नोड्स के चाइल्ड काले होते हैं, और सभी पथों की ब्लैक-हाइट समान होती है, जिससे ऊँचाई ≤ 2 log₂(n + 1) रहती है।

उत्तर

C · किसी नोड से उसकी वंशज पत्तियों तक के हर पथ में काले नोड्स की संख्या समान होती है
13.ग्राफ़ सिद्धांत

उत्तर: H = 12

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

गिनें

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

उत्तर

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

उत्तर: कोर AC

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

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

1. CE (1)
2. AC (3)
3. DE (5)
4. GC (6)
5. AB (7)
6. EF (14)

कोर संख्या 2

AC

उत्तर

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

उत्तर: B · जब सबक्वेरी कम से कम एक पंक्ति लौटाए

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

EXISTS केवल जाँचता है कि कोई पंक्ति बनती है या नहीं; NOT EXISTS तब सत्य होता है जब सबक्वेरी कोई पंक्ति नहीं लौटाती।

उत्तर

B · जब सबक्वेरी कम से कम एक पंक्ति लौटाए
16.डेटाबेस और SQL

उत्तर: A · जब उसका प्रभाव उन्हीं ट्रांज़ैक्शनों के किसी क्रमिक (serial) निष्पादन के समतुल्य हो

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

सीरियलाइज़ेबिलिटी समवर्तिता के लिए मुख्य शुद्धता मानदंड है: अंतर्गुंथित परिणाम किसी एक-एक करके चलने वाले क्रम के परिणाम के बराबर होना चाहिए।

उत्तर

A · जब उसका प्रभाव उन्हीं ट्रांज़ैक्शनों के किसी क्रमिक (serial) निष्पादन के समतुल्य हो
17.कंप्यूटर नेटवर्क

उत्तर: A · 192.168.0.0/16

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

निजी सीमाएँ 10.0.0.0/8, 172.16.0.0/12 और 192.168.0.0/16 हैं; इन्हें सार्वजनिक इंटरनेट पर रूट नहीं किया जाता।

उत्तर

A · 192.168.0.0/16
18.कंप्यूटर नेटवर्क

उत्तर: A · 16-बिट विंडो फ़ील्ड विंडो को 65,535 बाइट तक सीमित करता है, जो तेज़ लंबी दूरी के मार्गों के लिए बहुत छोटा है

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

मूल हेडर अधिकतम 65,535 बाइट के बिना पावती वाले डेटा की अनुमति देता है। विंडो स्केलिंग इसे दो की घात से गुणा करती है ताकि उच्च बैंडविड्थ-विलंब वाले मार्ग भरे जा सकें।

उत्तर

A · 16-बिट विंडो फ़ील्ड विंडो को 65,535 बाइट तक सीमित करता है, जो तेज़ लंबी दूरी के मार्गों के लिए बहुत छोटा है
19.IPv4 सबनेटिंग

उत्तर: H = 2

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

उपसर्ग लंबाई

255.255.255.252 = /30

उपयोगी होस्ट

22 − 2 = 2

उत्तर

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

उत्तर: p = 22

रूट सारांशीकरण: सारांश रूट a.b.c.0/p उन सभी नेटवर्कों को कवर करता है जिनके पहले p बिट मेल खाते हैं। पहले और अंतिम नेटवर्क के भिन्न ऑक्टेट को बाइनरी में लिखें; साझा अग्रणी बिटों की संख्या, उससे पहले के ऑक्टेटों के बिट जोड़कर, सबसे लंबा सारांश उपसर्ग है।

बिटों की तुलना करें

48 = 00110000
50 = 00110010
साझा अग्रणी बिट: 6

उपसर्ग लंबाई

p = 16 + 6 = 22

उत्तर

p = /22

सारांश रूट: 10.184.48.0/22 (यह 1 ऐसे नेटवर्क भी कवर करता है जो सूची में नहीं हैं)।

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