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

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

N = −1088 bit

U =

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

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

512 × 512 px24 bit/px1 KiB = 1024 B

M = KiB

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

कौन-सा सूत्र a → c के तार्किक रूप से तुल्य है? उस पर क्लिक करें।

a → c

1¬c ∧ ¬a
2¬a → ¬c
3c → a
4¬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-मानचित्र और फ़्लिप-फ़्लॉपमध्यम

F(A, B, C) = Σm(1, 6, 7) का न्यूनतम योगों का गुणनफल (POS) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कितने योग पद (गुणक) N हैं?

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

N =

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

एक 50 kHz क्लॉक mod-100 काउंटर को चलाती है। इसके सबसे महत्वपूर्ण निर्गत की आवृत्ति f_out ज्ञात करें, जो हर गिनती चक्र में एक चक्र पूरा करता है।

f_clk = 50 kHzN = 100

f_out = kHz

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

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

a = 39n = 88

39⁻¹ mod 88 =

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

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

p = 11q = 17e = 13c = 40

m =

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

V शीर्षों और E किनारों वाले ग्राफ़ पर बेलमैन–फ़ोर्ड एल्गोरिदम की टाइम कॉम्प्लेक्सिटी क्या है?

AO(V³ × E)
BO(V × E)
CO(V + E)
DO(E log V)

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

इंसर्शन सॉर्ट सॉर्टेड इनपुट पर O(n) में चलता है। क्या यह तुलना-आधारित सॉर्टिंग की Ω(n log n) निचली सीमा का खंडन करता है?

Aनहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं
Bहाँ, पर केवल 100 से छोटे ऐरे के लिए
Cनहीं, क्योंकि इंसर्शन सॉर्ट तुलना-आधारित सॉर्ट नहीं है
Dहाँ, इसलिए निचली सीमा ग़लत है

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

पोस्टफ़िक्स एक्सप्रेशन 3 4 + 2 * का मान क्या है?

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

ट्रैवर्सलों का कौन-सा युग्म भिन्न कुंजियों वाले एक अद्वितीय बाइनरी ट्री को हमेशा निर्धारित करता है?

Aप्रीऑर्डर और पोस्टऑर्डर
Bकेवल प्रीऑर्डर
Cकेवल लेवल-ऑर्डर
Dप्रीऑर्डर और इनऑर्डर

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

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

2 × deg 34 × deg 42 × deg 2

L =

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

लंबाई 2 की कितनी वॉक A से E तक जाती हैं? वॉक में शीर्ष और कोरें दोहराई जा सकती हैं। संख्या को N कहें।

M = संलग्नता आव्यूहL = 2

N =

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

जिस ग्राहक का phone NULL है, उसके लिए SELECT COALESCE(phone, 'unknown') FROM customers क्या लौटाता है?

Aएक ख़ाली स्ट्रिंग
BNULL
C'unknown'
Dएक त्रुटि

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

एक टेबल में दस लाख पंक्तियाँ हैं और एक Boolean कॉलम is_active है जो उनमें से 95% के लिए TRUE है। WHERE is_active = TRUE के लिए ऑप्टिमाइज़र is_active पर इंडेक्स को अनदेखा क्यों कर सकता है?

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

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

"ping" कमांड किस प्रोटोकॉल का उपयोग करता है?

AUDP
BHTTP
CICMP
DTCP

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

स्लाइडिंग-विंडो प्रोटोकॉल में, एक फ़्रेम खोने के बाद Go-Back-N, Selective Repeat से कैसे भिन्न है?

Aदोनों शुरुआत से पूरी विंडो फिर से भेजते हैं
BGo-Back-N केवल खोया फ़्रेम फिर से भेजता है; Selective Repeat वह फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है
CGo-Back-N खोया फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है; Selective Repeat केवल खोया फ़्रेम
Dकोई भी खोए फ़्रेम कभी फिर से नहीं भेजता

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

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

255.255.255.240

H =

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

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

10.124.141.0/24 … 10.124.143.0/24

p =

3विलयन

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

उत्तर: U = 148

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

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

108 = 0110 1100

उलटा हुआ: 1001 0011

+1 → 1001 0100

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

1001 0100₂ = 256 − 108 = 148

उत्तर

U = 148

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

उत्तर: M = 768 KiB

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

बिट और बाइट

512·512·24 = 6291456 bit = 786432 B

KiB में बदलें

786432/1024 = 768 KiB

उत्तर

M = 768 KiB

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

उत्तर: ¬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)।

नियम

निहितार्थ अपने प्रतिधनात्मक ¬b → ¬a के तुल्य होता है, अपने विलोम b → a या व्युत्क्रम ¬a → ¬b के नहीं।

a → c ≡ ¬c → ¬a

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

a = 1, c = 1: 1 | 0 1 1 1

a = 1, c = 0: 0 | 0 1 1 0

a = 0, c = 1: 1 | 0 0 0 1

a = 0, c = 0: 1 | 1 1 1 1

उत्तर

¬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

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

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

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

(B + C)

(A + B′)

(A′ + B)

न्यूनतम POS रूप

F = (B + C)(A + B′)(A′ + B)

N = 3

उत्तर

N = 3

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

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

उत्तर: f_out = 0.5 kHz

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

आवृत्ति विभाजन

f_out = 50 kHz / 100 = 0.5 kHz

उत्तर

f_out = 0.5 kHz

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

उत्तर: 39⁻¹ mod 88 = 79

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

r = 88, t = 0

r = 39, q = 2, t = 1

r = 10, q = 3, t = −2

r = 9, q = 1, t = 7

r = 1, q = 9, t = −9

व्युत्क्रम

1 ≡ −9·39 (mod 88)

x = 79

जाँच: 39·79 = 3081 = 35·88 + 1

उत्तर

39⁻¹ mod 88 = 79

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

उत्तर: m = 160

मॉड्यूलर घात और 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 = 187, φ(n) = 160

d = 13⁻¹ mod 160 = 37

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

37 = 32 + 4 + 1

40¹ ≡ 40 (mod 187)

40² ≡ 104 (mod 187)

40⁴ ≡ 157 (mod 187)

40⁸ ≡ 152 (mod 187)

40¹⁶ ≡ 103 (mod 187)

40³² ≡ 137 (mod 187)

40³⁷ ≡ 40·157·137 ≡ 160 (mod 187)

संदेश

m = 160

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

L + 26 = 2(L + 8) − 2

L = 12

उत्तर

L = 12

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

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

उत्तर: N = 1

घात: किसी शीर्ष की घात उससे मिलने वाली कोरों की संख्या है। हर कोर के दो सिरे होते हैं, इसलिए घातों का योग कोरों की संख्या का दोगुना होता है: Σ deg(v) = 2|E| (हैंडशेक लेमा)। अतः विषम घात वाले शीर्षों की संख्या सम होती है। K_n में n(n − 1)/2 कोरें होती हैं, n शीर्षों पर k-नियमित ग्राफ़ में nk/2, और n शीर्षों वाले वृक्ष में n − 1 कोरें।

संलग्नता आव्यूह

A: 0 0 1 0 0

B: 0 0 1 1 1

C · Go-Back-N खोया फ़्रेम और उसके बाद के सभी फ़्रेम फिर से भेजता है; Selective Repeat केवल खोया फ़्रेम

19.IPv4 सबनेटिंग

उत्तर: H = 14

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.255.240 = /28

उपयोगी होस्ट

2⁴ − 2 = 14

उत्तर

H = 14

20.IPv4 सबनेटिंग

उत्तर: p = 22

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

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

141 = 10001101

143 = 10001111

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

उपसर्ग लंबाई

p = 16 + 6 = 22

उत्तर

p = /22

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

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