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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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.संख्या पद्धतियाँकठिन
बिट सेट करने के लिए उन पर क्लिक करें012806403201608040201

बिट को 1001 1110 OR 1011 0001 के 8-बिट परिणाम पर सेट करें। दशमलव में परिणाम का मान R क्या है?

1001 1110OR1011 0001
R =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
¬r → ¬q¬q → ¬rq → r¬q ∧ ¬r

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

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

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

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

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

F = Σm(3, 4, 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-मानचित्र और फ़्लिप-फ़्लॉपकठिन
DQ3​Q3​DQ2​Q2​DQ1​Q1​DQ0​Q0​CLKSHIFT

एक 4-बिट शिफ़्ट रजिस्टर Q₃Q₂Q₁Q₀ में 0001 है। हर क्लॉक कोर पर बिट एक स्थान दाईं ओर खिसकते हैं (Q₃ → Q₂ → Q₁ → Q₀, Q₀ खो जाता है) और सीरियल निवेश Q₃ में प्रवेश करता है। सीरियल निवेश 6 कोरों पर 0, 1, 0, 1, 1, 0 है। अंतिम अवस्था Q = Q₃Q₂Q₁Q₀ दशमलव संख्या में दें।

Q₃Q₂Q₁Q₀ = 00010, 1, 0, 1, 1, 0
Q =
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

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

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

1093 mod 51 ज्ञात करने के लिए बार-बार वर्ग करने की विधि का उपयोग करें।

a = 10k = 93n = 51
1093 mod 51 =
9.एल्गोरिदम और जटिलतामध्यम

रिकरेंस T(n) = T(n − 1) + O(1) का हल क्या है?

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

जब कुछ किनारा भार ऋणात्मक हों, तो डाइकस्ट्रा का एल्गोरिदम ग़लत परिणाम क्यों दे सकता है?

  1. Aयह हर ऋणात्मक किनारे पर अनंत लूप में चला जाता है
  2. Bयह केवल अप्रत्यक्ष (undirected) ग्राफ़ पर काम करता है
  3. Cशीर्ष निकाले जाने पर अंतिम मान लिया जाता है, पर बाद का कोई ऋणात्मक किनारा उसे अब भी छोटा पथ दे सकता है
  4. Dप्रायोरिटी क्यू में ऋणात्मक संख्याएँ संग्रहीत नहीं की जा सकतीं
11.डेटा संरचनाएँमध्यम

ओपन एड्रेसिंग वाली हैश टेबल में अधिकतम संभव लोड फ़ैक्टर क्या है?

  1. A2
  2. Bकोई अधिकतम नहीं है
  3. C0.5
  4. D1
12.डेटा संरचनाएँकठिन

रेडिक्स ट्री (कंप्रेस्ड ट्राई) साधारण ट्राई में क्या सुधार करता है?

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

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

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

डाइक्स्ट्रा का एल्गोरिथ्म A से चलता है। उस शीर्ष पर क्लिक करें जो चक्र 3 में निर्धारित (स्थायी) होता है; A स्वयं चक्र 1 है।

प्रारंभ: Aचक्र 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
15.डेटाबेस और SQLमध्यम

SQL में व्यू (view) क्या है?

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

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

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

इंटरनेट पर किसी TCP कनेक्शन के एक छोर की अद्वितीय पहचान क्या करता है?

  1. Aपोर्ट नंबर के साथ एक IP पता
  2. Bअकेला MAC पता
  3. Cसबनेट मास्क और गेटवे
  4. Dअकेला डोमेन नाम
18.कंप्यूटर नेटवर्ककठिन

जब कोई साइट स्व-हस्ताक्षरित (self-signed) प्रमाणपत्र प्रस्तुत करती है तो ब्राउज़र चेतावनी क्यों देता है?

  1. Aप्रमाणपत्र हमेशा समाप्त (expired) होता है
  2. Bकोई विश्वसनीय प्रमाणपत्र प्राधिकरण (CA) यह पुष्टि नहीं करता कि कुंजी उसी साइट की है
  3. Cसाइट HTTPS के बजाय HTTP का उपयोग कर रही होगी
  4. Dस्व-हस्ताक्षरित प्रमाणपत्र बिल्कुल एन्क्रिप्शन का उपयोग नहीं करते, इसलिए ट्रैफ़िक सादे पाठ में भेजा जाता है
19.IPv4 सबनेटिंगमध्यम
/?11111111111111111111111000000000नेटवर्क बिटहोस्ट बिट

एक विभाग को एक ही सबनेट में 368 होस्ट पते चाहिए। पर्याप्त होने वाली सबसे लंबी उपसर्ग लंबाई p (सबसे छोटा सबनेट) क्या है?

368 hosts
p =
20.IPv4 सबनेटिंगकठिन
अंतिम ऑक्टेट = 82012816403211608041201नेटवर्कहोस्ट

एक होस्ट का पता 10.20.48.82/26 है। उसके सबनेट के ब्रॉडकास्ट पते की अंतिम संख्या (चौथा ऑक्टेट) x क्या है?

10.20.48.82/26
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.संख्या पद्धतियाँ

उत्तर: R = 191

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

बिट-दर-बिट

OR वहाँ 1 देता है जहाँ कम से कम एक बिट 1 हो।

1001 1110
OR 1011 0001
= 1011 1111

परिणाम का मान

1011 1111₂ = 191

उत्तर

R = 191
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)।

नियम

निहितार्थ अपने प्रतिधनात्मक ¬b → ¬a के तुल्य होता है, अपने विलोम b → a या व्युत्क्रम ¬a → ¬b के नहीं।
r → q ≡ ¬q → ¬r

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

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

उत्तर

¬q → ¬r

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

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

उत्तर: a = 0, b = 1

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

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

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

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

a = 0, b = 1

उत्तर

a = 0, b = 1

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

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

उत्तर: Q = 6

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

हर कोर के बाद की अवस्था

0001 → 0000 → 1000 → 0100 → 1010 → 1101 → 0110

दशमलव मान

0110₂ = 6

उत्तर

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

उत्तर: 11−1 mod 17 = 14

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

r = 17, t = 0
r = 11, q = 1, t = 1
r = 6, q = 1, t = −1
r = 5, q = 1, t = 2
r = 1, q = 5, t = −3

व्युत्क्रम

1 ≡ −3·11 (mod 17)
x = 14
जाँच: 11·14 = 154 = 9·17 + 1

उत्तर

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

उत्तर: 1093 mod 51 = 28

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

द्विआधारी घातांक

93 = 10111012 = 64 + 16 + 8 + 4 + 1

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

101 ≡ 10 (mod 51)
102 ≡ 49 (mod 51)
104 ≡ 4 (mod 51)
108 ≡ 16 (mod 51)
1016 ≡ 1 (mod 51)
1032 ≡ 1 (mod 51)
1064 ≡ 1 (mod 51)

आवश्यक घातों को गुणा करें

1093 ≡ 10·4·16·1·1 ≡ 28 (mod 51)

उत्तर

1093 mod 51 = 28
9.एल्गोरिदम और जटिलता

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

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

n स्तर हैं जिनमें से हर एक में स्थिर कार्य है, जैसे किसी ऐरे के रिकर्सिव योग में।

उत्तर

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

उत्तर: C · शीर्ष निकाले जाने पर अंतिम मान लिया जाता है, पर बाद का कोई ऋणात्मक किनारा उसे अब भी छोटा पथ दे सकता है

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

ग्रीडी चरण अऋणात्मक भारों पर निर्भर है ताकि निकाली गई दूरियाँ अंतिम हों; भार ऋणात्मक हो सकते हों तो बेलमैन–फ़ोर्ड का उपयोग होता है।

उत्तर

C · शीर्ष निकाले जाने पर अंतिम मान लिया जाता है, पर बाद का कोई ऋणात्मक किनारा उसे अब भी छोटा पथ दे सकता है
11.डेटा संरचनाएँ

उत्तर: D · 1

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

ओपन एड्रेसिंग में सभी कुंजियाँ स्वयं टेबल में संग्रहीत होती हैं, इसलिए n, m से अधिक नहीं हो सकता; सेपरेट चेनिंग में लोड फ़ैक्टर 1 से अधिक हो सकता है।

उत्तर

D · 1
12.डेटा संरचनाएँ

उत्तर: B · यह एकल-चाइल्ड नोडों की शृंखलाओं को एक स्ट्रिंग-लेबल वाले किनारे में मिला देता है

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

बिना शाखा वाले पथों को संकुचित करने से नोडों की संख्या और प्रयुक्त मेमोरी घटती है, जबकि प्रीफ़िक्स खोज बनी रहती है।

उत्तर

B · यह एकल-चाइल्ड नोडों की शृंखलाओं को एक स्ट्रिंग-लेबल वाले किनारे में मिला देता है
13.ग्राफ़ सिद्धांत

उत्तर: यूलर परिपथ

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

घात

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

विषम शीर्ष

0
यूलर परिपथ

उत्तर

यूलर परिपथ
14.ग्राफ़ सिद्धांत

उत्तर: D

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

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

1. A (0): B: 8
2. B (8): C: 23, D: 13, E: 14
3. D (13): F: 24
4. E (14): C: 15, F: 18
5. C (15)
6. F (18)

चक्र 3

D

उत्तर

D
15.डेटाबेस और SQL

उत्तर: D · एक संग्रहीत क्वेरी जो वर्चुअल टेबल की तरह व्यवहार करती है

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

व्यू एक SELECT स्टेटमेंट संग्रहीत करता है; इस पर क्वेरी करने से मूल क्वेरी चलती है (मटीरियलाइज़्ड व्यू परिणाम संग्रहीत करते हैं)।

उत्तर

D · एक संग्रहीत क्वेरी जो वर्चुअल टेबल की तरह व्यवहार करती है
16.डेटाबेस और SQL

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

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

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

उत्तर

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

उत्तर: A · पोर्ट नंबर के साथ एक IP पता

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

TCP कनेक्शन की पहचान स्रोत IP और पोर्ट तथा गंतव्य IP और पोर्ट से होती है। पोर्ट एक होस्ट पर कई एप्लिकेशन को अलग करते हैं।

उत्तर

A · पोर्ट नंबर के साथ एक IP पता
18.कंप्यूटर नेटवर्क

उत्तर: B · कोई विश्वसनीय प्रमाणपत्र प्राधिकरण (CA) यह पुष्टि नहीं करता कि कुंजी उसी साइट की है

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

ब्राउज़र उन प्रमाणपत्रों पर भरोसा करते हैं जिन पर उनके trust store के CA ने सीधे या श्रृंखला के माध्यम से हस्ताक्षर किए हों। स्व-हस्ताक्षरित प्रमाणपत्र कोई भी बना सकता है, जैसे कोई man-in-the-middle।

उत्तर

B · कोई विश्वसनीय प्रमाणपत्र प्राधिकरण (CA) यह पुष्टि नहीं करता कि कुंजी उसी साइट की है
19.IPv4 सबनेटिंग

उत्तर: p = 23

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

आवश्यक होस्ट बिट

28 − 2 = 254 < 368
29 − 2 = 510 ≥ 368 → h = 9

उपसर्ग लंबाई

p = 32 − 9 = 23

उत्तर

p = /23
20.IPv4 सबनेटिंग

उत्तर: x = 127

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

ब्लॉक आकार

26 = 64

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

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

उत्तर

x = 127

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