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

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

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

1100 00018 bit
N =
2.संख्या पद्धतियाँकठिन
24 bit1 px1024 px768 pxM = ? KiB

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

1024 × 768 px24 bit/px1 KiB = 1024 B
M = KiB
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
b ∧ ¬a¬b ↔ ¬ab ↔ ¬a¬b ∨ ¬a

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

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

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

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

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

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

F(A, B, C, D) = Σm(0, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12) + d(1, 14) का न्यूनतम SOP रूप ज्ञात करें, जहाँ d डोंट-केयर स्थितियों को दर्शाता है। उसमें कितने लिटरल L हैं?

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

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

a = 7n = 19
7−1 mod 19 =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन

41 अभाज्य है। 759540 mod 41 ज्ञात करने के लिए फर्मा के लघु प्रमेय का उपयोग करें।

p = 41k = 59540
759540 mod 41 =
9.एल्गोरिदम और जटिलतामध्यम

क्या यह कहना सही है कि एक O(n²) एल्गोरिदम O(n³) भी है?

  1. Aहाँ, पर केवल तब जब n 100 से छोटा हो
  2. Bनहीं, क्योंकि Big O को हमेशा फ़ंक्शन की सटीक वृद्धि दर बतानी चाहिए
  3. Cहाँ, क्योंकि Big O एक ऊपरी सीमा है और n², n³ से तेज़ नहीं बढ़ता
  4. Dनहीं, क्योंकि बड़े n के लिए n³, n² से छोटा है
10.एल्गोरिदम और जटिलताकठिन

यदि कोई किसी एक NP-complete समस्या के लिए बहुपदी-समय एल्गोरिदम खोज ले, तो क्या निष्कर्ष निकलेगा?

  1. ANP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP
  2. Bकेवल वही एक समस्या P में चली जाएगी
  3. Cसभी घातांकी-समय एल्गोरिदम तुरंत रैखिक समय में चलने लगेंगे
  4. Dहॉल्टिंग समस्या निर्णेय हो जाएगी
11.डेटा संरचनाएँमध्यम

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

  1. Aहमेशा अवरोही क्रम में
  2. Bस्तर क्रम (level order) में
  3. Cइंसर्शन के क्रम में
  4. Dआरोही क्रमबद्ध क्रम में
12.डेटा संरचनाएँकठिन

एक सर्वर अपना हैश फ़ंक्शन यूनिवर्सल फ़ैमिली से यादृच्छिक रूप से क्यों चुन सकता है?

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

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

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

क्रुस्कल का एल्गोरिथ्म न्यूनतम स्पैनिंग ट्री बनाता है। उस कोर पर क्लिक करें जिसे वह कोर संख्या 5 के रूप में जोड़ता है; छोड़ी गई कोरें नहीं गिनी जातीं।

k = 5
  1. 1कोर AB
  2. 2कोर AC
  3. 3कोर BC
  4. 4कोर BD
  5. 5कोर CE
  6. 6कोर DE
  7. 7कोर DF
  8. 8कोर EF
  9. 9कोर BE
15.डेटाबेस और SQLमध्यम

एक टेबल में केवल एक क्लस्टर्ड इंडेक्स क्यों हो सकता है?

  1. Aक्लस्टर्ड इंडेक्स बहुत अधिक मेमोरी उपयोग करते हैं
  2. Bक्लस्टर्ड इंडेक्स केवल प्राइमरी की पर हो सकते हैं
  3. Cपंक्तियाँ भौतिक रूप से केवल एक क्रम में संग्रहित की जा सकती हैं
  4. DSQL मानक किसी टेबल पर एक से अधिक इंडेक्स की अनुमति नहीं देता
16.डेटाबेस और SQLकठिन

3NF की तुलना में टेबलों को BCNF में विघटित करने की एक ज्ञात कमी क्या है?

  1. Aकुछ फ़ंक्शनल डिपेंडेंसी अब एक अकेली टेबल के भीतर जाँची नहीं जा सकतीं
  2. BBCNF टेबलों में प्राइमरी की नहीं हो सकती
  3. Cवापस जोड़ने पर विघटन हमेशा डेटा खो देता है
  4. DBCNF, 3NF से अधिक अतिरेक (redundancy) की अनुमति देता है
17.कंप्यूटर नेटवर्कमध्यम

/20 किस सबनेट मास्क के अनुरूप है?

  1. A255.255.248.0
  2. B255.255.240.0
  3. C255.255.255.240
  4. D255.255.224.0
18.कंप्यूटर नेटवर्ककठिन

TCP हर कनेक्शन के लिए अप्रत्याशित प्रारंभिक अनुक्रम संख्या (initial sequence number) क्यों चुनता है?

  1. Aपुराने सेगमेंटों से भ्रम से बचने और जाली सेगमेंट डालना कठिन बनाने के लिए
  2. Bडेटा को अधिक कुशलता से संपीड़ित करने के लिए
  3. Cउस कनेक्शन के सेगमेंटों के लिए गंतव्य तक का सबसे अच्छा मार्ग चुनने के लिए
  4. Dहर सेगमेंट के पेलोड को एन्क्रिप्ट करने के लिए
19.IPv4 सबनेटिंगमध्यम
/24 → /2711111111111111111111111111100000नेटवर्क बिटहोस्ट बिट

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

192.168.10.0/245 subnets
H =
20.IPv4 सबनेटिंगकठिन
तीसरा ऑक्टेट 3 … 7012806403201608041211साझाभिन्न

एक राउटर के पास इन नेटवर्कों के लिए रूट हैं: 10.209.3.0/24, 10.209.4.0/24, 10.209.5.0/24, 10.209.6.0/24, 10.209.7.0/24। इन सबको कवर करने वाले एकल सारांश रूट की सबसे लंबी उपसर्ग लंबाई p क्या है?

10.209.3.0/24 … 10.209.7.0/24
p =

3विलयन

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

उत्तर: N = −63

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

मान जोड़ें

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

−128 + 64 + 1 = −63

उत्तर

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

उत्तर: M = 2304 KiB

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

बिट और बाइट

1024·768·24 = 18874368 bit = 2359296 B

KiB में बदलें

2359296/1024 = 2304 KiB

उत्तर

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

उत्तर: b ↔ ¬a

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

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

a = 1, b = 1: 0 | 0 1 0 0
a = 1, b = 0: 1 | 0 0 1 1
a = 0, b = 1: 1 | 1 0 1 1
a = 0, b = 0: 0 | 0 1 0 1

उत्तर

b ↔ ¬a

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

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

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

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

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

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

उत्तर

∃x ∀y ¬R(x, y)

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

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

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

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

हर 1 के पड़ोसी

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

m6: m7, m4, m2, m14 → 0
ABCD000111100001111011111111

अकेला 1

m6 = A′BCD′ → AB = 01, CD = 10

उत्तर

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

उत्तर: L = 4

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

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

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

D′, B′, A′C
ABCD000111100001111010X1131214051716112013015X141819111110

न्यूनतम आवरण

F = D′ + B′ + A′C
L = 4

उत्तर

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

उत्तर: 7−1 mod 19 = 11

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

r = 19, t = 0
r = 7, q = 2, t = 1
r = 5, q = 1, t = −2
r = 2, q = 2, t = 3
r = 1, q = 2, t = −8

व्युत्क्रम

1 ≡ −8·7 (mod 19)
x = 11
जाँच: 7·11 = 77 = 4·19 + 1

उत्तर

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

उत्तर: 759540 mod 41 = 40

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

घातांक को घटाएँ

59540 mod 40 = 20
759540 ≡ 720 (mod 41)

छोटी घात

720 mod 41 = 40

उत्तर

759540 mod 41 = 40
9.एल्गोरिदम और जटिलता

उत्तर: C · हाँ, क्योंकि Big O एक ऊपरी सीमा है और n², n³ से तेज़ नहीं बढ़ता

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

Big O एक ऊपरी सीमा है, इसलिए कथन सत्य है पर सटीक नहीं; Θ(n²) सटीक वृद्धि दर बताता है।

उत्तर

C · हाँ, क्योंकि Big O एक ऊपरी सीमा है और n², n³ से तेज़ नहीं बढ़ता
10.एल्गोरिदम और जटिलता

उत्तर: A · NP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP

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

चूँकि पूरा NP किसी भी NP-complete समस्या में बहुपदी समय में रिड्यूस होता है, एक के लिए तेज़ एल्गोरिदम सबके लिए तेज़ एल्गोरिदम देता है।

उत्तर

A · NP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP
11.डेटा संरचनाएँ

उत्तर: D · आरोही क्रमबद्ध क्रम में

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

पहले बाएँ सबट्री, फिर नोड, फिर दाएँ सबट्री पर जाने से BST की कुंजियाँ क्रमबद्ध क्रम में मिलती हैं।

उत्तर

D · आरोही क्रमबद्ध क्रम में
12.डेटा संरचनाएँ

उत्तर: C · ताकि यह बहुत असंभाव्य हो कि कोई हमलावर ऐसी कई कुंजियाँ चुन सके जो सभी टकराएँ

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

यूनिवर्सल हैशिंग के साथ किसी भी कुंजी समुच्चय के लिए कोलिज़न की अपेक्षित संख्या कम होती है, क्योंकि हमलावर नहीं जानता कि कौन-सा फ़ंक्शन चुना गया।

उत्तर

C · ताकि यह बहुत असंभाव्य हो कि कोई हमलावर ऐसी कई कुंजियाँ चुन सके जो सभी टकराएँ
13.ग्राफ़ सिद्धांत

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

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

घात

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

विषम शीर्ष

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

उत्तर

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

उत्तर: कोर DF

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

क्रुस्कल का एल्गोरिथ्म

1. AC (2)
2. EF (3)
3. BE (6)
4. AB (7)
5. DF (8)

कोर संख्या 5

DF

उत्तर

कोर DF
15.डेटाबेस और SQL

उत्तर: C · पंक्तियाँ भौतिक रूप से केवल एक क्रम में संग्रहित की जा सकती हैं

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

क्लस्टर्ड इंडेक्स टेबल के डेटा को अपनी की के अनुसार क्रमबद्ध करता है, और डेटा केवल एक क्रम में रखा जा सकता है; अन्य इंडेक्स नॉन-क्लस्टर्ड होते हैं।

उत्तर

C · पंक्तियाँ भौतिक रूप से केवल एक क्रम में संग्रहित की जा सकती हैं
16.डेटाबेस और SQL

उत्तर: A · कुछ फ़ंक्शनल डिपेंडेंसी अब एक अकेली टेबल के भीतर जाँची नहीं जा सकतीं

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

लॉसलेस BCNF विघटन हमेशा मौजूद होता है, पर वह डिपेंडेंसी संरक्षित नहीं भी कर सकता; 3NF हमेशा लॉसलेस और डिपेंडेंसी-संरक्षक दोनों हो सकता है।

उत्तर

A · कुछ फ़ंक्शनल डिपेंडेंसी अब एक अकेली टेबल के भीतर जाँची नहीं जा सकतीं
17.कंप्यूटर नेटवर्क

उत्तर: B · 255.255.240.0

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

/20 का अर्थ है 8 + 8 + 4 एक-बिट। तीसरे ऑक्टेट में चार एक-बिट 11110000 = 240 हैं, इसलिए मास्क 255.255.240.0 है।

उत्तर

B · 255.255.240.0
18.कंप्यूटर नेटवर्क

उत्तर: A · पुराने सेगमेंटों से भ्रम से बचने और जाली सेगमेंट डालना कठिन बनाने के लिए

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

यादृच्छिक प्रारंभिक अनुक्रम संख्याएँ पुराने कनेक्शनों के विलंबित सेगमेंटों को स्वीकार होने से रोकती हैं और मार्ग से बाहर के हमलावरों के लिए वैध सेगमेंट जाली बनाना कठिन करती हैं।

उत्तर

A · पुराने सेगमेंटों से भ्रम से बचने और जाली सेगमेंट डालना कठिन बनाने के लिए
19.IPv4 सबनेटिंग

उत्तर: H = 30

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

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

23 = 8 ≥ 5 → b = 3, /27

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

25 − 2 = 30

उत्तर

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

उत्तर: p = 21

रूट सारांशीकरण: सारांश रूट a.b.c.0/p उन सभी नेटवर्कों को कवर करता है जिनके पहले p बिट मेल खाते हैं। पहले और अंतिम नेटवर्क के भिन्न ऑक्टेट को बाइनरी में लिखें; साझा अग्रणी बिटों की संख्या, उससे पहले के ऑक्टेटों के बिट जोड़कर, सबसे लंबा सारांश उपसर्ग है।

बिटों की तुलना करें

3 = 00000011
7 = 00000111
साझा अग्रणी बिट: 5

उपसर्ग लंबाई

p = 16 + 5 = 21

उत्तर

p = /21

सारांश रूट: 10.209.0.0/21 (यह 3 ऐसे नेटवर्क भी कवर करता है जो सूची में नहीं हैं)।

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