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

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

N = −688 bit
U =
2.संख्या पद्धतियाँकठिन
16 bit1 px1920 px1080 pxM = ? KiB

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

1920 × 1080 px16 bit/px1 KiB = 1024 B
M = KiB
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
पुनरुक्तिविरोधोक्तिआपातिक कथन

क्या (b ∧ (b → a)) → a पुनरुक्ति, विरोधोक्ति या आपातिक कथन है? अपना उत्तर क्लिक करें।

(b ∧ (b → a)) → a
  1. 1पुनरुक्ति
  2. 2विरोधोक्ति
  3. 3आपातिक कथन
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन

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

(¬p ∧ (r ∧ s)) → (s ↔ ¬q)
N =
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABCD00011110000111101111111

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

F = Σm(1, 3, 4, 5, 6, 7, 10)
  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-मानचित्र और फ़्लिप-फ़्लॉपकठिन
ABCD000111100001111010110312040507161121131150141819X11X10

F(A, B, C, D) = Σm(0, 1, 2, 6, 8, 9, 12, 13, 15) + d(10, 11) के लिए, जहाँ d डोंट-केयर स्थितियों को दर्शाता है, अनिवार्य प्रमुख प्रभाव्यों (एसेंशियल प्राइम इम्प्लिकेंट) की संख्या N ज्ञात करें।

F(A, B, C, D) = Σm(0, 1, 2, 6, 8, 9, 12, 13, 15) + d(10, 11)
N =
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

59 के मापांक में 51 का प्रतिलोम ज्ञात करें: वह संख्या x जिसके लिए 0 < x < 59 और 51·x ≡ 1 (mod 59)।

a = 51n = 59
51−1 mod 59 =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
mc = me​ mod ncm = cd​ mod nm(n, e) = (217, 23)d = ?

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

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

for i = 1 to n: (j = 1; while j < n: j = j × 2) — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

स्ट्रासेन का एल्गोरिदम आधे आकार के ब्लॉकों के 8 के बजाय 7 रिकर्सिव गुणनों से मैट्रिक्स गुणा करता है। इसका रनिंग टाइम क्या है?

  1. AΘ(n2)
  2. BΘ(n³)
  3. CΘ(n² log n)
  4. DΘ(nlog₂ 7), लगभग n2.81
11.डेटा संरचनाएँमध्यम

लिंक्ड लिस्ट में सेंटिनल (डमी) नोड का उद्देश्य क्या है?

  1. Aतत्वों की संख्या संग्रहीत करना
  2. Bलिस्ट को नोडों की एक निश्चित अधिकतम संख्या से आगे बढ़ने से रोकना
  3. Cलिस्ट को सॉर्टेड बनाना
  4. Dहेड या टेल पर विशेष मामलों को हटाकर कोड को सरल बनाना
12.डेटा संरचनाएँकठिन

एक ऑब्जेक्ट हैश मैप में कुंजी के रूप में संग्रहीत है, और फिर उसके हैश फ़ंक्शन में प्रयुक्त एक फ़ील्ड बदल दिया जाता है। संभावित परिणाम क्या है?

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

एक संबद्ध ग्राफ़ में 12 शीर्ष और 21 कोरें हैं। स्पैनिंग ट्री बचाने के लिए कितनी कोरें k हटानी होंगी?

|V| = 12|E| = 21
k =
14.ग्राफ़ सिद्धांतकठिन
77228334ABCDEF

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

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

डेटाबेस ट्रिगर क्या है?

  1. Aऐसा कोड जो किसी टेबल पर INSERT, UPDATE या DELETE जैसी निर्दिष्ट घटना होने पर स्वतः चलता है
  2. Bडेटाबेस का निर्धारित बैकअप
  3. Cखोज तेज़ करने वाला एक प्रकार का इंडेक्स
  4. Dऐसी क्वेरी जिसे उपयोगकर्ता हाथ से चलाता है
16.डेटाबेस और SQLकठिन

ऑन-कॉल दो डॉक्टर दोनों जाँचते हैं कि दूसरा अभी भी ऑन-कॉल है, फिर दोनों एक ही समय पर साइन-ऑफ़ करते हैं। स्नैपशॉट आइसोलेशन यहाँ अब भी कौन-सी विसंगति होने दे सकता है?

  1. Aडर्टी रीड
  2. Bएक ट्रांज़ैक्शन के भीतर नॉन-रिपीटेबल रीड
  3. Cडर्टी राइट
  4. Dराइट स्क्यू (write skew)
17.कंप्यूटर नेटवर्कमध्यम

क्लासिक साझा (हाफ़-डुप्लेक्स) Ethernet किस माध्यम अभिगम (medium access) विधि का उपयोग करता था?

  1. Aटोकन पासिंग
  2. BCSMA/CD
  3. CCSMA/CA
  4. DTDMA
18.कंप्यूटर नेटवर्ककठिन

TCP कंजेशन कंट्रोल का "slow start" चरण:

  1. Aपैकेट हानि का पता चलने तक हर राउंड ट्रिप में कंजेशन विंडो को आधा कर देता है
  2. Bकेवल UDP द्वारा उपयोग किया जाता है
  3. Cसीमा (threshold) या हानि होने तक कंजेशन विंडो को घातांकीय रूप से बढ़ाता है
  4. Dविंडो को एक सेगमेंट पर स्थिर रखता है
19.IPv4 सबनेटिंगमध्यम
255.255.255.12811111111111111111111111110000000नेटवर्क बिटहोस्ट बिट

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

255.255.255.128
H =
20.IPv4 सबनेटिंगकठिन

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

A: 65B: 35C: 11D: 24
x =

3विलयन

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

उत्तर: U = 188

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

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

68 = 0100 0100
उलटा हुआ: 1011 1011
+1 → 1011 1100

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

1011 1100₂ = 256 − 68 = 188

उत्तर

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

उत्तर: M = 4050 KiB

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

बिट और बाइट

1920·1080·16 = 33177600 bit = 4147200 B

KiB में बदलें

4147200/1024 = 4050 KiB

उत्तर

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

उत्तर: पुनरुक्ति

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

वर्गीकृत करें

(b ∧ (b → a)) → a: 1, 1, 1, 1
हर पंक्ति में 1: पुनरुक्ति।

उत्तर

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

उत्तर: N = 15

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

स्तंभ

¬p; r ∧ s; ¬p ∧ (r ∧ s); ¬q; s ↔ ¬q; (¬p ∧ (r ∧ s)) → (s ↔ ¬q)

p पर बाँटें

p = 1: 8
p = 0: 7
N = 8 + 7 = 15

उत्तर

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

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

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

हर 1 के पड़ोसी

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

m10: m11, m8, m14, m2 → 0
ABCD00011110000111101111111

अकेला 1

m10 = AB′CD′ → AB = 10, CD = 10

उत्तर

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

उत्तर: N = 4

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

प्रमुख प्रभाव्य

1 और X से बनने वाले सबसे बड़े समूह।

B′D′, B′C′, AD, AC′, A′CD′, AB′
ABCD000111100001111010110312040507161121131150141819X11X10

अनिवार्य प्रमुख प्रभाव्य

B′C′, AD, AC′, A′CD′
N = 4

उत्तर

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

उत्तर: 51−1 mod 59 = 22

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

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

हर शेषफल r को r ≡ t·51 (mod 59) के रूप में लिखा जाता है।

r = 59, t = 0
r = 51, q = 1, t = 1
r = 8, q = 6, t = −1
r = 3, q = 2, t = 7
r = 2, q = 1, t = −15
r = 1, q = 2, t = 22

व्युत्क्रम

1 ≡ 22·51 (mod 59)
x = 22
जाँच: 51·22 = 1122 = 19·59 + 1

उत्तर

51−1 mod 59 = 22
8.संख्या सिद्धांत और मॉड्यूलर अंकगणित

उत्तर: d = 47

मॉड्यूलर घात और 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·31 = 217
φ(n) = 6·30 = 180

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

r = 180, t = 0
r = 23, q = 7, t = 1
r = 19, q = 1, t = −7
r = 4, q = 4, t = 8
r = 3, q = 1, t = −39
r = 1, q = 3, t = 47

निजी घातांक

d = 47
जाँच: 23·47 = 1081 = 6·180 + 1

उत्तर

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

उत्तर: C · O(n log n)

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

n बाहरी इटरेशन में से हर एक के लिए भीतरी लूप लगभग log₂ n बार चलता है, जिससे O(n log n) मिलता है।

उत्तर

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

उत्तर: D · Θ(nlog₂ 7), लगभग n2.81

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

a = 7 और b = 2 के साथ nlog₂ 7, O(n²) जोड़ कार्य पर प्रभावी होता है, जिससे लगभग n2.81 मिलता है।

उत्तर

D · Θ(nlog₂ 7), लगभग n2.81
11.डेटा संरचनाएँ

उत्तर: D · हेड या टेल पर विशेष मामलों को हटाकर कोड को सरल बनाना

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

सेंटिनल के साथ हर वास्तविक नोड का एक पूर्ववर्ती होता है, इसलिए हेड पर डालने या हटाने के लिए विशेष व्यवहार की आवश्यकता नहीं होती।

उत्तर

D · हेड या टेल पर विशेष मामलों को हटाकर कोड को सरल बनाना
12.डेटा संरचनाएँ

उत्तर: C · ऑब्जेक्ट को खोजना विफल हो सकता है क्योंकि वह अपने पुराने हैश वाले बकेट में है

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

कुंजी का स्थान उसके पुराने हैश से चुना गया था; नए हैश से खोज ग़लत बकेट में होती है, इसलिए कुंजियाँ अपरिवर्तनीय (immutable) होनी चाहिए।

उत्तर

C · ऑब्जेक्ट को खोजना विफल हो सकता है क्योंकि वह अपने पुराने हैश वाले बकेट में है
13.ग्राफ़ सिद्धांत

उत्तर: k = 10

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

स्पैनिंग ट्री की कोरें

12 − 1 = 11

हटाई जाने वाली कोरें

k = 21 − 11 = 10

उत्तर

k = 10
14.ग्राफ़ सिद्धांत

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

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

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

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

A (0): B: 7, C: 7
B (7): D: 9, E: 11
C (7)
D (9)
E (11): F: 14
F (14)

सबसे छोटा पथ

A → B → D
d(D) = 9

उत्तर

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

उत्तर: A · ऐसा कोड जो किसी टेबल पर INSERT, UPDATE या DELETE जैसी निर्दिष्ट घटना होने पर स्वतः चलता है

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

ट्रिगर डेटा परिवर्तन से पहले या बाद में स्वतः निष्पादित होते हैं, उदाहरण के लिए ऑडिट लॉग लिखने या जटिल नियम लागू करने के लिए।

उत्तर

A · ऐसा कोड जो किसी टेबल पर INSERT, UPDATE या DELETE जैसी निर्दिष्ट घटना होने पर स्वतः चलता है
16.डेटाबेस और SQL

उत्तर: D · राइट स्क्यू (write skew)

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

स्नैपशॉट आइसोलेशन में दोनों ट्रांज़ैक्शन पुरानी स्थिति देखते हैं और अलग-अलग पंक्तियाँ बदलते हैं, इसलिए कोई लेखन संघर्ष नहीं पकड़ा जाता; serializable आइसोलेशन इसे रोकता है।

उत्तर

D · राइट स्क्यू (write skew)
17.कंप्यूटर नेटवर्क

उत्तर: B · CSMA/CD

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

Carrier sense multiple access with collision detection: टकराव का पता लगने पर स्टेशन रुक जाते हैं और एक यादृच्छिक बैकऑफ़ के बाद पुनः प्रयास करते हैं। फ़ुल-डुप्लेक्स स्विच्ड Ethernet में कोई टकराव नहीं होता।

उत्तर

B · CSMA/CD
18.कंप्यूटर नेटवर्क

उत्तर: C · सीमा (threshold) या हानि होने तक कंजेशन विंडो को घातांकीय रूप से बढ़ाता है

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

Slow start कंजेशन विंडो को घातांकीय रूप से बढ़ाता है; सीमा के बाद congestion avoidance इसे रैखिक रूप से बढ़ाता है, और हानि होने पर यह घटती है।

उत्तर

C · सीमा (threshold) या हानि होने तक कंजेशन विंडो को घातांकीय रूप से बढ़ाता है
19.IPv4 सबनेटिंग

उत्तर: H = 126

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.128 = /25

उपयोगी होस्ट

27 − 2 = 126

उत्तर

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

उत्तर: x = 128

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

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

A: 65 होस्ट → 27 = 128 (/25)
B: 35 होस्ट → 26 = 64 (/26)
D: 24 होस्ट → 25 = 32 (/27)
C: 11 होस्ट → 24 = 16 (/28)

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

A: .0 – .127
B: .128 – .191
D: .192 – .223
C: .224 – .239

उत्तर

x = 128

LAN B: 192.168.76.128/26।

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