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

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

N = −1108 bit

U =

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

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

1110 0010AND0010 0011

R =

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

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

r → p

1¬p → ¬r
2¬r → ¬p
3¬p ∧ ¬r
4p → r

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

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

q ∨ pq∴ ¬p

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

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

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

F(A, B, C, D) = Σm(0, 7, 10, 11)

N =

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

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

Q₀ = 424N = 9

Q =

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

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

a = 18n = 29

18⁻¹ mod 29 =

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

{0, 1, …, 33} में 6x ≡ 18 (mod 34) के कितने हल N हैं?

6x ≡ 18 (mod 34)

N =

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

डायनेमिक प्रोग्रामिंग (dynamic programming) तब उपयोगी है जब किसी समस्या में हों:

Aकोई उप-समस्या बिल्कुल न हो, ताकि उसे एक ही चरण में हल किया जा सके
Bकेवल एक लूप
Cओवरलैपिंग उप-समस्याएँ और इष्टतम उप-संरचना (optimal substructure)
Dकेवल यादृच्छिक इनपुट

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

यदि कोई किसी एक NP-complete समस्या के लिए बहुपदी-समय एल्गोरिदम खोज ले, तो क्या निष्कर्ष निकलेगा?

Aहॉल्टिंग समस्या निर्णेय हो जाएगी
Bसभी घातांकी-समय एल्गोरिदम तुरंत रैखिक समय में चलने लगेंगे
Cकेवल वही एक समस्या P में चली जाएगी
DNP की हर समस्या बहुपदी समय में हल हो सकेगी, इसलिए P = NP

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

AVL ट्री और रेड-ब्लैक ट्री किस बात की गारंटी देते हैं?

Aपुनर्संतुलन द्वारा O(log n) ऊँचाई
Bहर स्थिति में स्थिर समय में खोज
Cकुंजियाँ इंसर्शन के क्रम में संग्रहीत होती हैं
Dकिसी भी नोड के दो चाइल्ड नहीं होते

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

कौन-सी डेटा संरचना O(1) get और put के साथ LRU (least recently used) कैश को सपोर्ट करती है?

Aएक अकेला क्रमबद्ध ऐरे
Bकेवल बाइनरी सर्च ट्री
Cडबली लिंक्ड लिस्ट के साथ संयुक्त हैश मैप
Dकेवल स्टैक

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

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

|V| = 7|E| = 12

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

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

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

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

N =

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

रिलेशनल बीजगणित में प्रोजेक्शन ऑपरेटर (π) किसके अनुरूप है?

Aयह चुनना कि कौन-सी पंक्तियाँ दी गई शर्त को पूरा करती हैं
Bदो टेबलों को किसी की पर जोड़ना
Cपरिणाम को क्रमबद्ध करना
Dयह चुनना कि परिणाम में कौन-से कॉलम दिखें

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

R(A, B, C, D) में फ़ंक्शनल डिपेंडेंसी A → B और C → D हैं। कैंडिडेट की क्या है?

A{B, D}
B{C}
C{A}
D{A, C}

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

कौन-सा TCP फ़्लैग संकेत देता है कि प्रेषक ने डेटा भेजना समाप्त कर दिया है?

ASYN
BPSH
CFIN
DURG

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

TCP window scale विकल्प क्यों शुरू किया गया?

A16-बिट विंडो फ़ील्ड विंडो को 65,535 बाइट तक सीमित करता है, जो तेज़ लंबी दूरी के मार्गों के लिए बहुत छोटा है
B32-बिट विंडो फ़ील्ड बहुत बड़ा था और भेजे गए हर TCP सेगमेंट में हेडर की जगह बर्बाद करता था
CUDP को भीड़ भरे मार्गों पर अपनी प्रेषण दर नियंत्रित करने का तरीका चाहिए था
Dइसके बिना TCP लंबी दूरी के लिंकों पर खोए सेगमेंटों का पता नहीं लगा सकता था

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

नेटवर्क 192.168.251.0/24 को /28 सबनेटों में बाँटा गया है, जिन्हें सबसे निचले पते से 1, 2, 3, … क्रमांकित किया गया है (सबनेट 1 .0 से शुरू होता है)। सबनेट 6 के ब्रॉडकास्ट पते का चौथा ऑक्टेट x क्या है?

192.168.251.0/24/28सबनेट 6 (सबनेट 1 .0 से शुरू होता है)

x =

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

एक होस्ट का पता 10.20.62.171/28 है। उसके सबनेट के ब्रॉडकास्ट पते की अंतिम संख्या (चौथा ऑक्टेट) x क्या है?

10.20.62.171/28

x =

3विलयन

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

उत्तर: U = 146

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

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

110 = 0110 1110

उलटा हुआ: 1001 0001

+1 → 1001 0010

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

1001 0010₂ = 256 − 110 = 146

उत्तर

U = 146

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

उत्तर: R = 34

बिट-दर-बिट

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

1110 0010

AND 0010 0011

= 0010 0010

परिणाम का मान

0010 0010₂ = 34

उत्तर

R = 34

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

उत्तर: ¬p → ¬r

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

नियम

निहितार्थ अपने प्रतिधनात्मक ¬b → ¬a के तुल्य होता है, अपने विलोम b → a या व्युत्क्रम ¬a → ¬b के नहीं।

r → p ≡ ¬p → ¬r

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

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

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

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

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

उत्तर

¬p → ¬r

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

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

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

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

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

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

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

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

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

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

p = 1, q = 1

उत्तर

p = 1, q = 1

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

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

उत्तर: N = 5

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

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

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

(C + D′)

(B′ + D)

(A′ + C)

(A′ + B′)

(A + B + C′)

न्यूनतम POS रूप

F = (C + D′)(B′ + D)(A′ + C)(A′ + B′)(A + B + C′)

N = 5

उत्तर

N = 5

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

उत्तर: Q = 1

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

पूरे चक्र

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

24 = 2·9 + 6

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

Q = (4 + 6) mod 9 = 1

Q = 0001₂

उत्तर

Q = 1

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

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

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

r = 29, t = 0

r = 18, q = 1, t = 1

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

r = 7, q = 1, t = 2

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

r = 3, q = 1, t = 5

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

व्युत्क्रम

1 ≡ −8·18 (mod 29)

x = 21

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

उत्तर

18⁻¹ mod 29 = 21

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

उत्तर: N = 2

gcd से भाग दें

gcd(6, 34) = 2

3x ≡ 9 (mod 17)

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

3⁻¹ ≡ 6 (mod 17) → x ≡ 3 (mod 17)

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

x ∈ {3, 20}

घात

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

विषम शीर्ष

यूलर परिपथ

उत्तर

यूलर परिपथ

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

उत्तर: N = 1

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

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

A: 0 1 0 0 0

B: 1 0 1 1 1

A · 16-बिट विंडो फ़ील्ड विंडो को 65,535 बाइट तक सीमित करता है, जो तेज़ लंबी दूरी के मार्गों के लिए बहुत छोटा है

19.IPv4 सबनेटिंग

उत्तर: x = 95

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⁴ = 16

सबनेट संख्या 6

नेटवर्क: (6 − 1)·16 = 80

ब्रॉडकास्ट: 80 + 16 − 1 = 95

उत्तर

x = 95

20.IPv4 सबनेटिंग

उत्तर: x = 175

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

ब्लॉक आकार

2⁴ = 16

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

नेटवर्क: ⌊171/16⌋·16 = 160

ब्रॉडकास्ट: 160 + 16 − 1 = 175

उपयोगी होस्ट: 161 … 174

उत्तर

x = 175

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