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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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−12816413201618140211

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

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

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

32 bit
N =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
(p ∨ r) ∧ (p ∨ q)(p ∨ r) ∧ qp ∧ (r ∨ q)(p ∧ r) ∨ (p ∧ q)

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

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

निषेध को पूरी तरह भीतर ले जाने पर कौन-सा कथन ¬∀x ∀y (R(x, y) → R(y, x)) के तुल्य है? उस पर क्लिक करें।

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

F = A′B′ + A′C′ + AB′C को उसके न्यूनतम गुणनफलों के योग रूप में सरल करें। सरल किए गए व्यंजक में कितने लिटरल L हैं?

F = A′B′ + A′C′ + AB′C
L =
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
CLKJK1234567

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

Q₀ = 0JK
  1. 1क्लॉक कोर 1
  2. 2क्लॉक कोर 2
  3. 3क्लॉक कोर 3
  4. 4क्लॉक कोर 4
  5. 5क्लॉक कोर 5
  6. 6क्लॉक कोर 6
  7. 7क्लॉक कोर 7
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

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

a = 95n = 97
95−1 mod 97 =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
38c = me​ mod n?m = cd​ mod nm(n, e) = (629, 11)d

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

n = 629e = 11m = 38
c =
9.एल्गोरिदम और जटिलतामध्यम

रिकरेंस T(n) = T(n − 1) + O(n) का हल क्या है?

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

little-o नोटेशन के बारे में कौन-सा कथन सही है?

  1. An² = o(n)
  2. Bn = o(n), क्योंकि हर फलन स्वयं का little-o है
  3. Cn = o(n²), पर n, o(n) नहीं है
  4. D2n = o(n), क्योंकि 2n धीरे बढ़ता है
11.डेटा संरचनाएँमध्यम

संतुलित बाइनरी सर्च ट्री में किसी कुंजी को खोजने की समय जटिलता क्या है?

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

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

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

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

|V| = 13|E| = 20
k =
14.ग्राफ़ सिद्धांतकठिन
ABCDE

लंबाई 2 की कितनी बंद वॉक D से शुरू और समाप्त होती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।

M = संलग्नता आव्यूहL = 2
N =
15.डेटाबेस और SQLमध्यम

ROLLBACK TO SAVEPOINT s1 क्या करता है?

  1. Asavepoint s1 के बाद किए गए परिवर्तन पूर्ववत करता है, ट्रांज़ैक्शन खुला रखते हुए
  2. Bsavepoint और तब से बदली गई सभी टेबलें हटा देता है
  3. Cट्रांज़ैक्शन समाप्त करता है और सब कुछ कमिट करता है
  4. Dपूरे ट्रांज़ैक्शन को शुरुआत से पूर्ववत करता है
16.डेटाबेस और SQLकठिन

SELECT name, dept, AVG(salary) OVER (PARTITION BY dept) FROM emp क्या लौटाता है?

  1. Aएक त्रुटि क्योंकि name, GROUP BY में नहीं है
  2. Bकेवल वे कर्मचारी जो अपने विभाग के औसत से अधिक कमाते हैं
  3. Cहर कर्मचारी पंक्ति, उसके विभाग के औसत salary के साथ
  4. Dप्रति विभाग एक पंक्ति, उसके औसत salary के साथ
17.कंप्यूटर नेटवर्कमध्यम

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

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

SYN flood हमले में हमलावर किस संसाधन को समाप्त करने की कोशिश करता है?

  1. Aस्विच की MAC पता तालिका
  2. Bक्लाइंट का DNS कैश
  3. Cसर्वर की अर्ध-खुले (half-open) कनेक्शनों की तालिका
  4. Dसर्वर का डिस्क स्थान
19.IPv4 सबनेटिंगमध्यम
/22 → /2911111111111111111111111111111000नेटवर्क बिटहोस्ट बिट

नेटवर्क 10.65.104.0/22 को उपसर्ग /29 वाले समान सबनेट में बाँटा गया है। कितने सबनेट N हैं?

10.65.104.0/22/29
N =
20.IPv4 सबनेटिंगकठिन
अंतिम ऑक्टेट = 77012816403201618140211नेटवर्कहोस्ट

एक होस्ट का पता 10.20.36.77/29 है। उसके सबनेट के ब्रॉडकास्ट पते की अंतिम संख्या (चौथा ऑक्टेट) x क्या है?

10.20.36.77/29
x =

3विलयन

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

उत्तर: N = −19

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

मान जोड़ें

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

−128 + 64 + 32 + 8 + 4 + 1 = −19

उत्तर

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

उत्तर: N = −2.147 × 10⁹

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

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

−231 = −2147483648

उत्तर

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

उत्तर: (p ∨ r) ∧ (p ∨ q)

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

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

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

उत्तर

(p ∨ r) ∧ (p ∨ q)

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

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

उत्तर: ∃x ∃y (R(x, y) ∧ ¬R(y, x))

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

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

¬∀x ∀y (R(x, y) → R(y, x)) ≡ ∃x ∃y (R(x, y) ∧ ¬R(y, x))

उत्तर

∃x ∃y (R(x, y) ∧ ¬R(y, x))

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

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

उत्तर: L = 4

बूलीय बीजगणित: व्यंजकों को सरल करने वाले नियम हैं X + X′ = 1 और X·X′ = 0, X + X = X, अवशोषण X + X·Y = X, संयोजन नियम X·Y + X·Y′ = X, X + X′Y = X + Y और सहमति प्रमेय XY + X′Z + YZ = XY + X′Z। डी मॉर्गन के नियम (X·Y)′ को X′ + Y′ में और (X + Y)′ को X′·Y′ में बदलते हैं। कार्नो मानचित्र इन नियमों को चित्रात्मक रूप से लगाता है: दो पड़ोसी खानों का हर समूह XY + XY′ = X का एक उपयोग है।

व्यंजक के मिनटर्म

A′B′ → m(0, 1)
A′C′ → m(0, 2)
AB′C → m(5)
ABC00011110011011031204150706

समूहित करें और पढ़ें

F = B′C + A′C′

लिटरल गिनें

L = 4

उत्तर

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

उत्तर: क्लॉक कोर 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।

हर कोर के बाद Q

JK फ़्लिप-फ़्लॉप: 00 स्थिर रखता है, 01 रीसेट करता है (Q = 0), 10 सेट करता है (Q = 1), 11 टॉगल करता है।

1: J = 0, K = 1 → Q = 0
2: J = 0, K = 0 → Q = 0
3: J = 0, K = 1 → Q = 0
4: J = 1, K = 0 → Q = 1
5: J = 1, K = 1 → Q = 0
6: J = 0, K = 0 → Q = 0
7: J = 0, K = 1 → Q = 0

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

क्लॉक कोर 5

उत्तर

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

उत्तर: 95−1 mod 97 = 48

प्रतिलोम और सर्वांगसमताएँ: 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·95 (mod 97) के रूप में लिखा जाता है।

r = 97, t = 0
r = 95, q = 1, t = 1
r = 2, q = 47, t = −1
r = 1, q = 2, t = 48

व्युत्क्रम

1 ≡ 48·95 (mod 97)
x = 48
जाँच: 95·48 = 4560 = 47·97 + 1

उत्तर

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

उत्तर: c = 149

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

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

11 = 8 + 2 + 1
381 ≡ 38 (mod 629)
382 ≡ 186 (mod 629)
384 ≡ 1 (mod 629)
388 ≡ 1 (mod 629)
3811 ≡ 38·186·1 ≡ 149 (mod 629)

सिफरटेक्स्ट

c = 149

उत्तर

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

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

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

कार्य का योग लगभग n² / 2 होता है; यह सिलेक्शन सॉर्ट का या सबसे ख़राब पिवट वाले क्विकसॉर्ट का रिकरेंस है।

उत्तर

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

उत्तर: C · n = o(n²), पर n, o(n) नहीं है

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

f = o(g) का अर्थ है कि f(n) / g(n), 0 की ओर जाता है; n / n², 0 की ओर जाता है, पर n / n = 1 नहीं।

उत्तर

C · n = o(n²), पर n, o(n) नहीं है
11.डेटा संरचनाएँ

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

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

संतुलित ट्री की ऊँचाई लगभग log₂ n होती है, इसलिए खोज रूट से पत्ती तक एक ही पथ का अनुसरण करती है।

उत्तर

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

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

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

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

उत्तर

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

उत्तर: k = 8

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

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

13 − 1 = 12

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

k = 20 − 12 = 8

उत्तर

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

उत्तर: N = 2

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। Kn में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

संलग्नता आव्यूह

A: 0 1 1 0 0
B: 1 0 1 1 0
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 0 1 1 0

उभयनिष्ठ पड़ोसी

(M²)DD = 0·0 + 1·1 + 0·0 + 0·0 + 1·1 = 2

उत्तर

N = 2
15.डेटाबेस और SQL

उत्तर: A · savepoint s1 के बाद किए गए परिवर्तन पूर्ववत करता है, ट्रांज़ैक्शन खुला रखते हुए

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

savepoint ट्रांज़ैक्शन के भीतर एक बिंदु चिह्नित करता है; उस तक रोलबैक बाद का काम रद्द करता है जबकि पहले के परिवर्तन COMMIT तक लंबित रहते हैं।

उत्तर

A · savepoint s1 के बाद किए गए परिवर्तन पूर्ववत करता है, ट्रांज़ैक्शन खुला रखते हुए
16.डेटाबेस और SQL

उत्तर: C · हर कर्मचारी पंक्ति, उसके विभाग के औसत salary के साथ

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

GROUP BY के विपरीत, विंडो फ़ंक्शन हर इनपुट पंक्ति रखता है और उसके पार्टिशन, यहाँ विभाग, पर गणना किया गया मान जोड़ता है।

उत्तर

C · हर कर्मचारी पंक्ति, उसके विभाग के औसत salary के साथ
17.कंप्यूटर नेटवर्क

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

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

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

उत्तर

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

उत्तर: C · सर्वर की अर्ध-खुले (half-open) कनेक्शनों की तालिका

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

हर SYN सर्वर को स्थिति आरक्षित करने और ऐसे ACK की प्रतीक्षा करने पर मजबूर करता है जो कभी नहीं आता। SYN cookies हैंडशेक पूरा होने तक स्थिति संग्रहित करने से बचाती हैं।

उत्तर

C · सर्वर की अर्ध-खुले (half-open) कनेक्शनों की तालिका
19.IPv4 सबनेटिंग

उत्तर: N = 128

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

उधार लिए गए बिट

29 − 22 = 7

सबनेटों की संख्या

N = 27 = 128

उत्तर

N = 128

हर /29 सबनेट में 23 − 2 = 6 उपयोगी होस्ट हैं।

20.IPv4 सबनेटिंग

उत्तर: x = 79

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

ब्लॉक आकार

23 = 8

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

नेटवर्क: ⌊77/8⌋·8 = 72
ब्रॉडकास्ट: 72 + 8 − 1 = 79
उपयोगी होस्ट: 73 … 78

उत्तर

x = 79

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