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

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

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

1001 1011OR0110 0000

R =

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

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

(p → r) ↔ (¬r → ¬p)

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

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

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

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

N =

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

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

F = Σm(3, 5, 6, 10, 11, 14)

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

एक 4-बिट शिफ़्ट रजिस्टर Q₃Q₂Q₁Q₀ में 1100 है। हर क्लॉक कोर पर बिट एक स्थान दाईं ओर खिसकते हैं (Q₃ → Q₂ → Q₁ → Q₀, Q₀ खो जाता है) और सीरियल निवेश Q₃ में प्रवेश करता है। सीरियल निवेश 6 कोरों पर 0, 1, 0, 1, 1, 1 है। अंतिम अवस्था Q = Q₃Q₂Q₁Q₀ दशमलव संख्या में दें।

Q₃Q₂Q₁Q₀ = 11000, 1, 0, 1, 1, 1

Q =

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

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

n = 65 = 5·13

φ(65) =

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

22x ≡ 18 (mod 42) हल करें। सबसे छोटा धनात्मक हल x दें।

22x ≡ 18 (mod 42)

x =

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

किसी समस्या में इष्टतम उप-संरचना (optimal substructure) होने का क्या अर्थ है?

Aसमस्या का ठीक एक इष्टतम समाधान है, जो हर उप-समस्या में साझा होता है
Bसमस्या को स्थिर समय में हल किया जा सकता है
Cएक इष्टतम समाधान उसकी उप-समस्याओं के इष्टतम समाधानों से बनाया जा सकता है
Dहर उप-समस्या का आकार समान है

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

क्या 2²ⁿ, O(2ⁿ) में है?

Aनहीं, क्योंकि 2²ⁿ, 2ⁿ से धीमा बढ़ता है
Bनहीं, क्योंकि 2²ⁿ = 4ⁿ और 4ⁿ / 2ⁿ = 2ⁿ असीमित रूप से बढ़ता है
Cहाँ, क्योंकि दोनों घातांकी हैं
Dहाँ, क्योंकि Big O में घातांक के स्थिर गुणक हमेशा अनदेखे किए जाते हैं

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

व्यवहार में ऐरे का ट्रैवर्सल प्रायः समान लंबाई की लिंक्ड लिस्ट से बहुत तेज़ क्यों होता है?

Aलिंक्ड लिस्ट हमेशा तत्व डिस्क पर संग्रहीत करती हैं
Bऐरे मानों की तुलना के लिए कम निर्देश उपयोग करते हैं
Cऐरे ट्रैवर्सल कुल मिलाकर O(1) है जबकि लिंक्ड लिस्ट ट्रैवर्सल O(n)
Dऐरे तत्व लगातार होते हैं, इसलिए वे CPU कैश का अच्छा उपयोग करते हैं

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

सिंपल यूनिफ़ॉर्म हैशिंग के अंतर्गत n कुंजियों और m बकेटों वाली चेनिंग हैश टेबल में खोज का अपेक्षित समय क्या है?

AO(log n)
BO(1 + α), जहाँ α = n / m
CO(m)
DO(n)

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

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

|V| = 5|E| = 6

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

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

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

प्रारंभ: Fk = 4

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

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

SQL इंजेक्शन (SQL injection) क्या है?

Aइंडेक्स जोड़ने का एक तरीका
Bएक अकेले INSERT स्टेटमेंट से कई पंक्तियाँ जल्दी डालने की विधि
Cडेटाबेस बैकअप की एक तकनीक
Dएक हमला जिसमें उपयोगकर्ता इनपुट SQL क्वेरी की संरचना बदल देता है

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

फ़ैंटम रीड (phantom read) क्या है?

Aदोहराई गई क्वेरी किसी अन्य कमिट हुए ट्रांज़ैक्शन द्वारा डाली गई नई पंक्तियाँ लौटाती है
Bएक क्वेरी जो कोई पंक्ति नहीं लौटाती
Cऐसा डेटा पढ़ना जो कभी लिखा ही नहीं गया
Dबिना कमिट किए बदलाव पढ़ना

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

VLAN का मुख्य उद्देश्य क्या है?

Aएक भौतिक स्विच्ड नेटवर्क को अलग-अलग ब्रॉडकास्ट डोमेन में बाँटना
Bहर उपकरण को सार्वजनिक IP पता देना
Cस्विचों के बीच सारा ट्रैफ़िक एन्क्रिप्ट करना ताकि अन्य विभाग उसे न पढ़ सकें
Dहर स्विच पोर्ट की गति बढ़ाना

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

एक TCP कनेक्शन की विंडो 64 KB और राउंड-ट्रिप समय 100 ms है, और कोई window scaling नहीं है। इसका अनुमानित अधिकतम थ्रूपुट क्या है?

Aलगभग 0.5 Mbit/s
Bलगभग 50 Mbit/s
Cलगभग 640 Mbit/s
Dलगभग 5 Mbit/s

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

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

255.255.254.0

H =

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

एक राउटर के पास इन नेटवर्कों के लिए रूट हैं: 10.98.26.0/24, 10.98.27.0/24, 10.98.28.0/24, 10.98.29.0/24। इन सबको कवर करने वाले एकल सारांश रूट की सबसे लंबी उपसर्ग लंबाई p क्या है?

10.98.26.0/24 … 10.98.29.0/24

p =

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 = 251

बिट-दर-बिट

OR वहाँ 1 देता है जहाँ कम से कम एक बिट 1 हो।

1001 1011

OR 0110 0000

= 1111 1011

परिणाम का मान

1111 1011₂ = 251

उत्तर

R = 251

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)।

सत्यमान सारणी पंक्ति-दर-पंक्ति

p = 1, r = 1: p → r = 1, ¬r = 0, ¬p = 0, ¬r → ¬p = 1, (p → r) ↔ (¬r → ¬p) = 1

p = 1, r = 0: p → r = 0, ¬r = 1, ¬p = 0, ¬r → ¬p = 0, (p → r) ↔ (¬r → ¬p) = 1

p = 0, r = 1: p → r = 1, ¬r = 0, ¬p = 1, ¬r → ¬p = 1, (p → r) ↔ (¬r → ¬p) = 1

p = 0, r = 0: p → r = 1, ¬r = 1, ¬p = 1, ¬r → ¬p = 1, (p → r) ↔ (¬r → ¬p) = 1

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

(p → r) ↔ (¬r → ¬p): 1, 1, 1, 1

हर पंक्ति में 1: पुनरुक्ति।

उत्तर

पुनरुक्ति

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

उत्तर: N = 6

सत्यमान सारणियाँ: n अलग-अलग चरों वाले सूत्र की 2ⁿ पंक्तियाँ होती हैं, सत्यमानों के हर संयोजन के लिए एक (1 = सत्य, 0 = असत्य)। भीतर से बाहर की ओर काम करें और हर उप-सूत्र को अपना स्तंभ दें। ¬a मान उलट देता है; a ∧ b केवल तब 1 होता है जब दोनों 1 हों; a ∨ b केवल तब 0 होता है जब दोनों 0 हों; a → b केवल तब 0 होता है जब a = 1 और b = 0; a ↔ b तब 1 होता है जब दोनों पक्ष बराबर हों।

स्तंभ

¬d; ¬a; ¬d ↔ ¬a; ¬(¬d ↔ ¬a); b → ¬(¬d ↔ ¬a); ¬c; ¬c ∨ ¬a; b ∨ c; (¬c ∨ ¬a) ∧ (b ∨ c); (b → ¬(¬d ↔ ¬a)) ↔ ((¬c ∨ ¬a) ∧ (b ∨ c))

a पर बाँटें

a = 1: 2

a = 0: 4

N = 2 + 4 = 6

उत्तर

N = 6

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

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

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

हर 1 के पड़ोसी

पड़ोसी 1 वाला 1 दो या अधिक के समूह में शामिल हो सकता है।

m5: m4, m7, m1, m13 → 0

अकेला 1

m5 = A′BC′D → AB = 01, CD = 01

उत्तर

AB = 01, CD = 01

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

उत्तर: Q = 14

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

हर कोर के बाद की अवस्था

1100 → 0110 → 1011 → 0101 → 1010 → 1101 → 1110

दशमलव मान

1110₂ = 14

उत्तर

Q = 14

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

उत्तर: φ(65) = 48

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

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

65 = 5·13

टोशेंट

φ(65) = φ(5)·φ(13) = 4·12 = 48

उत्तर

φ(65) = 48

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

उत्तर: x = 18

gcd से भाग दें

gcd(22, 42) = 2

11x ≡ 9 (mod 21)

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

11⁻¹ ≡ 2 (mod 21) → x ≡ 18 (mod 21)

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

x ∈ {18, 39}

घात

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

विषम शीर्ष

यूलर परिपथ

उत्तर

यूलर परिपथ

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

उत्तर: कोर AC

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

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

1. DF (15)

2. DE (18)

3. CE (2)

4. AC (1)

5. AB (8)

थ्रूपुट ≤ विंडो / RTT = 65,536 × 8 बिट / 0.1 s ≈ 5.2 Mbit/s, लिंक कितना भी तेज़ हो।

उत्तर

D · लगभग 5 Mbit/s

19.IPv4 सबनेटिंग

उत्तर: H = 510

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.254.0 = /23

उपयोगी होस्ट

2⁹ − 2 = 510

उत्तर

H = 510

20.IPv4 सबनेटिंग

उत्तर: p = 21

रूट सारांशीकरण: सारांश रूट a.b.c.0/p उन सभी नेटवर्कों को कवर करता है जिनके पहले p बिट मेल खाते हैं। पहले और अंतिम नेटवर्क के भिन्न ऑक्टेट को बाइनरी में लिखें; साझा अग्रणी बिटों की संख्या, उससे पहले के ऑक्टेटों के बिट जोड़कर, सबसे लंबा सारांश उपसर्ग है।

बिटों की तुलना करें

26 = 00011010

29 = 00011101

साझा अग्रणी बिट: 5

उपसर्ग लंबाई

p = 16 + 5 = 21

उत्तर

p = /21

सारांश रूट: 10.98.24.0/21 (यह 4 ऐसे नेटवर्क भी कवर करता है जो सूची में नहीं हैं)।

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