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

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

N = −968 bit

U =

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

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

1101 0011AND0001 1011

R =

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

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

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

N =

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

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

q ∨ rq∴ ¬r

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

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

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

F = Σm(4, 6, 9, 12, 14, 15)

1AB = 00, CD = 00
2AB = 00, CD = 01
3AB = 00, CD = 11
4AB = 00, CD = 10
5AB = 01, CD = 00
6AB = 01, CD = 01
7AB = 01, CD = 11
8AB = 01, CD = 10
9AB = 11, CD = 00
10AB = 11, CD = 01
11AB = 11, CD = 11
12AB = 11, CD = 10
13AB = 10, CD = 00
14AB = 10, CD = 01
15AB = 10, CD = 11
16AB = 10, CD = 10

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

F(A, B, C, D) = Σm(1, 4, 9, 10, 11, 13, 14) + d(2, 7) के लिए, जहाँ d डोंट-केयर स्थितियों को दर्शाता है, अनिवार्य प्रमुख प्रभाव्यों (एसेंशियल प्राइम इम्प्लिकेंट) की संख्या N ज्ञात करें।

F(A, B, C, D) = Σm(1, 4, 9, 10, 11, 13, 14) + d(2, 7)

N =

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

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

a = 59n = 80

59⁻¹ mod 80 =

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

एक RSA कुंजी में p = 23, q = 37 और e = 13 हैं। सिफरटेक्स्ट c = 54 को डिक्रिप्ट करें: संदेश m ज्ञात करें।

p = 23q = 37e = 13c = 54

m =

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

एक ग्रीडी एल्गोरिदम (greedy algorithm):

Aहर संभव समाधान आज़माता है
Bकेवल रिकर्शन का उपयोग करता है
Cहर चरण में स्थानीय रूप से सर्वोत्तम विकल्प चुनता है
Dहमेशा इष्टतम समाधान देता है

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

कौन-सी तकनीक किसी भी इनपुट पर क्विकसॉर्ट को अपेक्षित (expected) O(n log n) रनिंग टाइम देती है?

Aकेवल बाईं ओर रिकर्शन का उपयोग करना
Bक्विकसॉर्ट चलाने से पहले इनपुट को सॉर्ट करना
Cहमेशा पहला तत्व चुनना
Dपिवट को समान रूप से यादृच्छिक (uniformly at random) चुनना

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

बाइनरी मिन-हीप में extract-min कैसे काम करता है?

Aऐरे का अंतिम तत्व हटाएँ
Bअंतिम तत्व को रूट पर ले जाकर नीचे sift करें
Cनए न्यूनतम के लिए सभी लीफ़ खोजें
Dरूट हटाकर सभी तत्वों को एक स्थान बाएँ खिसकाएँ

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

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

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

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

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

2 × deg 32 × deg 42 × deg 52 × deg 2

L =

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

भारित ग्राफ़ के न्यूनतम स्पैनिंग ट्री का कुल भार W ज्ञात करें।

|V| = 5|E| = 7

W =

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

orders टेबल में 5 पंक्तियाँ हैं, हर एक किसी मौजूदा ग्राहक को संदर्भित करती है। customers टेबल में 3 पंक्तियाँ हैं। customer_id पर INNER JOIN कितनी पंक्तियाँ लौटाता है?

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

टेबल employee(emp_id, dept_id, dept_name) की की emp_id है, और dept_id → dept_name है। कौन-सा कथन सही है?

Aयह 1NF में नहीं है
Bयह 2NF में है पर 3NF में नहीं
Cयह 2NF में नहीं है
Dयह BCNF में है और इसलिए 3NF में भी है

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

NAT (नेटवर्क एड्रेस ट्रांसलेशन) का मुख्य उपयोग किसलिए होता है?

Aस्थानीय नेटवर्क के उपकरणों के लिए डोमेन नामों को IP पतों में बदलने के लिए
Bनेटवर्क केबल की गति बढ़ाने के लिए
Cदो साइटों के बीच ट्रैफ़िक एन्क्रिप्ट करने के लिए
Dनिजी पतों वाले कई उपकरणों को एक सार्वजनिक IP पता साझा करने देने के लिए

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

स्टेशन A और C दोनों एक्सेस पॉइंट B तक पहुँचते हैं पर एक-दूसरे को नहीं सुन सकते, इसलिए उनके फ़्रेम B पर टकराते हैं। 802.11 कैसे मदद करता है?

AA और C से टकराव पता लगाने का उपयोग करवाकर, ताकि फ़्रेम के अतिव्यापन पर वे भेजना बंद कर दें
BA के फ़्रेमों को C से होकर रूट करके
Cफ़्रेमों का TTL बढ़ाकर
Dवैकल्पिक RTS/CTS आदान-प्रदान से: AP का CTS आसपास के सभी स्टेशनों को प्रतीक्षा करने को कहता है

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

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

192.168.10.0/246 subnets

H =

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

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

172.20.190.121/21

x =

3विलयन

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

उत्तर: U = 160

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

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

96 = 0110 0000

उलटा हुआ: 1001 1111

+1 → 1010 0000

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

1010 0000₂ = 256 − 96 = 160

उत्तर

U = 160

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

उत्तर: R = 19

बिट-दर-बिट

AND केवल वहीं 1 देता है जहाँ दोनों बिट 1 हों।

1101 0011

AND 0001 1011

= 0001 0011

परिणाम का मान

0001 0011₂ = 19

उत्तर

R = 19

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

उत्तर: N = 6

सत्यमान सारणियाँ: 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 ∧ a = 1, ¬(c ∧ a) = 0, ¬b = 0, c ∨ b = 1, ¬b → (c ∨ b) = 1, ¬(c ∧ a) → (¬b → (c ∨ b)) = 1

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

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

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

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

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

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

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

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

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

N = 6

उत्तर

N = 6

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

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

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

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

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

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

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

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

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

q = 1, r = 1

उत्तर

q = 1, r = 1

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

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

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

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

हर 1 के पड़ोसी

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

m9: m8, m11, m13, m1 → 0

अकेला 1

m9 = AB′C′D → AB = 10, CD = 01

उत्तर

AB = 10, CD = 01

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

उत्तर: N = 4

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

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

B′C′D, B′CD′, AC′D, ACD′, AB′D, AB′C, A′BC′D′

अनिवार्य प्रमुख प्रभाव्य

B′C′D, AC′D, ACD′, A′BC′D′

N = 4

उत्तर

N = 4

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

उत्तर: 59⁻¹ mod 80 = 19

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

r = 80, t = 0

r = 59, q = 1, t = 1

r = 21, q = 2, t = −1

r = 17, q = 1, t = 3

r = 4, q = 4, t = −4

r = 1, q = 4, t = 19

व्युत्क्रम

1 ≡ 19·59 (mod 80)

x = 19

जाँच: 59·19 = 1121 = 14·80 + 1

उत्तर

59⁻¹ mod 80 = 19

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

उत्तर: m = 59

मॉड्यूलर घात और 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 = 851, φ(n) = 792

d = 13⁻¹ mod 792 = 61

बार-बार वर्ग करके डिक्रिप्ट करें

61 = 32 + 16 + 8 + 4 + 1

54¹ ≡ 54 (mod 851)

54² ≡ 363 (mod 851)

54⁴ ≡ 715 (mod 851)

54⁸ ≡ 625 (mod 851)

54¹⁶ ≡ 16 (mod 851)

54³² ≡ 256 (mod 851)

54⁶¹ ≡ 54·715·625·16·256 ≡ 59 (mod 851)

संदेश

m = 59

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

L + 28 = 2(L + 8) − 2

L = 14

उत्तर

L = 14

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

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

उत्तर: W = 25

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

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

DE (3): लें

BD (4): लें

D · वैकल्पिक RTS/CTS आदान-प्रदान से: AP का CTS आसपास के सभी स्टेशनों को प्रतीक्षा करने को कहता है

19.IPv4 सबनेटिंग

उत्तर: H = 30

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

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

2³ = 8 ≥ 6 → b = 3, /27

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

2⁵ − 2 = 30

उत्तर

H = 30

20.IPv4 सबनेटिंग

उत्तर: x = 184

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

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

2³ = 8

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

नेटवर्क: 172.20.184.0

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

उत्तर

x = 184

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