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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 20 अभ्यास प्रश्न, पूरे हल पीछे दिए गए हैं।

नए प्रश्न कोर्स पर वापस जाएँ

प्रिंट विंडो में “PDF के रूप में सहेजें” चुनें, ताकि एक प्रति आपके डिवाइस पर रहे।

1सूत्र और विधियाँ

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

स्थानीय मान: बाइनरी 2^k, ऑक्टल 8^k, हेक्स 16^k
दशमलव में: Σ d_k·b^k
दशमलव से: आधार से भाग दें, शेषफल नीचे से ऊपर पढ़ें
हेक्स ↔ बाइनरी: एक हेक्स अंक = 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

विधि

अलग-अलग चरों को गिनें: सत्यमान सारणी में 2ⁿ पंक्तियाँ होती हैं, जो सभी के 1 होने से शुरू होती हैं।
हर उप-सूत्र को अपना अलग स्तंभ दें और स्तंभों को भीतर से बाहर की ओर भरें।
हर संयोजक का नियम लगाएँ: → केवल 1 → 0 के लिए 0 होता है, ↔ तब 1 होता है जब दोनों पक्ष समान हों।
तुल्यता के लिए अंतिम स्तंभों की पंक्ति-दर-पंक्ति तुलना करें; किसी तर्क के लिए केवल उन्हीं पंक्तियों को देखें जिनमें हर आधार-वाक्य 1 हो।
परिमाणक वाले कथन का निषेध करने के लिए ¬ को भीतर ले जाएँ, ∀ और ∃ आपस में बदलें, और भीतरी सूत्र का निषेध करें।

डिजिटल लॉजिक: गेट, 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′I₀ + A′BI₁ + AB′I₂ + ABI₃
फ़्लिप-फ़्लॉप: D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
काउंटर: n-बिट: 2ⁿ अवस्थाएँ; mod-N: सबसे छोटा n जिसमें 2ⁿ ≥ N; f_out = f_clk/N
रिपल काउंटर: f_max = 1/(n·t_pd)
रिंग और जॉनसन काउंटर: n और 2n अवस्थाएँ

विधि

परिपथ के लिए निवेशों से निर्गत तक एक-एक गेट करके काम करें और हर तार पर मान लिखें, या उसका व्यंजक लिखें और सत्यमान सारणी भरें।
सरलीकरण के लिए 1 (और डोंट-केयर को X के रूप में) को ग्रे-कोड पंक्तियों और स्तंभों वाले कार्नो मानचित्र में रखें: 00, 01, 11, 10।
1 को 1, 2, 4, 8 या 16 खानों के जितने कम और जितने बड़े संभव हों उतने समूहों से ढकें, किनारों से लिपटते हुए; हर समूह एक गुणन पद है जो उन चरों से बना है जो स्थिर रहते हैं। POS रूप के लिए 0 को समूहित करें।
फ़्लिप-फ़्लॉप और काउंटरों के लिए हर सक्रिय क्लॉक कोर पर निवेश पढ़ें, हर कोर के बाद अवस्था लिखें, और याद रखें कि 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

विधि

पहले हर संख्या को n के मापांक में घटाएँ; शेषफल 0 से n − 1 के बीच होते हैं।
gcd के लिए यूक्लिड एल्गोरिथ्म से बार-बार भाग दें; अंतिम अशून्य शेषफल ही gcd है।
प्रतिलोम के लिए विस्तारित एल्गोरिथ्म चलाएँ और a का गुणांक रखें; ऋणात्मक हो तो n जोड़ें।
a·x ≡ b को हल करने के लिए a⁻¹ से गुणा करें; दो सर्वांगसमताओं को x = r₁ + m₁k लिखकर मिलाएँ।
घातों के लिए घातांक को द्विआधारी में लिखें और बार-बार वर्ग करें; RSA में d = e⁻¹ mod φ(n) होता है, जहाँ φ(n) = (p − 1)(q − 1)।

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

हैंडशेक लेमा: Σ deg(v) = 2|E|
पूर्ण ग्राफ़: |E(K_n)| = n(n − 1)/2, |E(K_m,n)| = m·n
नियमित ग्राफ़: |E| = n·k/2
वृक्ष और वन: |E| = n − 1, |E| = n − c
वृक्ष के पत्ते: L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर: परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
K_n में हैमिल्टन परिपथ: (n − 1)!/2
डाइक्स्ट्रा अद्यतन: d(v) = min(d(v), d(u) + w(u, v))
लंबाई L की वॉक: (Mᴸ)_ij

विधि

हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।

IPv4 सबनेटिंग

प्रति सबनेट होस्ट: 2^{(32 − prefix)} − 2 (/31: 2, /32: 1)
ब्लॉक आकार: 256 − (mask octet)
नेटवर्क पता: IP AND मास्क
ब्रॉडकास्ट पता: IP OR (NOT mask): सभी होस्ट बिट 1
n उधार लिए बिट से सबनेट: 2ⁿ

2अभ्यास प्रश्न

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

बिट इस तरह सेट करें कि वे 8-बिट 2 के पूरक में −101 संग्रहीत करें। चिह्नरहित संख्या के रूप में पढ़ने पर पैटर्न का मान U क्या है?

N = −1018 bit

U =

2.संख्या पद्धतियाँकठिन

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

1011 1011<< 3

R =

3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम

इसकी सत्यमान सारणी की 8 पंक्तियों में से कितनी में ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) सत्य है? इस संख्या को N कहें।

¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)))

N =

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

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

p ∨ qp∴ ¬q

1p = 1, q = 1
2p = 1, q = 0
3p = 0, q = 1
4p = 0, q = 0

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

F = A′BC + BC + A′C + AC′ को उसके न्यूनतम गुणनफलों के योग रूप में सरल करें। सरल किए गए व्यंजक में कितने लिटरल L हैं?

F = A′BC + BC + A′C + AC′

L =

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

एक रिंग काउंटर 4 D फ़्लिप-फ़्लॉप से बना है जिसमें अंतिम निर्गत पहले निवेश में लौटाया जाता है, और वह एकल 1 से शुरू होता है। वह कितनी भिन्न अवस्थाओं N से गुज़रता है?

n = 4

N =

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

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

x ≡ 2 (mod 5)x ≡ 5 (mod 7)

x =

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

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

p = 7q = 41e = 23

d =

9.एल्गोरिदम और जटिलतामध्यम

प्रिम का एल्गोरिदम मिनिमम स्पैनिंग ट्री कैसे बनाता है?

Aयह सबसे महँगा किनारा तब तक हटाता है जब तक कोई चक्र न बचे
Bयह सभी किनारों को भार के अनुसार सॉर्ट करता है और हर किनारे को तब तक जोड़ता है जब तक वह फ़ॉरेस्ट में चक्र (cycle) न बनाए
Cयह एक प्रारंभिक शीर्ष से एक ट्री बढ़ाता है, और ट्री से बाहर जाने वाला सबसे सस्ता किनारा जोड़ता है
Dयह ब्रेड्थ-फ़र्स्ट सर्च चलाकर BFS ट्री रखता है

10.एल्गोरिदम और जटिलताकठिन

P और NP के बारे में कौन-सा कथन सही है?

ANP का अर्थ है "not polynomial"
BNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
Cयह सिद्ध हो चुका है कि P ≠ NP
DP की हर समस्या NP में भी है

11.डेटा संरचनाएँमध्यम

आकार 7 की हैश टेबल h(k) = k mod 7 और लीनियर प्रोबिंग का उपयोग करती है। 10 डालने के बाद 17 कहाँ संग्रहीत होगा?

Aइंडेक्स 4
Bइंडेक्स 3
Cइंडेक्स 6
Dइंडेक्स 0

12.डेटा संरचनाएँकठिन

सिंगली लिंक्ड लिस्ट को इन-प्लेस उलटने की समय और अतिरिक्त स्पेस लागत क्या है?

AO(n log n) समय और O(1) अतिरिक्त स्पेस
BO(1) समय और O(1) अतिरिक्त स्पेस
CO(n) समय और O(1) अतिरिक्त स्पेस
DO(n) समय और O(n) अतिरिक्त स्पेस

13.ग्राफ़ सिद्धांतमध्यम

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

K₈

H =

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

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

प्रारंभ: Aअंत: F

d(F) =

15.डेटाबेस और SQLमध्यम

कौन-सी क्वेरी उन ग्राहकों को सूचीबद्ध करती है जिन्होंने कभी ऑर्डर नहीं दिया?

ASELECT c.name FROM customers c INNER JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL
BSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id = NULL
CSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NOT NULL
DSELECT c.name FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.id IS NULL

16.डेटाबेस और SQLकठिन

टेबल b के कॉलम y में मान 1, 2 और NULL हैं। SELECT * FROM a WHERE x NOT IN (SELECT y FROM b) क्या लौटाता है?

Aa की वे पंक्तियाँ जहाँ x, 1 या 2 नहीं है
Ba की केवल वे पंक्तियाँ जहाँ x NULL है
Ca की हर पंक्ति
Dकोई पंक्ति नहीं

17.कंप्यूटर नेटवर्कमध्यम

कौन-सा एकल प्रीफ़िक्स 192.168.0.0/24 और 192.168.1.0/24 दोनों को सारांशित (summarise) करता है?

A192.168.0.0/25
B192.168.0.0/22
C192.168.1.0/23
D192.168.0.0/23

18.कंप्यूटर नेटवर्ककठिन

DNS क्वेरी सामान्यतः UDP का उपयोग करती हैं। DNS आमतौर पर इसके बजाय TCP का उपयोग कब करता है?

AUDP के लिए बहुत बड़ी प्रतिक्रियाओं और ज़ोन ट्रांसफ़र के लिए
Bकेवल जब डोमेन नाम दस अक्षरों से लंबा हो
Cकेवल IP पतों के रिवर्स लुकअप के लिए
Dवेब ब्राउज़र से भेजी गई हर क्वेरी के लिए

19.IPv4 सबनेटिंगमध्यम

नेटवर्क 192.168.139.0/24 को /28 सबनेटों में बाँटा गया है, जिन्हें सबसे निचले पते से 1, 2, 3, … क्रमांकित किया गया है (सबनेट 1 .0 से शुरू होता है)। सबनेट 6 के नेटवर्क पते का चौथा ऑक्टेट x क्या है?

192.168.139.0/24/28सबनेट 6 (सबनेट 1 .0 से शुरू होता है)

x =

20.IPv4 सबनेटिंगकठिन

एक राउटर के पास इन नेटवर्कों के लिए रूट हैं: 10.118.12.0/24, 10.118.13.0/24, 10.118.14.0/24, 10.118.15.0/24, 10.118.16.0/24, 10.118.17.0/24, 10.118.18.0/24। इन सबको कवर करने वाले एकल सारांश रूट की सबसे लंबी उपसर्ग लंबाई p क्या है?

10.118.12.0/24 … 10.118.18.0/24

p =

3विलयन

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

उत्तर: U = 155

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

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

101 = 0110 0101

उलटा हुआ: 1001 1010

+1 → 1001 1011

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

1001 1011₂ = 256 − 101 = 155

उत्तर

U = 155

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

उत्तर: R = 216

बिट-दर-बिट

3 से बाईं ओर शिफ़्ट करने पर हर बिट 3 स्थान बाईं ओर खिसकता है; बाएँ सिरे से गिरे बिट खो जाते हैं और दाईं ओर शून्य आ जाते हैं।

1011 1011 << 3

= 1101 1000

परिणाम का मान

1101 1000₂ = 216

उत्तर

R = 216

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

उत्तर: N = 7

सत्यमान सारणियाँ: n अलग-अलग चरों वाले सूत्र की 2ⁿ पंक्तियाँ होती हैं, सत्यमानों के हर संयोजन के लिए एक (1 = सत्य, 0 = असत्य)। भीतर से बाहर की ओर काम करें और हर उप-सूत्र को अपना स्तंभ दें। ¬a मान उलट देता है; a ∧ b केवल तब 1 होता है जब दोनों 1 हों; a ∨ b केवल तब 0 होता है जब दोनों 0 हों; a → b केवल तब 0 होता है जब a = 1 और b = 0; a ↔ b तब 1 होता है जब दोनों पक्ष बराबर हों।

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

a = 1, b = 1, c = 1: c ∧ b = 1, (c ∧ b) ↔ a = 1, c ∨ a = 1, b ∧ (c ∨ a) = 1, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 1, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 0

a = 1, b = 1, c = 0: c ∧ b = 0, (c ∧ b) ↔ a = 0, c ∨ a = 1, b ∧ (c ∨ a) = 1, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 0, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 1

a = 1, b = 0, c = 1: c ∧ b = 0, (c ∧ b) ↔ a = 0, c ∨ a = 1, b ∧ (c ∨ a) = 0, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 0, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 1

a = 1, b = 0, c = 0: c ∧ b = 0, (c ∧ b) ↔ a = 0, c ∨ a = 1, b ∧ (c ∨ a) = 0, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 0, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 1

a = 0, b = 1, c = 1: c ∧ b = 1, (c ∧ b) ↔ a = 0, c ∨ a = 1, b ∧ (c ∨ a) = 1, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 0, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 1

a = 0, b = 1, c = 0: c ∧ b = 0, (c ∧ b) ↔ a = 1, c ∨ a = 0, b ∧ (c ∨ a) = 0, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 0, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 1

a = 0, b = 0, c = 1: c ∧ b = 0, (c ∧ b) ↔ a = 1, c ∨ a = 1, b ∧ (c ∨ a) = 0, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 0, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 1

a = 0, b = 0, c = 0: c ∧ b = 0, (c ∧ b) ↔ a = 1, c ∨ a = 0, b ∧ (c ∨ a) = 0, ((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a)) = 0, ¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))) = 1

मान 1 वाली पंक्तियाँ गिनें

¬(((c ∧ b) ↔ a) ∧ (b ∧ (c ∨ a))): 0, 1, 1, 1, 1, 1, 1, 1

N = 7

उत्तर

N = 7

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

उत्तर: p = 1, q = 1

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

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

p = 1, q = 1: 1 1 | 0

p = 1, q = 0: 1 1 | 1

p = 0, q = 1: 1 0 | 0

p = 0, q = 0: 0 0 | 1

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

p = 1, q = 1

उत्तर

p = 1, q = 1

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

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

उत्तर: L = 6

बूलीय बीजगणित: व्यंजकों को सरल करने वाले नियम हैं X + X′ = 1 और X·X′ = 0, X + X = X, अवशोषण X + X·Y = X, संयोजन नियम X·Y + X·Y′ = X, X + X′Y = X + Y और सहमति प्रमेय XY + X′Z + YZ = XY + X′Z। डी मॉर्गन के नियम (X·Y)′ को X′ + Y′ में और (X + Y)′ को X′·Y′ में बदलते हैं। कार्नो मानचित्र इन नियमों को चित्रात्मक रूप से लगाता है: दो पड़ोसी खानों का हर समूह XY + XY′ = X का एक उपयोग है।

व्यंजक के मिनटर्म

A′BC → m(3)

BC → m(3, 7)

A′C → m(1, 3)

AC′ → m(4, 6)

समूहित करें और पढ़ें

F = BC + A′C + AC′

लिटरल गिनें

L = 6

उत्तर

L = 6

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

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 काउंटर का अंतिम निर्गत f_clk/N पर चलता है। n फ़्लिप-फ़्लॉप वाले जॉनसन काउंटर की 2n अवस्थाएँ होती हैं, रिंग काउंटर की n।

4 फ़्लिप-फ़्लॉप के लिए अनुक्रम

1000 → 0100 → 0010 → 0001

अवस्थाओं की संख्या

N = 4

उत्तर

N = 4

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

उत्तर: x = 12

प्रतिलोम और सर्वांगसमताएँ: 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 = 2 + 5k

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

2 + 5k ≡ 5 (mod 7) → 5k ≡ 3 (mod 7)

k ≡ 3·3 ≡ 2 (mod 7)

परिणाम

x = 2 + 5·2 = 12

x = 12

जाँच: 12 mod 5 = 2, 12 mod 7 = 5

उत्तर

x = 12

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

उत्तर: d = 167

मॉड्यूलर घात और 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 = 7·41 = 287

φ(n) = 6·40 = 240

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

r = 240, t = 0

r = 23, q = 10, t = 1

r = 10, q = 2, t = −10

r = 3, q = 3, t = 21

r = 1, q = 3, t = −73

निजी घातांक

d = 167

गिनें

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

उत्तर

H = 2520

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

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

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

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

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

A (0): B: 11, C: 13

B (11): D: 25, E: 17

C (13)

E (17): D: 21, F: 23

D (21)

F (23)

सबसे छोटा पथ

A → B → E → F

ब्लॉक आकार

2⁴ = 16

सबनेट संख्या 6

नेटवर्क: (6 − 1)·16 = 80

ब्रॉडकास्ट: 80 + 16 − 1 = 95

उत्तर

x = 80

20.IPv4 सबनेटिंग

उत्तर: p = 19

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

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

12 = 00001100

18 = 00010010

साझा अग्रणी बिट: 3

उपसर्ग लंबाई

p = 16 + 3 = 19

उत्तर

p = /19

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

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