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

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

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

N = −1098 bit

U =

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

एक प्रणाली को 411 वस्तुओं में से हर एक को समान लंबाई का अपना द्विआधारी कोड देना है। कम से कम कितनी बिटें b चाहिए?

411

b = bit

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

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

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

N =

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

निषेध को पूरी तरह भीतर ले जाने पर कौन-सा कथन ¬∃x (P(x) → Q(x)) के तुल्य है? उस पर क्लिक करें।

¬∃x (P(x) → Q(x))

1∀x (¬P(x) → ¬Q(x))
2∃x (P(x) ∧ ¬Q(x))
3∀x (P(x) ∧ ¬Q(x))
4∀x (P(x) → ¬Q(x))

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

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

F = Σm(0, 2, 3, 7, 8, 11, 13)

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

एक mod-9 काउंटर न्यूनतम संख्या के फ़्लिप-फ़्लॉप से बना है। संभव अवस्थाओं में से कितनी U कभी उपयोग नहीं होतीं?

N = 9

U =

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

यूलर का टोशेंट φ(297) ज्ञात करें, यानी 1 से 297 तक के वे पूर्णांक जो 297 से सहअभाज्य हैं।

n = 297 = 3³·11

φ(297) =

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

31¹⁶⁰ mod 36 ज्ञात करने के लिए बार-बार वर्ग करने की विधि का उपयोग करें।

a = 31k = 160n = 36

31¹⁶⁰ mod 36 =

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

प्रिम का एल्गोरिदम मिनिमम स्पैनिंग ट्री कैसे बनाता है?

Aयह एक प्रारंभिक शीर्ष से एक ट्री बढ़ाता है, और ट्री से बाहर जाने वाला सबसे सस्ता किनारा जोड़ता है
Bयह सबसे महँगा किनारा तब तक हटाता है जब तक कोई चक्र न बचे
Cयह ब्रेड्थ-फ़र्स्ट सर्च चलाकर BFS ट्री रखता है
Dयह सभी किनारों को भार के अनुसार सॉर्ट करता है और हर किनारे को तब तक जोड़ता है जब तक वह फ़ॉरेस्ट में चक्र (cycle) न बनाए

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

बॉटम-अप विधि से n अनसॉर्टेड तत्वों से बाइनरी हीप बनाने की टाइम कॉम्प्लेक्सिटी क्या है?

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

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

लोड फ़ैक्टर सीमा पार होने के बाद जब हैश टेबल rehash करती है, तो क्या होता है?

Aकेवल टकराने वाली कुंजियाँ टेबल के अंत में एक नई ओवरफ़्लो लिस्ट में ले जाई जाती हैं
Bमौजूदा कुंजियाँ उसी स्थान पर सॉर्ट की जाती हैं
Cएक बड़ी टेबल आवंटित होती है और हर कुंजी फिर से डाली जाती है
Dजगह बनाने के लिए सबसे पुरानी कुंजियाँ हटा दी जाती हैं

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

AVL ट्री में एक कुंजी डालने से किसी नोड का बायाँ सबट्री बहुत ऊँचा हो जाता है, और नई कुंजी उसके बाएँ चाइल्ड के बाएँ सबट्री में गई (left-left स्थिति)। कौन-सा सुधार लागू होता है?

Aअसंतुलित नोड पर एक एकल दायाँ रोटेशन
Bचाइल्ड पर बायाँ रोटेशन, फिर नोड पर दायाँ रोटेशन
Cअसंतुलित नोड पर एक एकल बायाँ रोटेशन
Dनोड और उसके चाइल्ड का रंग बदलना

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

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

|V| = 5|E| = 5

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

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

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

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

N =

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

ROLLBACK TO SAVEPOINT s1 क्या करता है?

Aट्रांज़ैक्शन समाप्त करता है और सब कुछ कमिट करता है
Bsavepoint और तब से बदली गई सभी टेबलें हटा देता है
Csavepoint s1 के बाद किए गए परिवर्तन पूर्ववत करता है, ट्रांज़ैक्शन खुला रखते हुए
Dपूरे ट्रांज़ैक्शन को शुरुआत से पूर्ववत करता है

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

EXPLAIN (या PostgreSQL में EXPLAIN ANALYZE) किसी क्वेरी के लिए क्या दिखाता है?

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

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

255.255.255.0 का सबनेट मास्क CIDR संकेतन में किसके बराबर है?

A/8
B/32
C/16
D/24

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

एक छात्र होम NAT राउटर के पीछे एक PC पर गेम सर्वर चलाता है। इंटरनेट पर दोस्त कनेक्ट नहीं कर पाते। सामान्य समाधान क्या है?

APC को अलग MAC पता देना ताकि राउटर उसे बाहर से खोज सके
BPC का सबनेट मास्क /32 करना
Cराउटर पर PC के निजी पते के लिए पोर्ट फ़ॉरवर्डिंग कॉन्फ़िगर करना
DPC का DNS क्लाइंट बंद करना

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

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

255.255.255.192

H =

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

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

10.20.111.188/29

x =

3विलयन

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

उत्तर: U = 147

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

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

109 = 0110 1101

उलटा हुआ: 1001 0010

+1 → 1001 0011

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

1001 0011₂ = 256 − 109 = 147

उत्तर

U = 147

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

उत्तर: b = 9 bit

दो की घातें

2⁸ = 256 < 411

2⁹ = 512 ≥ 411

उत्तर

b = 9

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

उत्तर: N = 4

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

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

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

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

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

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

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

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

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

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

N = 4

उत्तर

N = 4

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

उत्तर: ∀x (P(x) ∧ ¬Q(x))

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

निषेध को भीतर ले जाएँ

¬∃x (P(x) → Q(x)) ≡ ∀x (P(x) ∧ ¬Q(x))

उत्तर

∀x (P(x) ∧ ¬Q(x))

बाकी विकल्प या तो किसी परिमाणक को अपरिवर्तित रखते हैं, या परिमाणकों का क्रम बदल देते हैं, या भीतरी सूत्र का निषेध गलत करते हैं।

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

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

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

हर 1 के पड़ोसी

द्विआधारी घातांक

160 = 10100000₂ = 128 + 32

बार-बार वर्ग करना

31¹ ≡ 31 (mod 36)

31² ≡ 25 (mod 36)

31⁴ ≡ 13 (mod 36)

31⁸ ≡ 25 (mod 36)

31¹⁶ ≡ 13 (mod 36)

A · असंतुलित नोड पर एक एकल दायाँ रोटेशन

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

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

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

घात

deg(A) = 2, deg(B) = 2, deg(C) = 2, deg(D) = 2, deg(E) = 2

विषम शीर्ष

यूलर परिपथ

उत्तर

यूलर परिपथ

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

उत्तर: N = 2

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

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

A: 0 1 1 0 0 0

B: 1 0 1 1 1 0

C: 1 1 0 0 0 0

C · राउटर पर PC के निजी पते के लिए पोर्ट फ़ॉरवर्डिंग कॉन्फ़िगर करना

19.IPv4 सबनेटिंग

उत्तर: H = 62

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.255.192 = /26

उपयोगी होस्ट

2⁶ − 2 = 62

उत्तर

H = 62

20.IPv4 सबनेटिंग

उत्तर: x = 184

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

ब्लॉक आकार

2³ = 8

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

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

ब्रॉडकास्ट: 184 + 8 − 1 = 191

उपयोगी होस्ट: 185 … 190

उत्तर

x = 184

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