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

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

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

N = −408 bit

U =

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

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

1111 0010<< 1

R =

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

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

(q ∨ (p ∧ r)) ∧ (q ↔ ¬p)

N =

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

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

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

N =

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

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

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

L =

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

एक तुल्यकालिक mod-6 काउंटर 0, 1, …, 5 गिनता है और फिर 0 पर लौटता है। यह 3 से शुरू होता है। 23 क्लॉक पल्स के बाद वह कौन-सी गिनती Q (दशमलव में) दिखाएगा?

Q₀ = 323N = 6

Q =

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

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

a = 6n = 17

6⁻¹ mod 17 =

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

54x ≡ 10 (mod 88) हल करें। सबसे छोटा धनात्मक हल x दें।

54x ≡ 10 (mod 88)

x =

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

बॉटम-अप तालिका से n-वीं फ़िबोनाची संख्या की गणना की टाइम कॉम्प्लेक्सिटी क्या है?

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

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

सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?

Aहर तत्व की कम से कम एक बार तुलना होनी चाहिए
Bबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए
Cn संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
Dहर तुलना में लघुगणकीय समय लगता है

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

किनारों में गिनी गई ऊँचाई h वाले पर्फ़ेक्ट बाइनरी ट्री में कितने नोड होते हैं?

A2^h+1 − 1
B2h + 1
C2^h
Dh²

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

ओपन एड्रेसिंग वाली हैश टेबल में डिलीशन अक्सर "टॉम्बस्टोन" चिह्न से क्यों किया जाता है?

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

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

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

|V| = 11|E| = 20

k =

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

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

|V| = 6|E| = 8

W =

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

एक कॉलम में मान 10, 20 और NULL हैं। AVG(col) क्या लौटाता है?

A10
B30
C15
DNULL

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

ट्रांज़ैक्शन T1 पंक्ति A को लॉक करता है और पंक्ति B की प्रतीक्षा करता है, जबकि T2 पंक्ति B को लॉक करता है और पंक्ति A की प्रतीक्षा करता है। एक सामान्य DBMS क्या करता है?

Aदोनों ट्रांज़ैक्शनों को एक में मिला देता है
Bदोनों ट्रांज़ैक्शनों को एक साथ कमिट करता है
Cडेडलॉक का पता लगाकर एक ट्रांज़ैक्शन को पीड़ित (victim) के रूप में रद्द करता है
Dदोनों ट्रांज़ैक्शनों को तब तक प्रतीक्षा करने देता है जब तक उनमें से एक सामान्य रूप से कमिट न हो जाए

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

TCP/UDP पोर्ट संख्याओं की कौन-सी सीमा "well-known" पोर्टों के रूप में आरक्षित है?

A49152–65535
B1024–49151
C0–1023
D0–65535

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

TCP कनेक्शन पहले बंद करने वाला पक्ष अधिकतम सेगमेंट जीवनकाल के दोगुने समय तक TIME_WAIT अवस्था में क्यों रहता है?

ADNS कैश की समय-सीमा समाप्त होने की प्रतीक्षा हेतु
Bताकि विलंबित सेगमेंट समाप्त हो जाएँ और खो जाने पर अंतिम ACK फिर से भेजा जा सके
Cताकि मार्ग के राउटर अगले कनेक्शन के लिए अपनी रूटिंग तालिकाएँ अद्यतन कर सकें
Dएन्क्रिप्शन कुंजियों को बाद में पुनः उपयोग के लिए रखने हेतु

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

एक सबनेट मास्क 255.255.240.0 का उपयोग करता है। इसमें कितने उपयोगी होस्ट पते H हैं?

255.255.240.0

H =

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

एक होस्ट का पता 10.20.202.152/29 है। उसके सबनेट के अंतिम उपयोगी होस्ट पते का चौथा ऑक्टेट x क्या है?

10.20.202.152/29

x =

3विलयन

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

उत्तर: U = 216

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

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

40 = 0010 1000

उलटा हुआ: 1101 0111

+1 → 1101 1000

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

1101 1000₂ = 256 − 40 = 216

उत्तर

U = 216

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

उत्तर: R = 228

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

बिट-दर-बिट

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

1111 0010 << 1

= 1110 0100

परिणाम का मान

1110 0100₂ = 228

उत्तर

R = 228

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

उत्तर: N = 3

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

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

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

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

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

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

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

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

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

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

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

(q ∨ (p ∧ r)) ∧ (q ↔ ¬p): 0, 0, 1, 0, 1, 1, 0, 0

N = 3

उत्तर

N = 3

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

उत्तर: N = 9

स्तंभ

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

p पर बाँटें

p = 1: 4

p = 0: 5

N = 4 + 5 = 9

उत्तर

N = 9

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

उत्तर: L = 4

बूलीय बीजगणित: व्यंजकों को सरल करने वाले नियम हैं 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′B′C′ → m(0)

BC′ → m(2, 6)

A′B′C → m(1)

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

F = BC′ + A′B′

लिटरल गिनें

L = 4

उत्तर

L = 4

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।

पूरे चक्र

हर 6 पल्स काउंटर को उसी अवस्था में वापस ले आते हैं।

23 = 3·6 + 5

शेष पल्स के बाद गिनती

Q = (3 + 5) mod 6 = 2

Q = 010₂

उत्तर

Q = 2

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

उत्तर: 6⁻¹ mod 17 = 3

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

r = 17, t = 0

r = 6, q = 2, t = 1

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

r = 1, q = 5, t = 3

व्युत्क्रम

1 ≡ 3·6 (mod 17)

x = 3

जाँच: 6·3 = 18 = 1·17 + 1

उत्तर

6⁻¹ mod 17 = 3

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

उत्तर: x = 23

gcd से भाग दें

gcd(54, 88) = 2

27x ≡ 5 (mod 44)

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

27⁻¹ ≡ 31 (mod 44) → x ≡ 23 (mod 44)

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

x ∈ {23, 67}

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

11 − 1 = 10

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

k = 20 − 10 = 10

उत्तर

k = 10

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

उत्तर: W = 60

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

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

AC (3): लें

DF (12): लें

DE (13): लें

BC (14): लें

B · ताकि विलंबित सेगमेंट समाप्त हो जाएँ और खो जाने पर अंतिम ACK फिर से भेजा जा सके

19.IPv4 सबनेटिंग

उत्तर: H = 4094

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

उपसर्ग लंबाई

255.255.240.0 = /20

उपयोगी होस्ट

2¹² − 2 = 4094

उत्तर

H = 4094

20.IPv4 सबनेटिंग

उत्तर: x = 158

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

ब्लॉक आकार

2³ = 8

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

नेटवर्क: ⌊152/8⌋·8 = 152

ब्रॉडकास्ट: 152 + 8 − 1 = 159

उपयोगी होस्ट: 153 … 158

उत्तर

x = 158

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