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

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

N = −218 bit
U =
2.संख्या पद्धतियाँकठिन
24 बिट, चिह्नरहित, N = ?????????????????????????

24 बिटों में समाने वाला सबसे बड़ा अचिह्नित पूर्णांक N क्या है?

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

आप (r ∨ p) → ¬q को विरोधाभास द्वारा सिद्ध करना चाहते हैं। शुरू में कौन-सा कथन मानेंगे? उस पर क्लिक करें।

(r ∨ p) → ¬q
  1. 1¬(r ∨ p) ∧ ¬q
  2. 2(r ∨ p) ∧ ¬¬q
  3. 3¬(r ∨ p) → ¬¬q
  4. 4¬(r ∨ p) ∧ ¬¬q
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-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABC00011110010001131204151716

F(A, B, C) = Σm(2, 3, 5, 6, 7) का न्यूनतम योगों का गुणनफल (POS) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कितने योग पद (गुणक) N हैं?

F(A, B, C) = Σm(2, 3, 5, 6, 7)
N =
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
ABCD000111100001111010X1030214150716112X131150141819111110

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

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

53x ≡ 54 (mod 89) हल करें। हल x दें, जहाँ 0 < x < 89।

53x ≡ 54 (mod 89)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
520c = me​ mod n?m = cd​ mod nm(n, e) = (1517, 17)d

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

n = 1517e = 17m = 520
c =
9.एल्गोरिदम और जटिलतामध्यम

आप n तत्वों का ऐरे एक बार सॉर्ट करते हैं और फिर बाइनरी सर्च से k सदस्यता प्रश्नों के उत्तर देते हैं। कुल लागत क्या है?

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

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

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

चलता हुआ प्रोग्राम सक्रिय फ़ंक्शन कॉल और उनके स्थानीय वेरिएबल का हिसाब रखने के लिए कौन-सी डेटा संरचना उपयोग करता है?

  1. Aफ़्रेमों का बाइनरी सर्च ट्री
  2. Bफ़ंक्शनों की हैश टेबल
  3. Cकॉल स्टैक
  4. Dहीप मेमोरी क्यू
12.डेटा संरचनाएँकठिन

हैश टेबल के सही काम करने के लिए हैश और समानता (equality) को कौन-सा नियम मानना चाहिए?

  1. Aसमान हैश मानों का अर्थ है समान कुंजियाँ
  2. Bअलग कुंजियों के हैश मान अलग होने चाहिए
  3. Cसमान कुंजियों के हैश मान समान होने चाहिए
  4. Dहैश मान अभाज्य संख्याएँ होने चाहिए
13.ग्राफ़ सिद्धांतमध्यम
ABCDEFGयूलर परिपथयूलर पथ, परिपथ नहींदोनों में से कुछ नहीं

क्या संबद्ध ग्राफ़ में यूलर परिपथ है, परिपथ न होने वाला यूलर पथ है, या दोनों में से कुछ नहीं? अपना उत्तर क्लिक करें।

|V| = 7|E| = 9
  1. 1यूलर परिपथ
  2. 2यूलर पथ, परिपथ नहीं
  3. 3दोनों में से कुछ नहीं
14.ग्राफ़ सिद्धांतकठिन
1126161044ABCDEF

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

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

GRANT SELECT ON employees TO alice क्या करता है?

  1. Aउपयोगकर्ता alice को employees टेबल पढ़ने की अनुमति देता है
  2. Balice को डेटाबेस का स्वामी बनाता है
  3. Cemployees टेबल को alice तक कॉपी करता है
  4. Dalice को employees टेबल की पंक्तियाँ अपडेट और हटाने की अनुमति देता है
16.डेटाबेस और SQLकठिन

टेबल b के कॉलम y में मान 1, 2 और NULL हैं। SELECT * FROM a WHERE x NOT IN (SELECT y FROM b) क्या लौटाता है?

  1. Aa की केवल वे पंक्तियाँ जहाँ x NULL है
  2. Bकोई पंक्ति नहीं
  3. Ca की वे पंक्तियाँ जहाँ x, 1 या 2 नहीं है
  4. Da की हर पंक्ति
17.कंप्यूटर नेटवर्कमध्यम

एक /26 IPv4 सबनेट में कितने उपयोग योग्य होस्ट पते होते हैं?

  1. A62
  2. B30
  3. C126
  4. D64
18.कंप्यूटर नेटवर्ककठिन

एक छात्र होम NAT राउटर के पीछे एक PC पर गेम सर्वर चलाता है। इंटरनेट पर दोस्त कनेक्ट नहीं कर पाते। सामान्य समाधान क्या है?

  1. APC का सबनेट मास्क /32 करना
  2. BPC को अलग MAC पता देना ताकि राउटर उसे बाहर से खोज सके
  3. CPC का DNS क्लाइंट बंद करना
  4. Dराउटर पर PC के निजी पते के लिए पोर्ट फ़ॉरवर्डिंग कॉन्फ़िगर करना
19.IPv4 सबनेटिंगमध्यम
/24 → /2811111111111111111111111111110000नेटवर्क बिटहोस्ट बिट

नेटवर्क 192.168.170.0/24 को /28 सबनेटों में बाँटा गया है, जिन्हें सबसे निचले पते से 1, 2, 3, … क्रमांकित किया गया है (सबनेट 1 .0 से शुरू होता है)। सबनेट 2 के नेटवर्क पते का चौथा ऑक्टेट x क्या है?

192.168.170.0/24/28सबनेट 2 (सबनेट 1 .0 से शुरू होता है)
x =
20.IPv4 सबनेटिंगकठिन
अंतिम ऑक्टेट = 205112816403201618140211नेटवर्कहोस्ट

एक होस्ट का पता 10.20.39.205/25 है। उसके सबनेट के अंतिम उपयोगी होस्ट पते का चौथा ऑक्टेट x क्या है?

10.20.39.205/25
x =

3विलयन

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

उत्तर: U = 235

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

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

21 = 0001 0101
उलटा हुआ: 1110 1010
+1 → 1110 1011

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

1110 1011₂ = 256 − 21 = 235

उत्तर

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

उत्तर: N = 1.678 × 10⁷

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

सबसे बड़ा मान

224 − 1 = 16777215

उत्तर

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

उत्तर: (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 = r ∨ p, b = ¬q

निहितार्थ का निषेध

¬(a → b) ≡ a ∧ ¬b = (r ∨ p) ∧ ¬¬q

उत्तर

(r ∨ p) ∧ ¬¬q

यदि मान्यता विरोधाभास की ओर ले जाए, तो निहितार्थ सत्य होना चाहिए।

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-मानचित्र और फ़्लिप-फ़्लॉप

उत्तर: N = 2

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

ABC00011110010001131204151716

0 को समूहित करें

हर समूह 2ᵏ खानों का आयत होता है; किनारे के खाने विपरीत किनारे के खानों के पड़ोसी होते हैं।

(B + C)
(A + B)

न्यूनतम POS रूप

F = (B + C)(A + B)
N = 2

उत्तर

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

उत्तर: N = 4

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

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

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

C′, AD, AB′, A′BD′
ABCD000111100001111010X1030214150716112X131150141819111110

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

C′, AD, AB′, A′BD′
N = 4

उत्तर

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

उत्तर: x = 43

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

53 का प्रतिलोम

r = 89, t = 0
r = 53, q = 1, t = 1
r = 36, q = 1, t = −1
r = 17, q = 2, t = 2
r = 2, q = 8, t = −5
r = 1, q = 2, t = 42
53−1 ≡ 42 (mod 89)

हल करें

x ≡ 42·54 = 2268 ≡ 43 (mod 89)
जाँच: 53·43 = 2279 ≡ 54 (mod 89)

उत्तर

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

उत्तर: c = 832

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

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

17 = 16 + 1
5201 ≡ 520 (mod 1517)
5202 ≡ 374 (mod 1517)
5204 ≡ 312 (mod 1517)
5208 ≡ 256 (mod 1517)
52016 ≡ 305 (mod 1517)
52017 ≡ 520·305 ≡ 832 (mod 1517)

सिफरटेक्स्ट

c = 832

उत्तर

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

उत्तर: D · O(n log n + k log n)

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

सॉर्टिंग में O(n log n) और हर प्रश्न में O(log n) लगता है; जब k बड़ा हो तो यह k रैखिक स्कैन (O(nk)) से बेहतर है।

उत्तर

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

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

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

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

उत्तर

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

उत्तर: C · कॉल स्टैक

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

हर कॉल एक स्टैक फ़्रेम push करती है और हर return उसे pop करता है, इसीलिए सबसे हाल की कॉल पहले समाप्त होती है।

उत्तर

C · कॉल स्टैक
12.डेटा संरचनाएँ

उत्तर: C · समान कुंजियों के हैश मान समान होने चाहिए

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

यदि दो समान कुंजियों के हैश अलग हों, तो वे अलग बकेटों में संग्रहीत होंगी और खोज विफल होगी; असमान कुंजियाँ फिर भी एक हैश साझा कर सकती हैं।

उत्तर

C · समान कुंजियों के हैश मान समान होने चाहिए
13.ग्राफ़ सिद्धांत

उत्तर: दोनों में से कुछ नहीं

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

घात

deg(A) = 1, deg(B) = 2, deg(C) = 3, deg(D) = 3, deg(E) = 4, deg(F) = 2, deg(G) = 3

विषम शीर्ष

A, C, D, G → 4
दोनों में से कुछ नहीं

उत्तर

दोनों में से कुछ नहीं
14.ग्राफ़ सिद्धांत

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

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

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

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

A (0): B: 1, C: 12
B (1): C: 7, E: 5
E (5): C: 6, D: 11, F: 9
C (6)
F (9)
D (11)

सबसे छोटा पथ

A → B → E → F
d(F) = 9

उत्तर

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

उत्तर: A · उपयोगकर्ता alice को employees टेबल पढ़ने की अनुमति देता है

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

GRANT किसी ऑब्जेक्ट पर विशेषाधिकार देता है; SELECT केवल पढ़ने की अनुमति देता है, जबकि INSERT, UPDATE और DELETE अलग विशेषाधिकार हैं।

उत्तर

A · उपयोगकर्ता alice को employees टेबल पढ़ने की अनुमति देता है
16.डेटाबेस और SQL

उत्तर: B · कोई पंक्ति नहीं

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

NULL से तुलना UNKNOWN है, इसलिए पूरी शर्त कभी TRUE नहीं होती; NOT EXISTS या NULL को छानकर हटाना इस जाल से बचाता है।

उत्तर

B · कोई पंक्ति नहीं
17.कंप्यूटर नेटवर्क

उत्तर: A · 62

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

/26 में 6 होस्ट बिट होते हैं: 2⁶ = 64 पते, नेटवर्क और ब्रॉडकास्ट पते घटाने पर 62 उपयोग योग्य होस्ट।

उत्तर

A · 62
18.कंप्यूटर नेटवर्क

उत्तर: D · राउटर पर PC के निजी पते के लिए पोर्ट फ़ॉरवर्डिंग कॉन्फ़िगर करना

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

NAT केवल भीतर से शुरू किए गए कनेक्शनों के लिए मैपिंग बनाता है। पोर्ट-फ़ॉरवर्डिंग नियम एक सार्वजनिक पोर्ट को आंतरिक होस्ट से जोड़ता है ताकि आने वाले कनेक्शन उस तक पहुँच सकें।

उत्तर

D · राउटर पर PC के निजी पते के लिए पोर्ट फ़ॉरवर्डिंग कॉन्फ़िगर करना
19.IPv4 सबनेटिंग

उत्तर: x = 16

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

ब्लॉक आकार

24 = 16

सबनेट संख्या 2

नेटवर्क: (2 − 1)·16 = 16
ब्रॉडकास्ट: 16 + 16 − 1 = 31

उत्तर

x = 16
20.IPv4 सबनेटिंग

उत्तर: x = 254

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

ब्लॉक आकार

27 = 128

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

नेटवर्क: ⌊205/128⌋·128 = 128
ब्रॉडकास्ट: 128 + 128 − 1 = 255
उपयोगी होस्ट: 129 … 254

उत्तर

x = 254

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