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

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

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

N = −958 bit

U =

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

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

1001 1011OR0010 1101

R =

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

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

p ∨ (r ∧ q)

1(p ∨ r) ∧ (p ∨ q)
2(p ∨ r) ∧ q
3p ∧ (r ∨ q)
4(p ∧ r) ∨ (p ∧ q)

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

सत्यमान सारणी की 16 पंक्तियों में से कितनी ((q → p) ∨ (p → r)) ∧ (¬(¬r ∨ s) ∨ s) को सत्य बनाती हैं? इस संख्या को N कहें।

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

N =

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

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

F = Σm(1, 3, 4, 7, 9, 10, 13, 14)

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

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

n = 5

N =

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

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

a = 15n = 23

15⁻¹ mod 23 =

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

{0, 1, …, 41} में 22x ≡ 2 (mod 42) के कितने हल N हैं?

22x ≡ 2 (mod 42)

N =

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

for i = 1 to n: for j = 1 to i: O(1) कार्य करें — इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

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

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

Aसमस्याएँ जिन्हें हर कंप्यूटर पर घातांकी समय चाहिए
Bसमस्याएँ जो समानांतर रूप से हल हो सकती हैं
Cसमस्याएँ जिनके समाधान जाँचे तो जा सकते हैं पर बहुपदी समय में कभी खोजे नहीं जा सकते
Dनिर्णय समस्याएँ जो एक नियतात्मक (deterministic) एल्गोरिदम द्वारा बहुपदी समय में हल हो सकती हैं

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

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

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

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

ऐरे के हर तत्व के लिए आप उसके दाईं ओर का अगला बड़ा तत्व कुल O(n) समय में चाहते हैं। कौन-सी संरचना मदद करती है?

Aएक स्टैक जो उत्तर की प्रतीक्षा कर रहे तत्वों को रखता है
Bतत्वों के हर युग्म को रखने वाली क्यू
Cसभी तत्वों की हैश टेबल
Dहर तत्व के लिए फिर से बनाया गया बाइनरी सर्च ट्री

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

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

|V| = 7|E| = 8

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

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

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

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

d(F) =

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

किसी पंक्ति के लिए WHERE EXISTS (subquery) कब सत्य होता है?

Aजब सबक्वेरी शून्य से बड़ी संख्या लौटाए
Bजब सबक्वेरी कोई NULL मान न लौटाए
Cजब सबक्वेरी कम से कम एक पंक्ति लौटाए
Dजब सबक्वेरी ठीक एक पंक्ति लौटाए

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

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

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

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

कौन-सा IPv4 हेडर फ़ील्ड पैकेटों को रूटिंग लूप में हमेशा घूमने से रोकता है?

AIdentification
BType of service
Cहेडर चेकसम
DTime to live (TTL)

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

एक फ़ायरवॉल सभी ICMP को रोकता है। छोटे वेब अनुरोध काम करते हैं, पर कुछ मार्गों पर बड़े डाउनलोड अटक जाते हैं। संभावित कारण क्या है?

ATCP बिना ICMP के कनेक्शन नहीं खोल सकता
BTLS प्रमाणपत्र ICMP पर भेजे जाते हैं
CDNS को नाम resolve करने के लिए ICMP चाहिए
DPath MTU discovery विफल होती है क्योंकि "fragmentation needed" संदेश रोके जाते हैं

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

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

192.168.10.0/2410 subnets

H =

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

एक होस्ट का पता 10.20.236.143/25 है। उसके नेटवर्क पते का चौथा ऑक्टेट x क्या है?

10.20.236.143/25

x =

3विलयन

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

उत्तर: U = 161

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

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

95 = 0101 1111

उलटा हुआ: 1010 0000

+1 → 1010 0001

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

1010 0001₂ = 256 − 95 = 161

उत्तर

U = 161

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

उत्तर: R = 191

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

बिट-दर-बिट

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

1001 1011

OR 0010 1101

= 1011 1111

परिणाम का मान

1011 1111₂ = 191

उत्तर

R = 191

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

उत्तर: (p ∨ r) ∧ (p ∨ q)

तार्किक तुल्यता: दो सूत्र तुल्य (≡) होते हैं जब सत्यमान सारणी की हर पंक्ति में उनका मान समान हो। पुनरुक्ति हर पंक्ति में 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)।

नियम

∨, ∧ पर वितरित होता है: a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)।

p ∨ (r ∧ q) ≡ (p ∨ r) ∧ (p ∨ q)

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

p = 1, q = 1, r = 1: 1 | 1 1 1 1

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

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

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

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

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

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

p = 0, q = 0, r = 0: 0 | 0 0 0 0

उत्तर

(p ∨ r) ∧ (p ∨ q)

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

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

उत्तर: N = 12

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

स्तंभ

q → p; p → r; (q → p) ∨ (p → r); ¬r; ¬r ∨ s; ¬(¬r ∨ s); ¬(¬r ∨ s) ∨ s; ((q → p) ∨ (p → r)) ∧ (¬(¬r ∨ s) ∨ s)

p पर बाँटें

p = 1: 6

p = 0: 6

N = 6 + 6 = 12

उत्तर

N = 12

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

अकेला 1

m4 = A′BC′D′ → AB = 01, CD = 00

उत्तर

AB = 01, CD = 00

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

उत्तर: N = 10

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

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

00000 → 10000 → 11000 → 11100 → 11110 → 11111 → 01111 → 00111 → 00011 → 00001

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

N = 10

उत्तर

N = 10

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

उत्तर: 15⁻¹ mod 23 = 20

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

r = 23, t = 0

r = 15, q = 1, t = 1

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

r = 7, q = 1, t = 2

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

व्युत्क्रम

1 ≡ −3·15 (mod 23)

x = 20

जाँच: 15·20 = 300 = 13·23 + 1

उत्तर

15⁻¹ mod 23 = 20

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

उत्तर: N = 2

gcd से भाग दें

gcd(22, 42) = 2

11x ≡ 1 (mod 21)

घटी हुई सर्वांगसमता हल करें

11⁻¹ ≡ 2 (mod 21) → x ≡ 2 (mod 21)

42 के मापांक में हल

x ∈ {2, 23}

घात

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

विषम शीर्ष

B, C, E, F → 4

दोनों में से कुछ नहीं

उत्तर

दोनों में से कुछ नहीं

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

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

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

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

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

A (0): B: 15, C: 5

C (5): B: 6, E: 11

B (6)

E (11): D: 22, F: 16

F (16): D: 19

D (19)

सबसे छोटा पथ

A → C → E → F

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

2⁴ = 16 ≥ 10 → b = 4, /28

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

2⁴ − 2 = 14

उत्तर

H = 14

20.IPv4 सबनेटिंग

उत्तर: x = 128

ब्लॉक आकार

2⁷ = 128

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

नेटवर्क: ⌊143/128⌋·128 = 128

ब्रॉडकास्ट: 128 + 128 − 1 = 255

उपयोगी होस्ट: 129 … 254

उत्तर

x = 128

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