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

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

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

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

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

1024 × 768 px16 bit/px1 KiB = 1024 B
M = KiB
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
¬r ∧ p¬r ∧ ¬p¬r ∨ ¬p¬r ∨ p

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

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

आधार-वाक्य r → p; p और निष्कर्ष r वाला तर्क अवैध है। सत्यमान सारणी की उस पंक्ति पर क्लिक करें जो प्रति-उदाहरण है।

r → pp∴ r
  1. 1p = 1, r = 1
  2. 2p = 1, r = 0
  3. 3p = 0, r = 1
  4. 4p = 0, r = 0
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABCD000111100001111011111111

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

F = Σm(0, 6, 7, 9, 11, 13, 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-मानचित्र और फ़्लिप-फ़्लॉपकठिन
ABCD00011110000111100011030204050706112013X1511418X9111110

F(A, B, C, D) = Σm(1, 8, 10, 11, 12, 14) + d(9, 15) का न्यूनतम SOP रूप ज्ञात करें, जहाँ d डोंट-केयर स्थितियों को दर्शाता है। उसमें कितने गुणन पद N हैं?

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

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

a = 49n = 67
49−1 mod 67 =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
mc = me​ mod n297m = cd​ mod n?(n, e) = (493, 3)d

एक RSA कुंजी में p = 17, q = 29 और e = 3 हैं। सिफरटेक्स्ट c = 297 को डिक्रिप्ट करें: संदेश m ज्ञात करें।

p = 17q = 29e = 3c = 297
m =
9.एल्गोरिदम और जटिलतामध्यम

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

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

करात्सुबा गुणन T(n) = 3T(n/2) + O(n) को संतुष्ट करता है। इसका हल क्या है?

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

एक एप्लिकेशन को तेज़ खोज चाहिए और कुंजियों को सॉर्टेड क्रम में सूचीबद्ध करना तथा रेंज प्रश्नों के उत्तर देना भी चाहिए। कौन-सी संरचना सबसे उपयुक्त है?

  1. Aहैश टेबल
  2. Bअनसॉर्टेड लिंक्ड लिस्ट
  3. Cसंतुलित बाइनरी सर्च ट्री
  4. Dस्टैक
12.डेटा संरचनाएँकठिन

n तत्वों वाले बाइनरी मिन-हीप में किसी मनमानी कुंजी को खोजने में कितना समय लगता है?

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

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

K8
H =
14.ग्राफ़ सिद्धांतकठिन
ABCDE

लंबाई 3 की कितनी वॉक C से E तक जाती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।

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

एक टेबल हर ऑर्डर पंक्ति पर ग्राहक का पता संग्रहित करती है। एक पंक्ति में पता बदलना पर अन्य में नहीं, किसका उदाहरण है?

  1. Aडिलीशन विसंगति (deletion anomaly)
  2. Bइंसर्शन विसंगति (insertion anomaly)
  3. Cअपडेट विसंगति (update anomaly)
  4. Dफ़ैंटम रीड (phantom read)
16.डेटाबेस और SQLकठिन

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

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

HTTP विधियों GET और POST में मुख्य अंतर क्या है?

  1. AGET एन्क्रिप्टेड है, POST नहीं
  2. BGET UDP का उपयोग करता है, POST TCP का
  3. CGET संसाधन हटाता है, POST उसे सर्वर के डेटाबेस से पढ़ता है
  4. DGET एक संसाधन प्राप्त करता है, POST अनुरोध बॉडी में डेटा जमा करता है
18.कंप्यूटर नेटवर्ककठिन

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

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

नेटवर्क 192.168.10.0/24 को कम से कम 4 बराबर सबनेट में बाँटना है। यदि आप जितनी कम हो सकें उतनी बिटें उधार लें, तो हर सबनेट में कितने उपयोगी होस्ट H होंगे?

192.168.10.0/244 subnets
H =
20.IPv4 सबनेटिंगकठिन
तीसरा ऑक्टेट = 134112806403201608141201नेटवर्कहोस्ट

एक होस्ट का पता 172.20.134.104/21 है। इसके नेटवर्क पते का तीसरा ऑक्टेट x क्या है?

172.20.134.104/21
x =

3विलयन

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

उत्तर: U = 204

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

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

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

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

1100 1100₂ = 256 − 52 = 204

उत्तर

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

उत्तर: M = 1536 KiB

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

बिट और बाइट

1024·768·16 = 12582912 bit = 1572864 B

KiB में बदलें

1572864/1024 = 1536 KiB

उत्तर

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

उत्तर: ¬r ∨ ¬p

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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। ∧, ∨ बन जाता है और दोनों भागों का निषेध होता है।
¬(r ∧ p) ≡ ¬r ∨ ¬p

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

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

उत्तर

¬r ∨ ¬p

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

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

उत्तर: p = 1, r = 0

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

आधार-वाक्य और निष्कर्ष पंक्ति-दर-पंक्ति

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

प्रति-उदाहरण

p = 1, r = 0

उत्तर

p = 1, r = 0

इस रूप का तर्क वैध नियम जैसा दिखता है, पर यह दिखाने के लिए कि वह वैध नहीं है, एक पंक्ति काफ़ी है।

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

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

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

हर 1 के पड़ोसी

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

m0: m1, m2, m4, m8 → 0
ABCD000111100001111011111111

अकेला 1

m0 = A′B′C′D′ → AB = 00, CD = 00

उत्तर

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

उत्तर: N = 3

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

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

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

B′C′D, AD′, AC, AB′
ABCD00011110000111100011030204050706112013X1511418X9111110

न्यूनतम आवरण

F = B′C′D + AD′ + AC
N = 3

उत्तर

N = 3

उसी आकार का एक और समूहन संभव है; उसमें पदों और लिटरलों की संख्या वही है।

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

उत्तर: 49−1 mod 67 = 26

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

r = 67, t = 0
r = 49, q = 1, t = 1
r = 18, q = 2, t = −1
r = 13, q = 1, t = 3
r = 5, q = 2, t = −4
r = 3, q = 1, t = 11
r = 2, q = 1, t = −15
r = 1, q = 2, t = 26

व्युत्क्रम

1 ≡ 26·49 (mod 67)
x = 26
जाँच: 49·26 = 1274 = 19·67 + 1

उत्तर

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

उत्तर: m = 393

मॉड्यूलर घात और 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 = 493, φ(n) = 448
d = 3−1 mod 448 = 299

बार-बार वर्ग करके डिक्रिप्ट करें

299 = 256 + 32 + 8 + 2 + 1
2971 ≡ 297 (mod 493)
2972 ≡ 455 (mod 493)
2974 ≡ 458 (mod 493)
2978 ≡ 239 (mod 493)
29716 ≡ 426 (mod 493)
29732 ≡ 52 (mod 493)
29764 ≡ 239 (mod 493)
297128 ≡ 426 (mod 493)
297256 ≡ 52 (mod 493)
297299 ≡ 297·455·239·52·52 ≡ 393 (mod 493)

संदेश

m = 393
जाँच: 3933 mod 493 = 297

उत्तर

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

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

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

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

उत्तर

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

उत्तर: C · Θ(nlog₂ 3), लगभग n1.585

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

चूँकि log₂ 3 ≈ 1.585 > 1, मास्टर प्रमेय से पत्तियाँ (leaves) प्रभावी होती हैं, जो O(n²) पारंपरिक विधि से बेहतर है।

उत्तर

C · Θ(nlog₂ 3), लगभग n1.585
11.डेटा संरचनाएँ

उत्तर: C · संतुलित बाइनरी सर्च ट्री

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

संतुलित BST, O(log n) खोज देता है और कुंजियों को क्रम में रखता है, इसलिए इन-ऑर्डर ट्रैवर्सल और रेंज प्रश्न आसान हैं; हैश टेबल कुंजियों को बिखेर देती है।

उत्तर

C · संतुलित बाइनरी सर्च ट्री
12.डेटा संरचनाएँ

उत्तर: D · O(n)

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

हीप कोई नियम नहीं देता कि कौन-से सबट्री में कुंजी है, इसलिए वर्स्ट केस में सभी नोड जाँचने पड़ते हैं; केवल न्यूनतम तेज़ी से मिलता है।

उत्तर

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

उत्तर: H = 2520

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

गिनें

H = (8 − 1)!/2 = 5040/2 = 2520

उत्तर

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

उत्तर: N = 5

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ 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 1
C: 1 1 0 0 1
D: 0 1 0 0 0
E: 0 1 1 0 0

एक कदम और

(M³)CE = 1·0 + 2·1 + 3·1 + 1·0 + 1·0 = 5

उत्तर

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

उत्तर: C · अपडेट विसंगति (update anomaly)

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

अतिरिक्त (redundant) भंडारण का अर्थ है कि एक परिवर्तन कई पंक्तियों में करना पड़ता है; कुछ छूट जाने से डेटा असंगत हो जाता है, जिसे नॉर्मलाइज़ेशन रोकता है।

उत्तर

C · अपडेट विसंगति (update anomaly)
16.डेटाबेस और SQL

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

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

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

उत्तर

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

उत्तर: D · GET एक संसाधन प्राप्त करता है, POST अनुरोध बॉडी में डेटा जमा करता है

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

GET एक संसाधन माँगता है और उसे सर्वर की स्थिति नहीं बदलनी चाहिए। POST बॉडी में डेटा, जैसे फ़ॉर्म, सर्वर द्वारा संसाधित करने के लिए भेजता है।

उत्तर

D · GET एक संसाधन प्राप्त करता है, POST अनुरोध बॉडी में डेटा जमा करता है
18.कंप्यूटर नेटवर्क

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

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

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

उत्तर

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

उत्तर: H = 62

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

उधार ली जाने वाली बिटें

22 = 4 ≥ 4 → b = 2, /26

प्रति सबनेट होस्ट

26 − 2 = 62

उत्तर

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

उत्तर: x = 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).

तीसरे ऑक्टेट में ब्लॉक आकार

23 = 8

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

नेटवर्क: 172.20.128.0
ब्रॉडकास्ट: 172.20.135.255

उत्तर

x = 128

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