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

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

1010 01108 bit

N =

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

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

0111 0110AND0111 1111

R =

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

क्या ¬((c ∧ a) → c) पुनरुक्ति, विरोधोक्ति या आपातिक कथन है? अपना उत्तर क्लिक करें।

¬((c ∧ a) → c)

1पुनरुक्ति
2विरोधोक्ति
3आपातिक कथन

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

आधार-वाक्य q → p; ¬p दिए गए हैं। इनसे कौन-सा निष्कर्ष निकलता है? उस पर क्लिक करें।

q → p¬p

1¬q ∧ p
2q
3¬q
4p

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

एक 4-से-1 मल्टीप्लेक्सर के चयन निवेश S₁ = A और S₀ = B हैं, और उसके डेटा निवेश I₀ = 0, I₁ = 0, I₂ = 0, I₃ = 1 से जुड़े हैं। A, B और C के 8 संयोजनों में से कितनों के लिए निर्गत F = 1 है? N ज्ञात करें।

I₀ = 0I₁ = 0I₂ = 0I₃ = 1

N =

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

F(A, B, C, D) = Σm(5, 6, 13, 14, 15) + d(0, 12) का न्यूनतम SOP रूप ज्ञात करें, जहाँ d डोंट-केयर स्थितियों को दर्शाता है। उसमें कितने लिटरल L हैं?

F(A, B, C, D) = Σm(5, 6, 13, 14, 15) + d(0, 12)

L =

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

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

n = 11 = 11

φ(11) =

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

89 अभाज्य है। 30⁸⁰⁷⁸⁰ mod 89 ज्ञात करने के लिए फर्मा के लघु प्रमेय का उपयोग करें।

p = 89k = 80780

30⁸⁰⁷⁸⁰ mod 89 =

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

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

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

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

अनसॉर्टेड ऐरे का k-वाँ सबसे छोटा तत्व चुनने के बारे में कौन-सा कथन सही है?

Aसिलेक्शन केवल O(n²) में संभव है
Bक्विकसिलेक्ट वर्स्ट केस में O(log n) में चलता है क्योंकि वह पिवट के केवल एक ओर रिकर्स करता है
Cक्विकसिलेक्ट अपेक्षित O(n) में चलता है, और मीडियन-ऑफ़-मीडियन्स वर्स्ट केस में O(n) की गारंटी देता है
Dसिलेक्शन को हमेशा Ω(n log n) चाहिए क्योंकि उसे सॉर्टिंग चाहिए

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

"{[()]}" में कोष्ठक संतुलित हैं या नहीं, यह जाँचने के लिए कौन-सी डेटा संरचना उपयोग होती है?

Aस्टैक
Bक्यू
Cबाइनरी सर्च ट्री
Dहैश टेबल

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

एक डायनेमिक ऐरे भर जाने पर दोगुना होता है। कई कार्यान्वयन उसे आधा भरा होने के बजाय केवल एक-चौथाई भरा होने पर ही क्यों छोटा करते हैं?

Aक्योंकि मेमोरी आवंटक मेमोरी को केवल ब्लॉक के चौथाई भागों में मुक्त कर सकता है
Bसीमा के पास push और pop बारी-बारी से होने पर बार-बार आकार बदलने से बचने के लिए
Cऐरे को सॉर्टेड रखने के लिए
Dक्योंकि आधे पर आधा करने से तत्व खो जाएँगे

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

एक वृक्ष में घात 5 वाले 4 शीर्ष, घात 2 वाले 2 शीर्ष है, और उसके बाकी सभी शीर्ष पत्ते (घात 1) हैं। उसमें कितने पत्ते L हैं?

4 × deg 52 × deg 2

L =

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

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

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

d(F) =

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

EXCEPT (Oracle में MINUS कहलाता है) क्या लौटाता है?

Aदोनों क्वेरी की सभी पंक्तियाँ बिना डुप्लिकेट के
Bपहली क्वेरी की वे पंक्तियाँ जो दूसरी में नहीं हैं
Cदूसरी क्वेरी की वे पंक्तियाँ जो पहली में नहीं आतीं
Dवे पंक्तियाँ जो दोनों क्वेरी में हैं

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

एक ऐप UPDATE item SET qty = 4, version = 8 WHERE id = 1 AND version = 7 चलाता है, और कोई पंक्ति अपडेट न होने पर संघर्ष की सूचना देता है। यह कौन-सी तकनीक है?

Aडेटाबेस शार्डिंग
Bwrite-ahead logging
Cरो लॉक के साथ स्ट्रिक्ट टू-फ़ेज़ लॉकिंग
Dऑप्टिमिस्टिक कॉन्करेंसी कंट्रोल

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

एक संकेत फ़ाइबर में लगभग 2 × 10⁸ m/s की गति से 2000 km चलता है। प्रसार विलंब (propagation delay) क्या है?

A0.1 ms
B100 ms
C1 ms
D10 ms

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

इनमें से कौन-सा पता सार्वजनिक (RFC 1918 निजी नहीं) IPv4 पता है?

A172.32.0.1
B192.168.255.1
C10.255.0.1
D172.31.0.1

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

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

192.168.10.0/245 subnets

H =

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

एक होस्ट का पता 172.20.207.199/23 है। इसके नेटवर्क पते का तीसरा ऑक्टेट x क्या है?

172.20.207.199/23

x =

3विलयन

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

उत्तर: N = −90

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

मान जोड़ें

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

−128 + 32 + 4 + 2 = −90

उत्तर

N = −90

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

उत्तर: R = 118

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

बिट-दर-बिट

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

0111 0110

AND 0111 1111

= 0111 0110

परिणाम का मान

0111 0110₂ = 118

उत्तर

R = 118

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

उत्तर: विरोधोक्ति

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

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

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

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

वर्गीकृत करें

¬((c ∧ a) → c): 0, 0, 0, 0

हर पंक्ति में 0: विरोधोक्ति।

उत्तर

विरोधोक्ति

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

उत्तर: ¬q

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

वे पंक्तियाँ जिनमें सभी आधार-वाक्य सत्य हैं

p = 0, q = 0: ¬q ∧ p = 0, q = 0, ¬q = 1, p = 0

निष्कर्ष

¬q (मोडस टोलेंस)

उत्तर

¬q

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

उत्तर: N = 2

मल्टीप्लेक्सर: 2ⁿ-से-1 मल्टीप्लेक्सर अपने डेटा निवेशों में से एक को निर्गत तक पहुँचाता है; चयन लाइनें, द्विआधारी संख्या के रूप में पढ़ी जाकर, तय करती हैं कि कौन-सा। चयन S₁S₀ = AB वाले 4-से-1 MUX के लिए F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃। डेटा निवेशों को 0, 1, C या C′ से जोड़ने पर MUX A, B और C का कोई भी फलन बना सकता है, जो एक ही चिप से लॉजिक बनाने का आम तरीका है।

निर्गत व्यंजक

F = AB

F = 1 वाली पंक्तियाँ

ABC = 110, 111

N = 2

उत्तर

N = 2

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

उत्तर: L = 8

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

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

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

BC′D, BCD′, AB

न्यूनतम आवरण

F = BC′D + BCD′ + AB

L = 8

उत्तर

L = 8

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

उत्तर: φ(11) = 10

प्रतिलोम और सर्वांगसमताएँ: 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)।

अभाज्य गुणनखंड

11 = 11

टोशेंट

φ(11) = 11 − 1 = 10

उत्तर

φ(11) = 10

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

उत्तर: 30⁸⁰⁷⁸⁰ mod 89 = 81

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

B · सीमा के पास push और pop बारी-बारी से होने पर बार-बार आकार बदलने से बचने के लिए

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

उत्तर: L = 14

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

वृक्ष के लिए हैंडशेक लेमा

L + 24 = 2(L + 6) − 2

L = 14

उत्तर

L = 14

शॉर्टकट: L = 2 + Σ (d − 2), घात d ≥ 3 वाले शीर्षों पर।

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

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

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

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

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

A (0): B: 11, C: 3

C (3): E: 13, G: 16

B (11): D: 23

E (13): F: 19

G (16)

F (19)

D (23)

सबसे छोटा पथ

A → C → E → F

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

2³ = 8 ≥ 5 → b = 3, /27

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

2⁵ − 2 = 30

उत्तर

H = 30

20.IPv4 सबनेटिंग

उत्तर: x = 206

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¹ = 2

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

नेटवर्क: 172.20.206.0

ब्रॉडकास्ट: 172.20.207.255

उत्तर

x = 206

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