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

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

−53 को 8-बिट दो के पूरक पैटर्न के रूप में लिखें। पैटर्न को अचिह्नित द्विआधारी संख्या के रूप में पढ़ें: दशमलव में इसका मान U क्या है?

N = −538 bit

U =

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

एक असंपीड़ित छवि 1920 × 1080 पिक्सेल की है, प्रति पिक्सेल 16 बिट। यह KiB में (1 KiB = 1024 बाइट) कितनी मेमोरी M लेती है?

1920 × 1080 px16 bit/px1 KiB = 1024 B

M = KiB

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

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

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

N =

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

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

r ∨ p¬r

1r
2p
3r ∧ p
4¬p

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

F(A, B, C, D) = Σm(0, 3, 7, 10, 13, 15) का न्यूनतम गुणनफलों का योग (SOP) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कितने गुणन पद N हैं?

F(A, B, C, D) = Σm(0, 3, 7, 10, 13, 15)

N =

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

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

F(A, B, C, D) = Σm(1, 2, 7, 9) + d(5, 13)

N =

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

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

a = 21n = 29

21⁻¹ mod 29 =

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

19 अभाज्य है। 26⁶⁴⁶⁰⁰ mod 19 ज्ञात करने के लिए फर्मा के लघु प्रमेय का उपयोग करें।

p = 19k = 64600

26⁶⁴⁶⁰⁰ mod 19 =

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

किसी समस्या में इष्टतम उप-संरचना (optimal substructure) होने का क्या अर्थ है?

Aएक इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधानों से बनाया जा सकता है
Bहर उप-समस्या का आकार समान है
Cसमस्या को स्थिर समय में हल किया जा सकता है
Dसमस्या का ठीक एक इष्टतम समाधान है, जो हर उप-समस्या में साझा होता है

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

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

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

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

एक सड़क नेटवर्क में 100,000 जंक्शन हैं, हर एक लगभग 4 अन्य से जुड़ा है। कौन-सा निरूपण सबसे उपयुक्त है?

Aएडजेसेंसी लिस्ट
Bकिनारों का बाइनरी हीप
Cशीर्षों का एक सॉर्टेड ऐरे
Dएडजेसेंसी मैट्रिक्स

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

डेटाबेस इंडेक्स के लिए प्रायः साधारण B-ट्री के बजाय B+ ट्री का उपयोग क्यों करते हैं?

AB+ ट्री को संतुलित होने की आवश्यकता नहीं है
BB+ ट्री डेटा केवल रूट में संग्रहीत करते हैं
CB+ ट्री आंतरिक नोडों के रूप में बाइनरी नोड उपयोग करते हैं, जिससे डिस्क रीड घटते हैं
Dसभी रिकॉर्ड जुड़े हुए लीफ़ में होते हैं, जिससे रेंज स्कैन कुशल होते हैं

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

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

|V| = 7|E| = 12

1यूलर परिपथ
2यूलर पथ, परिपथ नहीं
3दोनों में से कुछ नहीं

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

क्रुस्कल का एल्गोरिथ्म न्यूनतम स्पैनिंग ट्री बनाता है। उस कोर पर क्लिक करें जिसे वह कोर संख्या 4 के रूप में जोड़ता है; छोड़ी गई कोरें नहीं गिनी जातीं।

k = 4

1कोर AB
2कोर AC
3कोर BC
4कोर BD
5कोर CE
6कोर DE
7कोर BE

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

SELECT name, CASE WHEN grade >= 5.5 THEN 'pass' ELSE 'fail' END FROM results क्या लौटाता है?

Aएक त्रुटि क्योंकि SELECT में CASE की अनुमति नहीं है
Bउत्तीर्ण और अनुत्तीर्ण छात्रों की संख्या
Cकेवल उत्तीर्ण छात्र
Dहर नाम, grade के अनुसार 'pass' या 'fail' लेबल के साथ

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

यदि col के सभी मान NULL हैं और टेबल में 10 पंक्तियाँ हैं, तो SELECT COUNT(col) FROM t का परिणाम क्या है?

A10
Bएक त्रुटि
C0
DNULL

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

1500-बाइट पैकेट को 12 Mbit/s लिंक पर डालने में कितना समय लगता है (संचरण विलंब, transmission delay)?

A1 ms
B0.125 ms
C8 ms
D12 ms

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

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

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

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

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

10.120.144.0/22/28

N =

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

एक राउटर के पास इन नेटवर्कों के लिए रूट हैं: 10.173.101.0/24, 10.173.102.0/24, 10.173.103.0/24, 10.173.104.0/24, 10.173.105.0/24, 10.173.106.0/24, 10.173.107.0/24, 10.173.108.0/24। इन सबको कवर करने वाले एकल सारांश रूट की सबसे लंबी उपसर्ग लंबाई p क्या है?

10.173.101.0/24 … 10.173.108.0/24

p =

3विलयन

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

उत्तर: U = 203

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

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

53 = 0011 0101

उलटा हुआ: 1100 1010

+1 → 1100 1011

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

1100 1011₂ = 256 − 53 = 203

उत्तर

U = 203

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

उत्तर: M = 4050 KiB

बिट और बाइट

1920·1080·16 = 33177600 bit = 4147200 B

KiB में बदलें

4147200/1024 = 4050 KiB

उत्तर

M = 4050 KiB

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

उत्तर: N = 1

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

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

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

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

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

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

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

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

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

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

N = 1

उत्तर

N = 1

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

उत्तर: p

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

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

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

निष्कर्ष

p (वियोजक न्यायवाक्य)

उत्तर

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

उत्तर: N = 4

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

1 को समूहित करें

हर समूह 2ᵏ खानों का आयत होता है; किनारे के खाने विपरीत किनारे के खानों के पड़ोसी होते हैं।

A′CD

ABD

A′B′C′D′

AB′CD′

न्यूनतम SOP रूप

F = A′CD + ABD + A′B′C′D′ + AB′CD′

N = 4

उत्तर

N = 4

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

उत्तर: N = 3

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

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

C′D, A′BD, A′B′CD′

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

C′D, A′BD, A′B′CD′

N = 3

उत्तर

N = 3

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

उत्तर: 21⁻¹ mod 29 = 18

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

r = 29, t = 0

r = 21, q = 1, t = 1

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

r = 5, q = 1, t = 3

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

r = 2, q = 1, t = 7

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

व्युत्क्रम

1 ≡ −11·21 (mod 29)

x = 18

जाँच: 21·18 = 378 = 13·29 + 1

उत्तर

21⁻¹ mod 29 = 18

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

उत्तर: 26⁶⁴⁶⁰⁰ mod 19 = 7

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

D · सभी रिकॉर्ड जुड़े हुए लीफ़ में होते हैं, जिससे रेंज स्कैन कुशल होते हैं

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

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

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

घात

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

विषम शीर्ष

यूलर परिपथ

उत्तर

यूलर परिपथ

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

उत्तर: कोर AB

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

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

1. DE (2)

2. CE (3)

3. BC (8)

4. AB (9)

Diffie-Hellman दो पक्षों को वही रहस्य निकालने देता है जिसकी गणना छिपकर सुनने वाले नहीं कर सकते। बीच में बैठा हमलावर हर पक्ष के साथ अलग विनिमय चला सकता है, जब तक कि मानों पर हस्ताक्षर न हों या उनका अन्यथा प्रमाणीकरण न हो।

उत्तर

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

19.IPv4 सबनेटिंग

उत्तर: N = 64

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

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

28 − 22 = 6

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

N = 2⁶ = 64

उत्तर

N = 64

हर /28 सबनेट में 2⁴ − 2 = 14 उपयोगी होस्ट हैं।

20.IPv4 सबनेटिंग

उत्तर: p = 20

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

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

101 = 01100101

108 = 01101100

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

उपसर्ग लंबाई

p = 16 + 4 = 20

उत्तर

p = /20

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

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