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

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

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

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

32 bit
N =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
पुनरुक्तिविरोधोक्तिआपातिक कथन

क्या q → (q ∧ p) पुनरुक्ति, विरोधोक्ति या आपातिक कथन है? अपना उत्तर क्लिक करें।

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

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

p ∨ rp → qr → q
  1. 1¬q
  2. 2q
  3. 3p ∧ r
  4. 4p
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABCD0001111000011110111111

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

F = Σm(1, 3, 4, 8, 9, 13)
  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-मानचित्र और फ़्लिप-फ़्लॉपकठिन
CLKT1234567

एक धनात्मक-कोर-ट्रिगर्ड T फ़्लिप-फ़्लॉप Q = 0 से शुरू होता है और 7 आरोही क्लॉक कोरों पर दिखाए गए निवेश पाता है। Q कितनी बार N अवस्था बदलता है?

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

सबसे छोटा धनात्मक पूर्णांक x ज्ञात करें जिसके लिए x ≡ 10 (mod 11) और x ≡ 2 (mod 13)।

x ≡ 10 (mod 11)x ≡ 2 (mod 13)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन

{0, 1, …, 54} में 45x ≡ 50 (mod 55) के कितने हल N हैं?

45x ≡ 50 (mod 55)
N =
9.एल्गोरिदम और जटिलतामध्यम

भर जाने पर अपनी क्षमता दोगुनी करने वाले डायनेमिक ऐरे में तत्व जोड़ने (append) की एमॉर्टाइज़्ड (amortised) टाइम कॉम्प्लेक्सिटी क्या है?

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

बॉटम-अप विधि से n अनसॉर्टेड तत्वों से बाइनरी हीप बनाने की टाइम कॉम्प्लेक्सिटी क्या है?

  1. AO(n)
  2. BO(log n)
  3. CO(n log n)
  4. DO(n²)
11.डेटा संरचनाएँमध्यम

बाइनरी हीप में नया तत्व कैसे डाला जाता है?

  1. Aपूरे हीप को फिर से शुरू से बनाएँ
  2. Bसभी बड़े तत्वों को एक स्थान दाएँ खिसकाकर उसे उसकी सॉर्टेड स्थिति में डालें
  3. Cउसे रूट पर रखें और नीचे sift करें
  4. Dउसे ऐरे के अंत में रखें और जब तक वह हीप गुण का उल्लंघन करे, ऊपर sift करें
12.डेटा संरचनाएँकठिन

डेटाबेस और फ़ाइल सिस्टम में B-ट्री का उपयोग क्यों किया जाता है?

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

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

2 × deg 33 × deg 44 × deg 5
L =
14.ग्राफ़ सिद्धांतकठिन
ABCDE

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

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

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

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

कई DBMS स्ट्रिक्ट टू-फ़ेज़ लॉकिंग का उपयोग क्यों करते हैं, जिसमें एक्सक्लूसिव लॉक कमिट तक रखे जाते हैं?

  1. Aयह ट्रांज़ैक्शनों को सुरक्षित रूप से डर्टी डेटा पढ़ने देता है
  2. Bयह डेडलॉक असंभव बनाता है
  3. Cयह ट्रांज़ैक्शन लॉग की आवश्यकता समाप्त करता है
  4. Dयह कैस्केडिंग एबॉर्ट रोकता है, क्योंकि कोई बिना कमिट के लेखन नहीं पढ़ सकता
17.कंप्यूटर नेटवर्कमध्यम

TCP/UDP पोर्ट संख्याओं की कौन-सी सीमा "well-known" पोर्टों के रूप में आरक्षित है?

  1. A49152–65535
  2. B1024–49151
  3. C0–1023
  4. D0–65535
18.कंप्यूटर नेटवर्ककठिन

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

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

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

192.168.10.0/243 subnets
H =
20.IPv4 सबनेटिंगकठिन

नेटवर्क 192.168.105.0/24 को इन LAN के लिए VLSM से बाँटा जाता है: A: 30 होस्ट, B: 22 होस्ट, C: 7 होस्ट, D: 4 होस्ट, E: 41 होस्ट। सबनेट .0 से ऊपर की ओर आवंटित किए जाते हैं, सबसे अधिक होस्ट वाला LAN पहले, हर एक को सबसे छोटा फ़िट होने वाला सबनेट। LAN A के नेटवर्क पते का चौथा ऑक्टेट x क्या है?

A: 30B: 22C: 7D: 4E: 41
x =

3विलयन

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

उत्तर: U = 254

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

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

2 = 0000 0010
उलटा हुआ: 1111 1101
+1 → 1111 1110

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

1111 1110₂ = 256 − 2 = 254

उत्तर

U = 254
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.प्रस्ताविक तर्क और उपपत्तियाँ

उत्तर: आपातिक कथन

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

सत्यमान सारणी पंक्ति-दर-पंक्ति

p = 1, q = 1: q ∧ p = 1, q → (q ∧ p) = 1
p = 1, q = 0: q ∧ p = 0, q → (q ∧ p) = 1
p = 0, q = 1: q ∧ p = 0, q → (q ∧ p) = 0
p = 0, q = 0: q ∧ p = 0, q → (q ∧ p) = 1

वर्गीकृत करें

q → (q ∧ p): 1, 1, 0, 1
4 पंक्तियों में से 3 में 1, बाकी में 0: एक आकस्मिकता (contingency)।

उत्तर

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

उत्तर: q

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

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

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

निष्कर्ष

q (स्थिति-विभाजन द्वारा उपपत्ति)

उत्तर

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

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

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

हर 1 के पड़ोसी

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

m4: m5, m6, m0, m12 → 0
ABCD0001111000011110111111

अकेला 1

m4 = A′BC′D′ → AB = 01, CD = 00

उत्तर

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

उत्तर: N = 4

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

T फ़्लिप-फ़्लॉप T = 1 के साथ हर आरोही कोर पर टॉगल करता है और T = 0 के साथ स्थिर रहता है।

1: T = 1 → Q = 1
2: T = 1 → Q = 0
3: T = 0 → Q = 0
4: T = 1 → Q = 1
5: T = 1 → Q = 0
6: T = 0 → Q = 0
7: T = 0 → Q = 0

परिवर्तन गिनें

0 → 1 → 0 → 0 → 1 → 0 → 0 → 0
N = 4

उत्तर

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

उत्तर: x = 54

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

पहली सर्वांगसमता

x = 10 + 11k

दूसरी सर्वांगसमता

10 + 11k ≡ 2 (mod 13) → 11k ≡ 5 (mod 13)
k ≡ 6·5 ≡ 4 (mod 13)

परिणाम

x = 10 + 11·4 = 54
x = 54
जाँच: 54 mod 11 = 10, 54 mod 13 = 2

उत्तर

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

उत्तर: N = 5

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

gcd से भाग दें

gcd(45, 55) = 5
9x ≡ 10 (mod 11)

घटी हुई सर्वांगसमता हल करें

9−1 ≡ 5 (mod 11) → x ≡ 6 (mod 11)

55 के मापांक में हल

x ∈ {6, 17, 28, 39, 50}
N = 5

उत्तर

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

उत्तर: C · O(1)

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

सभी तत्वों की कॉपी केवल दो की घातों पर होती है; सभी appends पर फैलाने से प्रति append औसत लागत स्थिर रहती है।

उत्तर

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

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

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

सभी स्तरों पर sift-down लागतों का योग एक अभिसारी श्रेणी देता है, इसलिए heapify रैखिक समय में चलता है।

उत्तर

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

उत्तर: D · उसे ऐरे के अंत में रखें और जब तक वह हीप गुण का उल्लंघन करे, ऊपर sift करें

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

अंत में जोड़ने से ट्री पूर्ण रहता है; पैरेंट से स्वैप करना O(log n) चरणों में क्रम बहाल करता है।

उत्तर

D · उसे ऐरे के अंत में रखें और जब तक वह हीप गुण का उल्लंघन करे, ऊपर sift करें
12.डेटा संरचनाएँ

उत्तर: A · उनका उच्च ब्रांचिंग फ़ैक्टर ट्री को उथला रखता है, जिससे धीमी डिस्क रीड कम होती हैं

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

B-ट्री प्रति नोड कई कुंजियाँ रखते हैं, इसलिए ऊँचाई कम होती है और प्रति लुकअप कम ब्लॉक रीड चाहिए; B+ ट्री रेंज स्कैन के लिए पत्तियों को भी जोड़ते हैं।

उत्तर

A · उनका उच्च ब्रांचिंग फ़ैक्टर ट्री को उथला रखता है, जिससे धीमी डिस्क रीड कम होती हैं
13.ग्राफ़ सिद्धांत

उत्तर: L = 22

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

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

L + 38 = 2(L + 9) − 2
L = 22

उत्तर

L = 22

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

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 1
C: 1 1 0 0 0
D: 0 1 0 0 1
E: 0 1 0 1 0

एक कदम और

(M³)AA = 2·0 + 1·1 + 1·1 + 1·0 + 1·0 = 2

उत्तर

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

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

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

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

उत्तर

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

उत्तर: D · यह कैस्केडिंग एबॉर्ट रोकता है, क्योंकि कोई बिना कमिट के लेखन नहीं पढ़ सकता

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

बुनियादी 2PL सीरियलाइज़ेबिलिटी की गारंटी देता है, पर राइट लॉक जल्दी छोड़ने से दूसरे ऐसा डेटा पढ़ सकते हैं जो बाद में रोलबैक हो; स्ट्रिक्ट 2PL इससे बचाता है।

उत्तर

D · यह कैस्केडिंग एबॉर्ट रोकता है, क्योंकि कोई बिना कमिट के लेखन नहीं पढ़ सकता
17.कंप्यूटर नेटवर्क

उत्तर: C · 0–1023

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

पोर्ट 0–1023 मानक सेवाओं के लिए well-known पोर्ट हैं। 1024–49151 पंजीकृत (registered) पोर्ट हैं और 49152–65535 डायनेमिक या निजी पोर्ट हैं।

उत्तर

C · 0–1023
18.कंप्यूटर नेटवर्क

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

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

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

उत्तर

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

उत्तर: H = 62

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

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

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

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

26 − 2 = 62

उत्तर

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

उत्तर: x = 64

VLSM: हर LAN को सबसे छोटा सबनेट मिलता है जिसके लिए 2ʰ − 2 ≥ उसकी होस्ट संख्या, अर्थात उपसर्ग 32 − h। सबसे बड़े सबनेट पहले आवंटित करने से हर ब्लॉक अपने आकार के गुणज पर संरेखित रहता है, इसलिए नेटवर्क पते ब्लॉक आकार जोड़ते जाने से मिलते हैं।

प्रति LAN ब्लॉक आकार

E: 41 होस्ट → 26 = 64 (/26)
A: 30 होस्ट → 25 = 32 (/27)
B: 22 होस्ट → 25 = 32 (/27)
C: 7 होस्ट → 24 = 16 (/28)
D: 4 होस्ट → 23 = 8 (/29)

आवंटन, सबसे बड़ा पहले

E: .0 – .63
A: .64 – .95
B: .96 – .127
C: .128 – .143
D: .144 – .151

उत्तर

x = 64

LAN A: 192.168.105.64/27।

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