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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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-बिट पैटर्न 1100 1110 दो के पूरक में एक चिह्नित पूर्णांक संग्रहीत करता है। दशमलव में इसका मान N क्या है?

1100 11108 bit

N =

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

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

0101 1001<< 3

R =

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

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

((r ∨ p) ∧ ¬r) → p

1पुनरुक्ति
2विरोधोक्ति
3आपातिक कथन

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

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

¬∀x ∀y (R(x, y) → R(y, x))

1∀x ∀y (R(x, y) ∧ ¬R(y, x))
2∃x ∃y (R(x, y) ∧ ¬R(y, x))
3∃x ∃y (¬R(x, y) ∧ ¬R(y, x))
4∃x ∃y (R(x, y) → ¬R(y, x))

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

एक 4-से-1 मल्टीप्लेक्सर के चयन निवेश S₁ = A और S₀ = B हैं, और उसके डेटा निवेश I₀ = C′, I₁ = C′, I₂ = C′, I₃ = 1 से जुड़े हैं। A, B और C के 8 संयोजनों में से कितनों के लिए निर्गत F = 1 है? N ज्ञात करें।

I₀ = C′I₁ = C′I₂ = C′I₃ = 1

N =

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

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

Q₃Q₂Q₁Q₀ = 10110, 1, 0, 0

Q =

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

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

x ≡ 3 (mod 4)x ≡ 2 (mod 13)

x =

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

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

p = 13q = 43e = 19

d =

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

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

AO(n log n)
BO(n)
CO(log n)
DO(n²)

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

क्लास NP की कौन-सी परिभाषा सही है?

Aसमस्याएँ जिन्हें कोई एल्गोरिदम हल नहीं कर सकता
Bसमस्याएँ जो बहुपदी समय में हल नहीं हो सकतीं
Cनिर्णय समस्याएँ जिनके "हाँ" उत्तर किसी प्रमाणपत्र (certificate) के साथ बहुपदी समय में सत्यापित हो सकते हैं
Dसमस्याएँ जो बहुपदी नहीं हैं

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

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

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

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

मानक ब्लूम फ़िल्टर से तत्वों को उनके बिट साफ़ करके सीधे क्यों नहीं हटाया जा सकता?

Aहटाने से फ़ॉल्स पॉज़िटिव दर 100% हो जाएगी
Bब्लूम फ़िल्टर पूरे तत्व संग्रहीत करते हैं, और हैश हो जाने के बाद उन्हें दोबारा खोजा नहीं जा सकता
Cब्लूम फ़िल्टर के बिट बनने के बाद बदले नहीं जा सकते
Dवे बिट अन्य तत्वों के भी हो सकते हैं, जिससे फ़ॉल्स नेगेटिव होंगे

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

एक संबद्ध ग्राफ़ में 14 शीर्ष और 21 कोरें हैं। स्पैनिंग ट्री बचाने के लिए कितनी कोरें k हटानी होंगी?

|V| = 14|E| = 21

k =

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

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

M = संलग्नता आव्यूहL = 3

N =

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

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

Aइंसर्शन विसंगति (insertion anomaly)
Bफ़ैंटम रीड (phantom read)
Cअपडेट विसंगति (update anomaly)
Dडिलीशन विसंगति (deletion anomaly)

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

EXPLAIN (या PostgreSQL में EXPLAIN ANALYZE) किसी क्वेरी के लिए क्या दिखाता है?

Aकेवल रिलेशनल बीजगणित संकेतन में क्वेरी का पुनर्लेखन
Bक्वेरी चलाने वाले उपयोगकर्ताओं की सूची
Cऑप्टिमाइज़र द्वारा चुनी गई निष्पादन योजना, जैसे स्कैन और जॉइन विधियाँ
Dक्वेरी में हर SQL कीवर्ड का अर्थ

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

एक /24 IPv4 नेटवर्क में कितने उपयोग योग्य होस्ट पते होते हैं?

A252
B256
C255
D254

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

Diffie-Hellman कुंजी विनिमय अपने आप में क्या प्राप्त करता है, और इसकी कमज़ोरी क्या है?

Aयह वेबसाइटों के प्रमाणपत्रों पर हस्ताक्षर करता है, पर केवल छोटी कुंजियों के साथ काम करता है
Bयह सार्वजनिक चैनल पर बड़े डेटा को सीधे एन्क्रिप्ट करता है, पर बड़ी फ़ाइलों और वीडियो के लिए बहुत धीमा है
Cयह सार्वजनिक चैनल पर एक साझा रहस्य पर सहमति करता है, पर अकेले यह man-in-the-middle के लिए खुला है
Dयह पासवर्ड से दोनों उपयोगकर्ताओं का प्रमाणीकरण करता है, पर इसे केंद्रीय सर्वर चाहिए

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

नेटवर्क 172.20.0.0/16 को उपसर्ग /21 वाले समान सबनेट में बाँटा गया है। कितने सबनेट N हैं?

172.20.0.0/16/21

N =

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

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

172.20.197.152/22

x =

3विलयन

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

उत्तर: N = −50

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

मान जोड़ें

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

−128 + 64 + 8 + 4 + 2 = −50

उत्तर

N = −50

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

उत्तर: R = 200

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

बिट-दर-बिट

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

0101 1001 << 3

= 1100 1000

परिणाम का मान

1100 1000₂ = 200

उत्तर

R = 200

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, r = 1: r ∨ p = 1, ¬r = 0, (r ∨ p) ∧ ¬r = 0, ((r ∨ p) ∧ ¬r) → p = 1

p = 1, r = 0: r ∨ p = 1, ¬r = 1, (r ∨ p) ∧ ¬r = 1, ((r ∨ p) ∧ ¬r) → p = 1

p = 0, r = 1: r ∨ p = 1, ¬r = 0, (r ∨ p) ∧ ¬r = 0, ((r ∨ p) ∧ ¬r) → p = 1

p = 0, r = 0: r ∨ p = 0, ¬r = 1, (r ∨ p) ∧ ¬r = 0, ((r ∨ p) ∧ ¬r) → p = 1

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

((r ∨ p) ∧ ¬r) → p: 1, 1, 1, 1

हर पंक्ति में 1: पुनरुक्ति।

उत्तर

पुनरुक्ति

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

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

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

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

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

उत्तर

∃x ∃y (R(x, y) ∧ ¬R(y, x))

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

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

उत्तर: N = 5

मल्टीप्लेक्सर: 2ⁿ-से-1 मल्टीप्लेक्सर अपने डेटा निवेशों में से एक को निर्गत तक पहुँचाता है; चयन लाइनें, द्विआधारी संख्या के रूप में पढ़ी जाकर, तय करती हैं कि कौन-सा। चयन S₁S₀ = AB वाले 4-से-1 MUX के लिए F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃। डेटा निवेशों को 0, 1, C या C′ से जोड़ने पर MUX A, B और C का कोई भी फलन बना सकता है, जो एक ही चिप से लॉजिक बनाने का आम तरीका है।

निर्गत व्यंजक

F = A′B′C′ + A′BC′ + AB′C′ + AB

F = 1 वाली पंक्तियाँ

ABC = 000, 010, 100, 110, 111

N = 5

उत्तर

N = 5

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

उत्तर: Q = 2

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

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

1011 → 0101 → 1010 → 0101 → 0010

दशमलव मान

0010₂ = 2

उत्तर

Q = 2

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

उत्तर: x = 15

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

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

3 + 4k ≡ 2 (mod 13) → 4k ≡ 12 (mod 13)

k ≡ 10·12 ≡ 3 (mod 13)

परिणाम

x = 3 + 4·3 = 15

x = 15

जाँच: 15 mod 4 = 3, 15 mod 13 = 2

उत्तर

x = 15

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

उत्तर: d = 451

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

φ(n) = 12·42 = 504

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

r = 504, t = 0

r = 19, q = 26, t = 1

r = 10, q = 1, t = −26

r = 9, q = 1, t = 27

r = 1, q = 9, t = −53

निजी घातांक

d = 451

स्पैनिंग ट्री की कोरें

14 − 1 = 13

हटाई जाने वाली कोरें

k = 21 − 13 = 8

उत्तर

k = 8

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

उत्तर: N = 2

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। K_n में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

संलग्नता आव्यूह

A: 0 1 1 0 0

B: 1 0 1 1 0

C · यह सार्वजनिक चैनल पर एक साझा रहस्य पर सहमति करता है, पर अकेले यह man-in-the-middle के लिए खुला है

19.IPv4 सबनेटिंग

उत्तर: N = 32

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).

उधार लिए गए बिट

21 − 16 = 5

सबनेटों की संख्या

N = 2⁵ = 32

उत्तर

N = 32

हर /21 सबनेट में 2¹¹ − 2 = 2046 उपयोगी होस्ट हैं।

20.IPv4 सबनेटिंग

उत्तर: x = 196

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

2² = 4

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

नेटवर्क: 172.20.196.0

ब्रॉडकास्ट: 172.20.199.255

उत्तर

x = 196

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