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

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

N = −258 bit

U =

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

एक असंपीड़ित छवि 1280 × 720 पिक्सेल की है, प्रति पिक्सेल 24 बिट। यह KiB में (1 KiB = 1024 बाइट) कितनी मेमोरी M लेती है?

1280 × 720 px24 bit/px1 KiB = 1024 B

M = KiB

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

कौन-सा सूत्र (p ∨ q) → r के तार्किक रूप से तुल्य है? उस पर क्लिक करें।

(p ∨ q) → r

1(p ∧ q) → r
2(p → r) ∧ (q → r)
3p ∨ (q → r)
4(p → r) ∨ (q → r)

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, D) = Σm(1, 6, 7, 9, 10, 11, 15) का न्यूनतम गुणनफलों का योग (SOP) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कितने गुणन पद N हैं?

F(A, B, C, D) = Σm(1, 6, 7, 9, 10, 11, 15)

N =

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

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

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

Q =

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

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

a = 16n = 53

16⁻¹ mod 53 =

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

एक RSA कुंजी अभाज्य p = 13 और q = 47 तथा सार्वजनिक घातांक e = 19 का उपयोग करती है। निजी घातांक d ज्ञात करें (0 < d < φ(n))।

p = 13q = 47e = 19

d =

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

आप n तत्वों का ऐरे एक बार सॉर्ट करते हैं और फिर बाइनरी सर्च से k सदस्यता प्रश्नों के उत्तर देते हैं। कुल लागत क्या है?

AO(n + k)
BO(nk)
CO(k n log n)
DO(n log n + k log n)

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

P और NP के बारे में कौन-सा कथन सही है?

Aयह सिद्ध हो चुका है कि P ≠ NP
BNP समस्याओं को जल्दी सत्यापित नहीं किया जा सकता
CNP का अर्थ है "not polynomial"
DP की हर समस्या NP में भी है

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

n तत्वों के ऐरे के बीच में एक तत्व डालने की लागत क्या है?

AO(n²), क्योंकि हर तत्व n बार खिसकता है
BO(1), क्योंकि इंडेक्स ज्ञात है
CO(log n), बाइनरी सर्च के कारण
DO(n), क्योंकि बाद के तत्वों को खिसकना पड़ता है

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

ऐरे के हर तत्व के लिए आप उसके दाईं ओर का अगला बड़ा तत्व कुल O(n) समय में चाहते हैं। कौन-सी संरचना मदद करती है?

Aतत्वों के हर युग्म को रखने वाली क्यू
Bसभी तत्वों की हैश टेबल
Cएक स्टैक जो उत्तर की प्रतीक्षा कर रहे तत्वों को रखता है
Dहर तत्व के लिए फिर से बनाया गया बाइनरी सर्च ट्री

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

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

|V| = 5|E| = 7

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

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

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

|V| = 6|E| = 9

W =

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

ACID में "A" का क्या अर्थ है?

Aएकत्रीकरण (Aggregation)
Bशुद्धता (Accuracy)
Cपरमाणुता (Atomicity)
Dउपलब्धता (Availability)

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

मल्टीवर्ज़न कॉन्करेंसी कंट्रोल (MVCC) के साथ रीडर राइटरों को अवरुद्ध करने से कैसे बच सकते हैं?

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

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

HTTP स्टेटलेस है। वेबसाइटें अनुरोधों के बीच उपयोगकर्ता को आमतौर पर लॉग इन कैसे रखती हैं?

ATCP कनेक्शन को कई दिनों तक खुला रखकर
Bसेशन पहचानकर्ता या टोकन रखने वाली कुकीज़ से
Cहर उपयोगकर्ता को एक निश्चित IP पता देकर
Dपासवर्ड को URL में संग्रहित करके

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

TCP कंजेशन कंट्रोल का "slow start" चरण:

Aपैकेट हानि का पता चलने तक हर राउंड ट्रिप में कंजेशन विंडो को आधा कर देता है
Bकेवल UDP द्वारा उपयोग किया जाता है
Cसीमा (threshold) या हानि होने तक कंजेशन विंडो को घातांकीय रूप से बढ़ाता है
Dविंडो को एक सेगमेंट पर स्थिर रखता है

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

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

1780 hosts

p =

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

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

172.20.53.24/22

x =

3विलयन

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

उत्तर: U = 231

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

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

25 = 0001 1001

उलटा हुआ: 1110 0110

+1 → 1110 0111

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

1110 0111₂ = 256 − 25 = 231

उत्तर

U = 231

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

उत्तर: M = 2700 KiB

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

बिट और बाइट

1280·720·24 = 22118400 bit = 2764800 B

KiB में बदलें

2764800/1024 = 2700 KiB

उत्तर

M = 2700 KiB

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

उत्तर: (p → r) ∧ (q → r)

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

(p ∨ q) → r ≡ (p → r) ∧ (q → r)

सत्यमान सारणी से जाँच

p = 1, q = 1, r = 1: 1 | 1 1 1 1

p = 1, q = 1, r = 0: 0 | 0 0 1 0

p = 1, q = 0, r = 1: 1 | 1 1 1 1

p = 1, q = 0, r = 0: 0 | 1 0 1 1

p = 0, q = 1, r = 1: 1 | 1 1 1 1

p = 0, q = 1, r = 0: 0 | 1 0 0 1

p = 0, q = 0, r = 1: 1 | 1 1 1 1

p = 0, q = 0, r = 0: 1 | 1 1 1 1

उत्तर

(p → r) ∧ (q → r)

पट्टी के बाद के स्तंभ विकल्प हैं, दिखाए गए क्रम में।

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

उत्तर: N = 4

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

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

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

B′C′D

BCD

A′BC

AB′C

न्यूनतम SOP रूप

F = B′C′D + BCD + A′BC + AB′C

N = 4

उत्तर

N = 4

उसी आकार का एक और समूहन संभव है; उसमें पदों और लिटरलों की संख्या वही है।

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

उत्तर: Q = 11

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

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

0100 → 1010 → 1101 → 0110 → 1011

दशमलव मान

1011₂ = 11

उत्तर

Q = 11

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

उत्तर: 16⁻¹ mod 53 = 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)।

विस्तारित यूक्लिडीय एल्गोरिथ्म

हर शेषफल r को r ≡ t·16 (mod 53) के रूप में लिखा जाता है।

r = 53, t = 0

r = 16, q = 3, t = 1

r = 5, q = 3, t = −3

r = 1, q = 5, t = 10

व्युत्क्रम

1 ≡ 10·16 (mod 53)

x = 10

जाँच: 16·10 = 160 = 3·53 + 1

उत्तर

16⁻¹ mod 53 = 10

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

उत्तर: d = 523

मॉड्यूलर घात और 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 = 13·47 = 611

φ(n) = 12·46 = 552

विस्तारित यूक्लिडीय एल्गोरिथ्म

r = 552, t = 0

r = 19, q = 29, t = 1

r = 1, q = 19, t = −29

निजी घातांक

d = 523

घात

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

विषम शीर्ष

C, E → 2

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

उत्तर

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

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

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

उत्तर: W = 24

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

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

CE (2): लें

EF (3): लें

BD (5): लें

C · सीमा (threshold) या हानि होने तक कंजेशन विंडो को घातांकीय रूप से बढ़ाता है

19.IPv4 सबनेटिंग

उत्तर: p = 21

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

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

2¹⁰ − 2 = 1022 < 1780

2¹¹ − 2 = 2046 ≥ 1780 → h = 11

उपसर्ग लंबाई

p = 32 − 11 = 21

उत्तर

p = /21

20.IPv4 सबनेटिंग

उत्तर: x = 55

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² = 4

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

नेटवर्क: 172.20.52.0

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

उत्तर

x = 55

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