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

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

N = −488 bit

U =

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

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

0011 0011OR1011 1101

R =

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

आप ¬r → (q ∨ p) को प्रतिधनात्मक द्वारा सिद्ध करना चाहते हैं। इसके बजाय कौन-सा निहितार्थ सिद्ध करेंगे? उस पर क्लिक करें।

¬r → (q ∨ p)

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

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

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

¬∀x (P(x) → ∃y R(x, y))

1∀x (P(x) ∧ ∀y ¬R(x, y))
2∃x (¬P(x) ∧ ∃y R(x, y))
3∃x (P(x) → ∀y ¬R(x, y))
4∃x (P(x) ∧ ∀y ¬R(x, y))

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

F(A, B, C, D) = Σm(1, 2, 3, 5, 6, 8, 9, 10, 11, 12, 14) का न्यूनतम गुणनफलों का योग (SOP) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कितने गुणन पद N हैं?

F(A, B, C, D) = Σm(1, 2, 3, 5, 6, 8, 9, 10, 11, 12, 14)

N =

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

F(A, B, C, D) = Σm(0, 3, 5, 8, 10, 15) + d(1, 2, 4, 12, 14) के लिए, जहाँ d डोंट-केयर स्थितियों को दर्शाता है, अनिवार्य प्रमुख प्रभाव्यों (एसेंशियल प्राइम इम्प्लिकेंट) की संख्या N ज्ञात करें।

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

N =

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

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

n = 133 = 7·19

φ(133) =

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

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

p = 11q = 41e = 13c = 181

m =

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

एक फ़ंक्शन n इटरेशन का एक लूप चलाता है और फिर, अलग से, n इटरेशन का एक और लूप। इसकी टाइम कॉम्प्लेक्सिटी क्या है?

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

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

जब कुछ किनारा भार ऋणात्मक हों, तो डाइकस्ट्रा का एल्गोरिदम ग़लत परिणाम क्यों दे सकता है?

Aप्रायोरिटी क्यू में ऋणात्मक संख्याएँ संग्रहीत नहीं की जा सकतीं
Bयह केवल अप्रत्यक्ष (undirected) ग्राफ़ पर काम करता है
Cशीर्ष निकाले जाने पर अंतिम मान लिया जाता है, पर बाद का कोई ऋणात्मक किनारा उसे अब भी छोटा पथ दे सकता है
Dयह हर ऋणात्मक किनारे पर अनंत लूप में चला जाता है

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

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

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

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

ओपन एड्रेसिंग वाली हैश टेबल में डिलीशन अक्सर "टॉम्बस्टोन" चिह्न से क्यों किया जाता है?

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

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

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

4 × deg 33 × deg 44 × deg 2

L =

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

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

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

d(F) =

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

एक टेबल में केवल एक क्लस्टर्ड इंडेक्स क्यों हो सकता है?

Aक्लस्टर्ड इंडेक्स केवल प्राइमरी की पर हो सकते हैं
BSQL मानक किसी टेबल पर एक से अधिक इंडेक्स की अनुमति नहीं देता
Cक्लस्टर्ड इंडेक्स बहुत अधिक मेमोरी उपयोग करते हैं
Dपंक्तियाँ भौतिक रूप से केवल एक क्रम में संग्रहित की जा सकती हैं

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

write-ahead logging (WAL) नियम क्या अपेक्षा करता है?

Aकिसी परिवर्तन का लॉग रिकॉर्ड बदले गए डेटा पेज से पहले स्थिर भंडारण तक पहुँचना चाहिए
Bलॉग केवल क्रैश के बाद लिखा जाता है
Cहर क्वेरी पार्स होने से पहले लॉग होनी चाहिए
Dडेटा पेज लॉग से पहले लिखे जाने चाहिए

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

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

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

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

TCP कनेक्शन में रिसीव विंडो (rwnd) किसे नियंत्रित करती है?

Aप्रत्येक IP पैकेट हेडर का आकार
Bपुनःप्रेषण टाइम-आउट, जिसकी गणना हर सेगमेंट के मापे गए राउंड-ट्रिप समय से होती है
Cखुले पोर्टों की संख्या
Dप्राप्तकर्ता के बफ़र के आधार पर प्रेषक कितना बिना पावती वाला डेटा भेज सकता है

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

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

192.168.10.0/246 subnets

H =

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

एक होस्ट का पता 10.20.153.81/29 है। उसके सबनेट के ब्रॉडकास्ट पते की अंतिम संख्या (चौथा ऑक्टेट) x क्या है?

10.20.153.81/29

x =

3विलयन

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

उत्तर: U = 208

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

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

48 = 0011 0000

उलटा हुआ: 1100 1111

+1 → 1101 0000

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

1101 0000₂ = 256 − 48 = 208

उत्तर

U = 208

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

उत्तर: R = 191

बिट-दर-बिट

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

0011 0011

OR 1011 1101

= 1011 1111

परिणाम का मान

1011 1111₂ = 191

उत्तर

R = 191

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

उत्तर: ¬(q ∨ p) → ¬¬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 = ¬r, b = q ∨ p

प्रतिधनात्मक

¬b → ¬a = ¬(q ∨ p) → ¬¬r

उत्तर

¬(q ∨ p) → ¬¬r

प्रतिधनात्मक मूल कथन के तुल्य है, इसलिए उसे सिद्ध करने से कथन सिद्ध हो जाता है।

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

उत्तर: ∃x (P(x) ∧ ∀y ¬R(x, y))

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

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

¬∀x (P(x) → ∃y R(x, y)) ≡ ∃x (P(x) ∧ ∀y ¬R(x, y))

उत्तर

∃x (P(x) ∧ ∀y ¬R(x, y))

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

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

उत्तर: N = 4

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

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

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

CD′

B′D

AD′

A′C′D

न्यूनतम SOP रूप

F = CD′ + B′D + AD′ + A′C′D

N = 4

उत्तर

N = 4

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

उत्तर: N = 3

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

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

C′D′, B′D′, AD′, A′C′, A′B′, ABC

अनिवार्य प्रमुख प्रभाव्य

A′C′, A′B′, ABC

N = 3

उत्तर

N = 3

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

उत्तर: φ(133) = 108

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

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

133 = 7·19

टोशेंट

φ(133) = φ(19)·φ(7) = 18·6 = 108

उत्तर

φ(133) = 108

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

उत्तर: m = 322

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

d = 13⁻¹ mod 400 = 277

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

277 = 256 + 16 + 4 + 1

181¹ ≡ 181 (mod 451)

181² ≡ 289 (mod 451)

181⁴ ≡ 86 (mod 451)

181⁸ ≡ 180 (mod 451)

181¹⁶ ≡ 379 (mod 451)

181³² ≡ 223 (mod 451)

181⁶⁴ ≡ 119 (mod 451)

181¹²⁸ ≡ 180 (mod 451)

181²⁵⁶ ≡ 379 (mod 451)

181²⁷⁷ ≡ 181·86·379·379 ≡ 322 (mod 451)

संदेश

m = 322

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

L + 32 = 2(L + 11) − 2

L = 12

उत्तर

L = 12

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

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

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

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

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

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

A (0): B: 2, C: 15

B (2): C: 6, D: 11

C (6): E: 17

D (11): E: 13, F: 22

E (13): F: 16

F (16)

सबसे छोटा पथ

A → B → D → E → F

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

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

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

2⁵ − 2 = 30

उत्तर

H = 30

20.IPv4 सबनेटिंग

उत्तर: x = 87

ब्लॉक आकार

2³ = 8

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

नेटवर्क: ⌊81/8⌋·8 = 80

ब्रॉडकास्ट: 80 + 8 − 1 = 87

उपयोगी होस्ट: 81 … 86

उत्तर

x = 87

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