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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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-बिट पैटर्न 1001 0111 दो के पूरक में एक चिह्नित पूर्णांक संग्रहीत करता है। दशमलव में इसका मान N क्या है?

1001 01118 bit

N =

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

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

2655

b = bit

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

आप r → ¬q को विरोधाभास द्वारा सिद्ध करना चाहते हैं। शुरू में कौन-सा कथन मानेंगे? उस पर क्लिक करें।

r → ¬q

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

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

F(A, B, C) = Σm(1, 4, 5, 6) का न्यूनतम गुणनफलों का योग (SOP) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कुल कितने लिटरल L हैं (प्राइम वाला चर एक लिटरल गिना जाता है)?

F(A, B, C) = Σm(1, 4, 5, 6)

L =

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

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

F(A, B, C, D) = Σm(3, 7, 8, 9, 10, 14, 15) + d(4, 5, 11)

N =

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

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

a = 43n = 61

43⁻¹ mod 61 =

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

एक RSA कुंजी में p = 13, q = 41 और e = 17 हैं। सिफरटेक्स्ट c = 68 को डिक्रिप्ट करें: संदेश m ज्ञात करें।

p = 13q = 41e = 17c = 68

m =

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

रिकरेंस T(n) = T(n − 1) + O(1) का हल क्या है?

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

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

कौन-सा एल्गोरिदम बार-बार ऐसा सबसे सस्ता एज जोड़कर, जो चक्र न बनाए, मिनिमम स्पैनिंग ट्री खोजता है?

ADijkstra का एल्गोरिदम
BFloyd–Warshall
CKruskal का एल्गोरिदम
Dएक नोड से शुरू होने वाला Prim का एल्गोरिदम

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

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

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

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

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

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

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

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

|V| = 5|E| = 7

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

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

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

|V| = 6|E| = 8

W =

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

कौन-सी क्वेरी customers टेबल में अलग-अलग शहरों की संख्या लौटाती है?

ASELECT COUNT(city) FROM customers GROUP BY city
BSELECT DISTINCT COUNT(city) FROM customers
CSELECT COUNT(DISTINCT city) FROM customers
DSELECT SUM(DISTINCT city) FROM customers

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

SELECT name, dept, AVG(salary) OVER (PARTITION BY dept) FROM emp क्या लौटाता है?

Aकेवल वे कर्मचारी जो अपने विभाग के औसत से अधिक कमाते हैं
Bएक त्रुटि क्योंकि name, GROUP BY में नहीं है
Cहर कर्मचारी पंक्ति, उसके विभाग के औसत salary के साथ
Dप्रति विभाग एक पंक्ति, उसके औसत salary के साथ

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

कौन-सा DNS रिकॉर्ड प्रकार होस्ट नाम को IPv6 पते से जोड़ता है?

AA
BMX
CAAAA
DCNAME

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

Nyquist सूत्र के अनुसार, 4 सिग्नल स्तरों का उपयोग करने वाले शोर-रहित 3 kHz चैनल की अधिकतम बिट दर क्या है?

A6 kbit/s
B12 kbit/s
C3 kbit/s
D24 kbit/s

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

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

192.168.77.0/24/26सबनेट 4 (सबनेट 1 .0 से शुरू होता है)

x =

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

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

10.20.221.126/25

x =

3विलयन

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

उत्तर: N = −105

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

मान जोड़ें

बाकी बिटें अपने सामान्य धनात्मक मान रखती हैं।

−128 + 16 + 4 + 2 + 1 = −105

उत्तर

N = −105

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

उत्तर: b = 12 bit

दो की घातें

2¹¹ = 2048 < 2655

2¹² = 4096 ≥ 2655

उत्तर

b = 12

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

उत्तर: r ∧ ¬¬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 = r, b = ¬q

निहितार्थ का निषेध

¬(a → b) ≡ a ∧ ¬b = r ∧ ¬¬q

उत्तर

r ∧ ¬¬q

यदि मान्यता विरोधाभास की ओर ले जाए, तो निहितार्थ सत्य होना चाहिए।

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

उत्तर: L = 4

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

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

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

B′C

AC′

न्यूनतम SOP रूप

F = B′C + AC′

L = 4

उत्तर

L = 4

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

उत्तर: N = 3

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

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

CD, AC, AB′, A′BD

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

CD, AC, AB′

N = 3

उत्तर

N = 3

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

उत्तर: 43⁻¹ mod 61 = 44

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

r = 61, t = 0

r = 43, q = 1, t = 1

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

r = 7, q = 2, t = 3

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

r = 3, q = 1, t = 10

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

व्युत्क्रम

1 ≡ −17·43 (mod 61)

x = 44

जाँच: 43·44 = 1892 = 31·61 + 1

उत्तर

43⁻¹ mod 61 = 44

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

उत्तर: m = 191

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

निजी घातांक

n = 533, φ(n) = 480

d = 17⁻¹ mod 480 = 113

बार-बार वर्ग करके डिक्रिप्ट करें

113 = 64 + 32 + 16 + 1

68¹ ≡ 68 (mod 533)

68² ≡ 360 (mod 533)

68⁴ ≡ 81 (mod 533)

68⁸ ≡ 165 (mod 533)

68¹⁶ ≡ 42 (mod 533)

68³² ≡ 165 (mod 533)

68⁶⁴ ≡ 42 (mod 533)

68¹¹³ ≡ 68·42·165·42 ≡ 191 (mod 533)

संदेश

m = 191

घात

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

विषम शीर्ष

C, E → 2

यूलर पथ, परिपथ नहीं

उत्तर

यूलर पथ, परिपथ नहीं

यूलर पथ एक विषम शीर्ष से शुरू होता है और दूसरे पर समाप्त होता है।

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

उत्तर: W = 31

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

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

DF (2): लें

BD (5): लें

BC (6): लें

B · 12 kbit/s

19.IPv4 सबनेटिंग

उत्तर: x = 192

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⁶ = 64

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

नेटवर्क: (4 − 1)·64 = 192

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

उत्तर

x = 192

20.IPv4 सबनेटिंग

उत्तर: x = 127

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

ब्लॉक आकार

2⁷ = 128

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

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

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

उपयोगी होस्ट: 1 … 126

उत्तर

x = 127

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