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

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

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

1010 11118 bit
N =
2.संख्या पद्धतियाँकठिन
32 bit1 px800 px600 pxM = ? KiB

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

800 × 600 px32 bit/px1 KiB = 1024 B
M = KiB
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
¬q ∧ rq ∧ ¬r¬q → ¬rq → ¬r

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

¬(q → r)
  1. 1¬q ∧ r
  2. 2q ∧ ¬r
  3. 3¬q → ¬r
  4. 4q → ¬r
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
rp ∧ ¬r¬r¬p

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

p → rp
  1. 1r
  2. 2p ∧ ¬r
  3. 3¬r
  4. 4¬p
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
MUXC′I0​CI1​CI2​1I3​ABS1​S0​F

एक 4-से-1 मल्टीप्लेक्सर के चयन निवेश S₁ = A और S₀ = B हैं, और उसके डेटा निवेश I₀ = C′, I₁ = C, I₂ = C, I₃ = 1 से जुड़े हैं। A, B और C के 8 संयोजनों में से कितनों के लिए निर्गत F = 1 है? N ज्ञात करें।

I₀ = C′I₁ = CI₂ = CI₃ = 1
N =
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
TQ0​Q0​TQ1​Q1​TQ2​Q2​TQ3​Q3​TQ4​Q4​TQ5​Q5​TQ6​Q6​TQ7​Q7​CLK

एक 8-बिट रिपल (अतुल्यकालिक) काउंटर ऐसे फ़्लिप-फ़्लॉप से बना है जिनमें से प्रत्येक का संचरण विलंब 12 ns है। अगली क्लॉक कोर से पहले सभी निर्गत स्थिर हो जाने चाहिए। अधिकतम क्लॉक आवृत्ति fmax ज्ञात करें।

n = 8tpd = 12 ns
fmax = MHz
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

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

n = 343 = 73
φ(343) =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
mc = me​ mod ncm = cd​ mod nm(n, e) = (247, 17)d = ?

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

p = 13q = 19e = 17
d =
9.एल्गोरिदम और जटिलतामध्यम

मानक तीन लूप से दो n × n मैट्रिक्स गुणा करने की टाइम कॉम्प्लेक्सिटी क्या है?

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

यह सिद्ध करने के लिए कि कोई निर्णय समस्या X NP-complete है, कौन-सी दो बातें दिखानी होंगी?

  1. AX, P की किसी समस्या में रिड्यूस होती है, और X, NP में है
  2. BX का कोई बहुपदी एल्गोरिदम नहीं है, और X निर्णेय है
  3. CX, NP में है, और कोई ज्ञात NP-complete समस्या बहुपदी समय में X में रिड्यूस होती है
  4. DX, P में है, और X, SAT में रिड्यूस होती है
11.डेटा संरचनाएँमध्यम

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

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

बाइनरी हीप में decrease-key की समय जटिलता (तत्व की स्थिति ज्ञात होने पर) क्या है?

  1. AO(n log n)
  2. BO(log n)
  3. CO(n)
  4. DO(1)
13.ग्राफ़ सिद्धांतमध्यम

एक वृक्ष में घात 4 वाले 2 शीर्ष, घात 5 वाले 3 शीर्ष, घात 2 वाले 3 शीर्ष है, और उसके बाकी सभी शीर्ष पत्ते (घात 1) हैं। उसमें कितने पत्ते L हैं?

2 × deg 43 × deg 53 × deg 2
L =
14.ग्राफ़ सिद्धांतकठिन
1171435102141111ABCDEFG

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

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

प्रथम नॉर्मल फ़ॉर्म (1NF) की आवश्यकता क्या है?

  1. Aप्रत्येक नॉन-की कॉलम पूरी की पर निर्भर हो और की के अलावा किसी पर नहीं
  2. Bप्रत्येक कॉलम में परमाणु (atomic) मान हों और कोई दोहराए जाने वाले समूह न हों
  3. Cहर टेबल में ठीक एक कॉलम हो
  4. Dकोई फ़ॉरेन की न हो
16.डेटाबेस और SQLकठिन

एक रिपोर्टिंग डेटाबेस जॉइन से बचने के लिए ग्राहक नामों को orders टेबल में कॉपी करता है। इस डीनॉर्मलाइज़ेशन की मुख्य लागत क्या है?

  1. Aorders टेबल पर क्वेरी धीमी हो जाती हैं
  2. Bडेटाबेस अब इंडेक्स का उपयोग नहीं कर सकता
  3. Cप्राइमरी की का अब उपयोग नहीं हो सकता
  4. Dग्राहक डेटा बदलने पर अतिरिक्त प्रतियों को संगत रखना पड़ता है
17.कंप्यूटर नेटवर्कमध्यम

लाइव वीडियो कॉल के लिए अक्सर UDP को क्यों प्राथमिकता दी जाती है?

  1. Aहर खोए हुए पैकेट को दोबारा भेजने से ज़्यादा कम देरी महत्वपूर्ण है
  2. BUDP डेटा को स्वचालित रूप से एन्क्रिप्ट करता है
  3. CUDP हर पैकेट के पहुँचने की गारंटी देता है, इसलिए तस्वीर कभी नहीं रुकती
  4. Dसभी वीडियो के लिए UDP अनिवार्य है
18.कंप्यूटर नेटवर्ककठिन

एक 8-पोर्ट स्विच (बिना VLAN) के हर पोर्ट पर एक होस्ट है। कितने टकराव डोमेन और ब्रॉडकास्ट डोमेन हैं?

  1. A8 टकराव डोमेन, 1 ब्रॉडकास्ट डोमेन
  2. B8 टकराव डोमेन, 8 ब्रॉडकास्ट डोमेन
  3. C1 टकराव डोमेन, 1 ब्रॉडकास्ट डोमेन
  4. D1 टकराव डोमेन, 8 ब्रॉडकास्ट डोमेन
19.IPv4 सबनेटिंगमध्यम
255.255.252.011111111111111111111110000000000नेटवर्क बिटहोस्ट बिट

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

255.255.252.0
H =
20.IPv4 सबनेटिंगकठिन
अंतिम ऑक्टेट = 109012816413201618140211नेटवर्कहोस्ट

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

10.20.124.109/26
x =

3विलयन

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

उत्तर: N = −81

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

मान जोड़ें

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

−128 + 32 + 8 + 4 + 2 + 1 = −81

उत्तर

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

उत्तर: M = 1875 KiB

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

बिट और बाइट

800·600·32 = 15360000 bit = 1920000 B

KiB में बदलें

1920000/1024 = 1875 KiB

उत्तर

M = 1875 KiB
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) ≡ a ∧ ¬b: एकमात्र पंक्ति जहाँ निहितार्थ विफल होता है।
¬(q → r) ≡ q ∧ ¬r

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

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

उत्तर

q ∧ ¬r

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

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

उत्तर: r

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

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

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

निष्कर्ष

r (मोडस पोनेंस)

उत्तर

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

उत्तर: N = 5

मल्टीप्लेक्सर: 2ⁿ-से-1 मल्टीप्लेक्सर अपने डेटा निवेशों में से एक को निर्गत तक पहुँचाता है; चयन लाइनें, द्विआधारी संख्या के रूप में पढ़ी जाकर, तय करती हैं कि कौन-सा। चयन S₁S₀ = AB वाले 4-से-1 MUX के लिए F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃। डेटा निवेशों को 0, 1, C या C′ से जोड़ने पर MUX A, B और C का कोई भी फलन बना सकता है, जो एक ही चिप से लॉजिक बनाने का आम तरीका है।

निर्गत व्यंजक

F = A′B′C′ + A′BC + AB′C + AB

F = 1 वाली पंक्तियाँ

ABC = 000, 011, 101, 110, 111
N = 5

उत्तर

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

उत्तर: fmax = 10.42 MHz

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

सबसे खराब स्थिति का स्थिर होने का समय

T = 8·12 ns = 96 ns

अधिकतम आवृत्ति

fmax = 1/96 ns = 10.42 MHz

उत्तर

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

उत्तर: φ(343) = 294

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

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

343 = 73

टोशेंट

φ(343) = 343 − 49 = 294

उत्तर

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

उत्तर: d = 89

मॉड्यूलर घात और 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 = 13·19 = 247
φ(n) = 12·18 = 216

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

r = 216, t = 0
r = 17, q = 12, t = 1
r = 12, q = 1, t = −12
r = 5, q = 2, t = 13
r = 2, q = 2, t = −38
r = 1, q = 2, t = 89

निजी घातांक

d = 89
जाँच: 17·89 = 1513 = 7·216 + 1

उत्तर

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

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

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

n² प्रविष्टियाँ हैं और हर एक को n गुणन चाहिए, जिससे n³ ऑपरेशन होते हैं।

उत्तर

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

उत्तर: C · X, NP में है, और कोई ज्ञात NP-complete समस्या बहुपदी समय में X में रिड्यूस होती है

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

NP में सदस्यता दिखाती है कि X, NP से कठिन नहीं है; किसी ज्ञात NP-complete समस्या से रिडक्शन दिखाता है कि X कम से कम पूरे NP जितनी कठिन है।

उत्तर

C · X, NP में है, और कोई ज्ञात NP-complete समस्या बहुपदी समय में X में रिड्यूस होती है
11.डेटा संरचनाएँ

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

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

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

उत्तर

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

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

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

कुंजी घटाने के बाद तत्व अधिकतम हीप की ऊँचाई तक ऊपर खिसकता है (sift up)। फ़िबोनाची हीप O(1) परिशोधित decrease-key प्राप्त करते हैं।

उत्तर

B · O(log n)
13.ग्राफ़ सिद्धांत

उत्तर: L = 15

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

वृक्ष के लिए हैंडशेक लेमा

L + 29 = 2(L + 8) − 2
L = 15

उत्तर

L = 15

शॉर्टकट: L = 2 + Σ (d − 2), घात d ≥ 3 वाले शीर्षों पर।

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

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

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

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

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

A (0): B: 11, C: 7
C (7): G: 18
B (11): D: 14
D (14): E: 19, F: 24
G (18)
E (19): F: 21
F (21)

सबसे छोटा पथ

A → B → D → E → F
d(F) = 21

उत्तर

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

उत्तर: B · प्रत्येक कॉलम में परमाणु (atomic) मान हों और कोई दोहराए जाने वाले समूह न हों

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

1NF के लिए प्रति सेल परमाणु मान और पंक्तियों की विशिष्ट पहचान आवश्यक है, बिना दोहराए जाने वाले समूहों के।

उत्तर

B · प्रत्येक कॉलम में परमाणु (atomic) मान हों और कोई दोहराए जाने वाले समूह न हों
16.डेटाबेस और SQL

उत्तर: D · ग्राहक डेटा बदलने पर अतिरिक्त प्रतियों को संगत रखना पड़ता है

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

डीनॉर्मलाइज़ेशन पढ़ना तेज़ करता है पर अतिरेक वापस लाता है, इसलिए अपडेट को हर प्रति बदलनी होती है वरना विसंगतियाँ आती हैं।

उत्तर

D · ग्राहक डेटा बदलने पर अतिरिक्त प्रतियों को संगत रखना पड़ता है
17.कंप्यूटर नेटवर्क

उत्तर: A · हर खोए हुए पैकेट को दोबारा भेजने से ज़्यादा कम देरी महत्वपूर्ण है

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

खोए हुए पैकेट दोबारा भेजने से देरी बढ़ेगी; रियल-टाइम मीडिया कुछ हानि सहन कर लेता है, इसलिए RTP जैसे UDP-आधारित प्रोटोकॉल उपयोग किए जाते हैं।

उत्तर

A · हर खोए हुए पैकेट को दोबारा भेजने से ज़्यादा कम देरी महत्वपूर्ण है
18.कंप्यूटर नेटवर्क

उत्तर: A · 8 टकराव डोमेन, 1 ब्रॉडकास्ट डोमेन

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

हर स्विच पोर्ट अपना टकराव डोमेन है, लेकिन ब्रॉडकास्ट सभी पोर्टों पर भेजे जाते हैं, इसलिए पूरा स्विच एक ब्रॉडकास्ट डोमेन है। हब से दोनों का एक-एक होता।

उत्तर

A · 8 टकराव डोमेन, 1 ब्रॉडकास्ट डोमेन
19.IPv4 सबनेटिंग

उत्तर: H = 1022

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.252.0 = /22

उपयोगी होस्ट

210 − 2 = 1022

उत्तर

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

उत्तर: x = 126

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

ब्लॉक आकार

26 = 64

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

नेटवर्क: ⌊109/64⌋·64 = 64
ब्रॉडकास्ट: 64 + 64 − 1 = 127
उपयोगी होस्ट: 65 … 126

उत्तर

x = 126

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