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

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

N = −348 bit

U =

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

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

0100 1010<< 2

R =

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

आप b → (c ∨ a) को विरोधाभास द्वारा सिद्ध करना चाहते हैं। शुरू में कौन-सा कथन मानेंगे? उस पर क्लिक करें।

b → (c ∨ a)

1¬b ∧ ¬(c ∨ a)
2¬b ∧ (c ∨ a)
3b ∧ ¬(c ∨ a)
4¬b → ¬(c ∨ a)

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

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

¬∀x P(x)

1∃x P(x)
2∃x ¬P(x)
3∀x P(x)
4∀x ¬P(x)

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

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

I₀ = CI₁ = 0I₂ = C′I₃ = C

N =

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

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

F(A, B, C, D) = Σm(3, 5, 6, 8, 11, 12, 14) + d(1, 4, 10, 13, 15)

L =

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

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

a = 4n = 19

4⁻¹ mod 19 =

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

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

p = 61k = 72784

22⁷²⁷⁸⁴ mod 61 =

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

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

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

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

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

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

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

एडजेसेंसी मैट्रिक्स से यह जाँचने में कितना समय लगता है कि किनारा (u, v) मौजूद है या नहीं?

AO(E)
BO(1)
CO(log V)
DO(V)

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

क्रमबद्ध लिंक्ड लिस्ट की तुलना में स्किप लिस्ट का मुख्य लाभ क्या है?

Aयह कोई अतिरिक्त मेमोरी नहीं लेती
Bआगे के पॉइंटरों के कई स्तरों का उपयोग करके अपेक्षित O(log n) खोज
Cगारंटीकृत O(1) खोज, क्योंकि हर नोड बाकी हर नोड का पॉइंटर रखता है
Dयह कुंजियों को बिना क्रम के संग्रहीत करती है

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

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

|V| = 7|E| = 7

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

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

प्रिम का एल्गोरिथ्म शीर्ष C से शुरू करके न्यूनतम स्पैनिंग ट्री बनाता है। उस कोर पर क्लिक करें जिसे वह कोर संख्या 2 के रूप में जोड़ता है।

प्रारंभ: Ck = 2

1कोर AB
2कोर BC
3कोर BD
4कोर CE
5कोर DE
6कोर DF
7कोर EF
8कोर BE

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

कॉलमों पर इंडेक्स क्यों बनाए जाते हैं?

Aउन कॉलमों पर खोज और जॉइन को तेज़ करने के लिए
Bडिस्क स्थान बचाने के लिए
CNULL मानों को रोकने के लिए
Dउन कॉलमों पर इंसर्ट और अपडेट को तेज़ करने के लिए

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

WHERE YEAR(order_date) = 2025 वाली क्वेरी order_date पर बने इंडेक्स का उपयोग क्यों नहीं कर सकती?

Aकॉलम पर फ़ंक्शन लगाने से सामान्य इंडेक्स रेंज लुकअप संभव नहीं रहता
BYEAR मान्य SQL नहीं है
Cइंडेक्स कभी भी तारीख़ों के साथ काम नहीं करते
Dorder_date पर बना इंडेक्स केवल ORDER BY क्लॉज़ के लिए उपयोग होता है, WHERE के लिए कभी नहीं

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

सम पैरिटी (even parity) का उपयोग करते हुए, डेटा बिट्स 1011001 में कौन-सा पैरिटी बिट जोड़ा जाता है?

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

एक सर्वर की निजी कुंजी आज से एक वर्ष बाद चोरी हो जाती है। कौन-सा TLS गुण आज के रिकॉर्ड किए गए सेशनों को सुरक्षित रखता है?

Aअल्पकालिक (ephemeral) Diffie-Hellman कुंजी विनिमय से forward secrecy
Bप्रमाणपत्र को दो बार भेजना
Cलंबे डोमेन नाम का उपयोग
Dएन्क्रिप्शन से पहले डेटा को संपीड़ित करना

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

एक विभाग को एक ही सबनेट में 202 होस्ट पते चाहिए। पर्याप्त होने वाली सबसे लंबी उपसर्ग लंबाई p (सबसे छोटा सबनेट) क्या है?

202 hosts

p =

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

एक होस्ट का पता 172.20.46.160/20 है। इसके सबनेट के ब्रॉडकास्ट पते का तीसरा ऑक्टेट x क्या है?

172.20.46.160/20

x =

3विलयन

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

उत्तर: U = 222

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

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

34 = 0010 0010

उलटा हुआ: 1101 1101

+1 → 1101 1110

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

1101 1110₂ = 256 − 34 = 222

उत्तर

U = 222

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

उत्तर: R = 40

बिट-दर-बिट

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

0100 1010 << 2

= 0010 1000

परिणाम का मान

0010 1000₂ = 40

उत्तर

R = 40

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

उत्तर: b ∧ ¬(c ∨ a)

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

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

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

उत्तर

b ∧ ¬(c ∨ a)

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

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

उत्तर: ∃x ¬P(x)

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

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

¬∀x P(x) ≡ ∃x ¬P(x)

उत्तर

∃x ¬P(x)

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

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

उत्तर: N = 3

मल्टीप्लेक्सर: 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 = A′B′C + AB′C′ + ABC

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

ABC = 001, 100, 111

N = 3

उत्तर

N = 3

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

उत्तर: L = 9

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

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

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

BD′, BC′, B′CD, AD′, AC, A′C′D, AB, A′B′D

न्यूनतम आवरण

F = BD′ + BC′ + B′CD + AD′

L = 9

उत्तर

L = 9

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

उत्तर: 4⁻¹ mod 19 = 5

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

r = 19, t = 0

r = 4, q = 4, t = 1

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

r = 1, q = 3, t = 5

व्युत्क्रम

1 ≡ 5·4 (mod 19)

x = 5

जाँच: 4·5 = 20 = 1·19 + 1

उत्तर

4⁻¹ mod 19 = 5

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

उत्तर: 22⁷²⁷⁸⁴ mod 61 = 16

मॉड्यूलर घात और 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 · आगे के पॉइंटरों के कई स्तरों का उपयोग करके अपेक्षित O(log n) खोज

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

उत्तर: यूलर पथ, परिपथ नहीं

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

घात

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

विषम शीर्ष

A, E → 2

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

उत्तर

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

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

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

उत्तर: कोर AB

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

प्रिम का एल्गोरिथ्म

1. BC (13)

2. AB (2)

3. BD (10)

4. BE (11)

5. EF (1)

अल्पकालिक (EC)DHE के साथ हर सेशन कुंजी अस्थायी मानों से निकाली जाती है जिन्हें नष्ट कर दिया जाता है। दीर्घकालिक कुंजी केवल विनिमय पर हस्ताक्षर करती है, इसलिए बाद में उसकी चोरी पुराने ट्रैफ़िक को डिक्रिप्ट नहीं करती।

उत्तर

A · अल्पकालिक (ephemeral) Diffie-Hellman कुंजी विनिमय से forward secrecy

19.IPv4 सबनेटिंग

उत्तर: p = 24

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

आवश्यक होस्ट बिट

2⁷ − 2 = 126 < 202

2⁸ − 2 = 254 ≥ 202 → h = 8

उपसर्ग लंबाई

p = 32 − 8 = 24

उत्तर

p = /24

20.IPv4 सबनेटिंग

उत्तर: x = 47

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

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

नेटवर्क: 172.20.32.0

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

उत्तर

x = 47

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