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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 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-बिट पैटर्न 1001 1011 दो के पूरक में एक चिह्नित पूर्णांक संग्रहीत करता है। दशमलव में इसका मान N क्या है?

1001 10118 bit

N =

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

एक प्रणाली को 3693 वस्तुओं में से हर एक को समान लंबाई का अपना द्विआधारी कोड देना है। कम से कम कितनी बिटें b चाहिए?

3693

b = bit

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

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

r → (r ∨ q)

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

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

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

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

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

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

F = B′C′ + ABC′ + AB′ को उसके न्यूनतम गुणनफलों के योग रूप में सरल करें। सरल किए गए व्यंजक में कितने लिटरल L हैं?

F = B′C′ + ABC′ + AB′

L =

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

एक तुल्यकालिक mod-12 काउंटर 0, 1, …, 11 गिनता है और फिर 0 पर लौटता है। यह 10 से शुरू होता है। 18 क्लॉक पल्स के बाद वह कौन-सी गिनती Q (दशमलव में) दिखाएगा?

Q₀ = 1018N = 12

Q =

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

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

a = 27n = 47

27⁻¹ mod 47 =

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

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

p = 43q = 47e = 13

d =

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

क्विकसॉर्ट हमेशा पहले तत्व को पिवट के रूप में उपयोग करता है। किस इनपुट पर यह अपना वर्स्ट-केस व्यवहार दिखाता है?

Aयादृच्छिक क्रम वाला ऐरे
Bऐसा ऐरे जिसके सभी तत्व भिन्न हैं
Cएक ऐरे जो पहले से सॉर्टेड है
Dलंबाई 2 का ऐरे

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

कुक–लेविन प्रमेय ने क्या स्थापित किया?

Aहर NP समस्या घातांकी समय में हल हो सकती है
Bबूलियन संतुष्टि समस्या (SAT) NP-complete है
CP, NP के बराबर नहीं है
Dहॉल्टिंग समस्या अनिर्णेय (undecidable) है

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

डेप्थ-फ़र्स्ट सर्च (पुनरावृत्त संस्करण) किस डेटा संरचना का उपयोग करती है?

Aकेवल हैश टेबल
Bहीप
Cक्यू
Dस्टैक

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

एक AVL नोड असंतुलित है क्योंकि उसके बाएँ चाइल्ड का दायाँ सबट्री बहुत ऊँचा हो गया (left-right स्थिति)। कौन-सा सुधार लागू होता है?

Aबाएँ चाइल्ड पर दायाँ रोटेशन, फिर नोड पर बायाँ रोटेशन
Bबाएँ चाइल्ड पर बायाँ रोटेशन, फिर नोड पर दायाँ रोटेशन
Cनोड पर एक एकल बायाँ रोटेशन
Dनोड पर एक एकल दायाँ रोटेशन

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

एक संबद्ध ग्राफ़ में 10 शीर्ष और 16 कोरें हैं। स्पैनिंग ट्री बचाने के लिए कितनी कोरें k हटानी होंगी?

|V| = 10|E| = 16

k =

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

डाइक्स्ट्रा का एल्गोरिथ्म A से चलता है। उस शीर्ष पर क्लिक करें जो चक्र 4 में निर्धारित (स्थायी) होता है; A स्वयं चक्र 1 है।

प्रारंभ: Aचक्र 4

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

orders टेबल में 5 पंक्तियाँ हैं, हर एक किसी मौजूदा ग्राहक को संदर्भित करती है। customers टेबल में 3 पंक्तियाँ हैं। customer_id पर INNER JOIN कितनी पंक्तियाँ लौटाता है?

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

SELECT day, SUM(amount) OVER (ORDER BY day) FROM sales क्या गणना करता है?

Aप्रति दिन एक पंक्ति, केवल उस दिन के योग के साथ
Bहर पंक्ति पर सभी amounts का योग
Cप्रति दिन औसत amount
Dday के अनुसार क्रमबद्ध amount का चलता योग (running total)

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

एक ब्राउज़र को HTTP स्टेटस कोड 404 मिलता है। इसका क्या अर्थ है?

Aसर्वर में आंतरिक त्रुटि हुई
Bअनुरोधित संसाधन नहीं मिला
Cक्लाइंट को पहले लॉग इन करना होगा
Dअनुरोध सफल रहा

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

TCP/IP मॉडल में कौन-सी परत पोर्ट नंबर जोड़ती है?

Aइंटरनेट परत
Bलिंक परत
Cट्रांसपोर्ट परत
Dएप्लिकेशन परत

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

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

255.255.255.240

H =

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

नेटवर्क 192.168.112.0/24 को इन LAN के लिए VLSM से बाँटा जाता है: A: 24 होस्ट, B: 25 होस्ट, C: 3 होस्ट, D: 77 होस्ट। सबनेट .0 से ऊपर की ओर आवंटित किए जाते हैं, सबसे अधिक होस्ट वाला LAN पहले, हर एक को सबसे छोटा फ़िट होने वाला सबनेट। LAN C के नेटवर्क पते का चौथा ऑक्टेट x क्या है?

A: 24B: 25C: 3D: 77

x =

3विलयन

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

उत्तर: N = −101

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

मान जोड़ें

बाकी बिटें अपने सामान्य धनात्मक मान रखती हैं।

−128 + 16 + 8 + 2 + 1 = −101

उत्तर

N = −101

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

उत्तर: b = 12 bit

दो की घातें

2¹¹ = 2048 < 3693

2¹² = 4096 ≥ 3693

उत्तर

b = 12

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

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

q = 1, r = 1: r ∨ q = 1, r → (r ∨ q) = 1

q = 1, r = 0: r ∨ q = 1, r → (r ∨ q) = 1

q = 0, r = 1: r ∨ q = 1, r → (r ∨ q) = 1

q = 0, r = 0: r ∨ q = 0, r → (r ∨ q) = 1

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

r → (r ∨ q): 1, 1, 1, 1

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

उत्तर

पुनरुक्ति

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

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

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

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

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

उत्तर

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

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

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

उत्तर: L = 6

बूलीय बीजगणित: व्यंजकों को सरल करने वाले नियम हैं X + X′ = 1 और X·X′ = 0, X + X = X, अवशोषण X + X·Y = X, संयोजन नियम X·Y + X·Y′ = X, X + X′Y = X + Y और सहमति प्रमेय XY + X′Z + YZ = XY + X′Z। डी मॉर्गन के नियम (X·Y)′ को X′ + Y′ में और (X + Y)′ को X′·Y′ में बदलते हैं। कार्नो मानचित्र इन नियमों को चित्रात्मक रूप से लगाता है: दो पड़ोसी खानों का हर समूह XY + XY′ = X का एक उपयोग है।

व्यंजक के मिनटर्म

B′C′ → m(0, 4)

ABC′ → m(6)

AB′ → m(4, 5)

समूहित करें और पढ़ें

F = B′C′ + AC′ + AB′

लिटरल गिनें

L = 6

उत्तर

L = 6

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

उत्तर: Q = 4

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

पूरे चक्र

हर 12 पल्स काउंटर को उसी अवस्था में वापस ले आते हैं।

18 = 1·12 + 6

शेष पल्स के बाद गिनती

Q = (10 + 6) mod 12 = 4

Q = 0100₂

उत्तर

Q = 4

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

उत्तर: 27⁻¹ mod 47 = 7

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

r = 47, t = 0

r = 27, q = 1, t = 1

r = 20, q = 1, t = −1

r = 7, q = 2, t = 2

r = 6, q = 1, t = −5

r = 1, q = 6, t = 7

व्युत्क्रम

1 ≡ 7·27 (mod 47)

x = 7

जाँच: 27·7 = 189 = 4·47 + 1

उत्तर

27⁻¹ mod 47 = 7

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

उत्तर: d = 1189

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

φ(n) = 42·46 = 1932

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

r = 1932, t = 0

r = 13, q = 148, t = 1

r = 8, q = 1, t = −148

r = 5, q = 1, t = 149

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

r = 2, q = 1, t = 446

r = 1, q = 2, t = −743

निजी घातांक

d = 1189

स्पैनिंग ट्री की कोरें

10 − 1 = 9

हटाई जाने वाली कोरें

k = 16 − 9 = 7

उत्तर

k = 7

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

उत्तर: B

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

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

1. A (0): B: 11, C: 7

2. C (7): E: 10

3. E (10): D: 13, F: 24

4. B (11)

5. D (13)

TCP और UDP हेडर में स्रोत और गंतव्य पोर्ट होते हैं; इंटरनेट परत (IP) पते जोड़ती है।

उत्तर

C · ट्रांसपोर्ट परत

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 सबनेटिंग

उत्तर: x = 192

VLSM: हर LAN को सबसे छोटा सबनेट मिलता है जिसके लिए 2ʰ − 2 ≥ उसकी होस्ट संख्या, अर्थात उपसर्ग 32 − h। सबसे बड़े सबनेट पहले आवंटित करने से हर ब्लॉक अपने आकार के गुणज पर संरेखित रहता है, इसलिए नेटवर्क पते ब्लॉक आकार जोड़ते जाने से मिलते हैं।

प्रति LAN ब्लॉक आकार

D: 77 होस्ट → 2⁷ = 128 (/25)

B: 25 होस्ट → 2⁵ = 32 (/27)

A: 24 होस्ट → 2⁵ = 32 (/27)

C: 3 होस्ट → 2³ = 8 (/29)

आवंटन, सबसे बड़ा पहले

D: .0 – .127

B: .128 – .159

A: .160 – .191

C: .192 – .199

उत्तर

x = 192

LAN C: 192.168.112.192/29।

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