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

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

N = −938 bit

U =

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

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

4138

b = bit

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

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

(q → p) ↔ (p → q)

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

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

आधार-वाक्य q ∨ r; q और निष्कर्ष ¬r वाला तर्क अवैध है। सत्यमान सारणी की उस पंक्ति पर क्लिक करें जो प्रति-उदाहरण है।

q ∨ rq∴ ¬r

1q = 1, r = 1
2q = 1, r = 0
3q = 0, r = 1
4q = 0, r = 0

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

F(A, B, C, D) = Σm(2, 5, 6, 10, 12, 14) का न्यूनतम गुणनफलों का योग (SOP) रूप कार्नो मानचित्र से ज्ञात करें। उसमें कुल कितने लिटरल L हैं (प्राइम वाला चर एक लिटरल गिना जाता है)?

F(A, B, C, D) = Σm(2, 5, 6, 10, 12, 14)

L =

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

F(A, B, C, D) = Σm(0, 4, 5, 6, 9, 11) + d(12, 13) का न्यूनतम SOP रूप ज्ञात करें, जहाँ d डोंट-केयर स्थितियों को दर्शाता है। उसमें कितने गुणन पद N हैं?

F(A, B, C, D) = Σm(0, 4, 5, 6, 9, 11) + d(12, 13)

N =

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

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

n = 169 = 13²

φ(169) =

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

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

p = 29q = 41e = 23

d =

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

कई लाइब्रेरी सॉर्टिंग रूटीन बहुत छोटे सबऐरे के लिए इंसर्शन सॉर्ट पर क्यों चली जाती हैं?

Aरिकर्सिव एल्गोरिदम 10 से कम तत्वों वाले ऐरे नहीं सँभाल सकते
Bइंसर्शन सॉर्ट वर्स्ट केस में O(n log n) है
Cबड़े इनपुट पर इंसर्शन सॉर्ट किसी भी अन्य सॉर्टिंग एल्गोरिदम से कम मेमोरी उपयोग करता है
Dइंसर्शन सॉर्ट का ओवरहेड कम है और यह छोटे या लगभग सॉर्टेड इनपुट पर तेज़ है

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

रिकरेंस T(n) = 2T(n/2) + n log n का हल क्या है?

AΘ(n²)
BΘ(n)
CΘ(n log² n)
DΘ(n log n)

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

एक बाइनरी ट्री का रूट 1 है, जिसका बायाँ चाइल्ड 2 और दायाँ चाइल्ड 3 है; नोड 2 के चाइल्ड 4 (बायाँ) और 5 (दायाँ) हैं। प्रीऑर्डर ट्रैवर्सल क्या है?

A1 2 4 5 3
B4 2 5 1 3
C4 5 2 3 1
D1 2 3 4 5

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

टोपोलॉजिकल सॉर्टिंग के लिए कान का एल्गोरिदम बार-बार in-degree 0 वाले शीर्ष हटाता है। उन शीर्षों को कौन-सी संरचना रखती है?

Aएक एडजेसेंसी मैट्रिक्स जो दर्ज करे कि कौन-से शीर्ष पहले ही हटाए जा चुके हैं
Bout-degree के अनुसार क्रमित मैक्स-हीप
Cin-degree 0 वाले शीर्षों की एक क्यू (या कोई भी संग्रह)
Dसभी देखे गए किनारों का स्टैक

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

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

4 × deg 32 × deg 42 × deg 54 × deg 2

L =

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

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

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

N =

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

एक फ़ॉरेन की ON DELETE CASCADE के साथ घोषित है। पैरेंट पंक्ति हटाने पर क्या होता है?

Aपैरेंट पंक्ति एक आर्काइव टेबल में कॉपी हो जाती है
Bहटाना हमेशा अस्वीकार हो जाता है
Cउसे संदर्भित करने वाली चाइल्ड पंक्तियाँ स्वतः हट जाती हैं
Dचाइल्ड पंक्तियों की फ़ॉरेन की अपने आप NULL हो जाती है

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

बिना उपयोगी इंडेक्स वाली दो बड़ी टेबलों के बीच समता जॉइन के लिए ऑप्टिमाइज़र अक्सर कौन-सा जॉइन एल्गोरिदम चुनता है?

Aहैश जॉइन
Bक्रॉस जॉइन
Cप्राइमरी की पर बिटमैप जॉइन
Dइंडेक्स लुकअप के साथ नेस्टेड लूप जॉइन

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

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

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

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

IPv4 की तुलना में IPv6 में विखंडन (fragmentation) कैसे भिन्न है?

Aराउटर IPv6 पैकेटों को कभी विखंडित नहीं करते; केवल स्रोत path MTU discovery का उपयोग करके कर सकता है
BIPv6 राउटर आगे भेजने से पहले 64 बाइट से बड़े हर पैकेट को मार्ग में विखंडित करते हैं
CIPv6 ट्रांसपोर्ट परत पर TCP के भीतर विखंडन करता है
DIPv6 576 बाइट से बड़े पैकेटों की अनुमति नहीं देता

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

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

953 hosts

p =

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

एक होस्ट का पता 10.20.243.141/26 है। उसके सबनेट के अंतिम उपयोगी होस्ट पते का चौथा ऑक्टेट x क्या है?

10.20.243.141/26

x =

3विलयन

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

उत्तर: U = 163

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

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

93 = 0101 1101

उलटा हुआ: 1010 0010

+1 → 1010 0011

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

1010 0011₂ = 256 − 93 = 163

उत्तर

U = 163

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

उत्तर: b = 13 bit

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

दो की घातें

2¹² = 4096 < 4138

2¹³ = 8192 ≥ 4138

उत्तर

b = 13

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, q = 1: q → p = 1, p → q = 1, (q → p) ↔ (p → q) = 1

p = 1, q = 0: q → p = 1, p → q = 0, (q → p) ↔ (p → q) = 0

p = 0, q = 1: q → p = 0, p → q = 1, (q → p) ↔ (p → q) = 0

p = 0, q = 0: q → p = 1, p → q = 1, (q → p) ↔ (p → q) = 1

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

(q → p) ↔ (p → q): 1, 0, 0, 1

4 पंक्तियों में से 2 में 1, बाकी में 0: एक आकस्मिकता (contingency)।

उत्तर

आपातिक कथन

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

उत्तर: q = 1, r = 1

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

आधार-वाक्य और निष्कर्ष पंक्ति-दर-पंक्ति

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

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

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

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

प्रति-उदाहरण

q = 1, r = 1

उत्तर

q = 1, r = 1

इस रूप का तर्क वैध नियम जैसा दिखता है, पर यह दिखाने के लिए कि वह वैध नहीं है, एक पंक्ति काफ़ी है।

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

उत्तर: L = 9

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

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

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

CD′

ABD′

A′BC′D

न्यूनतम SOP रूप

F = CD′ + ABD′ + A′BC′D

L = 9

उत्तर

L = 9

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

उत्तर: N = 4

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

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

BC′, A′C′D′, AC′D, A′BD′, AB′D

न्यूनतम आवरण

F = BC′ + A′C′D′ + A′BD′ + AB′D

N = 4

उत्तर

N = 4

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

उत्तर: φ(169) = 156

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

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

169 = 13²

टोशेंट

φ(169) = 169 − 13 = 156

उत्तर

φ(169) = 156

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

उत्तर: d = 487

मॉड्यूलर घात और 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 = 29·41 = 1189

φ(n) = 28·40 = 1120

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

r = 1120, t = 0

r = 23, q = 48, t = 1

r = 16, q = 1, t = −48

r = 7, q = 2, t = 49

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

r = 1, q = 2, t = 487

निजी घातांक

d = 487

जाँच: 23·487 = 11201 = 10·1120 + 1

उत्तर

d = 487

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

उत्तर: D · इंसर्शन सॉर्ट का ओवरहेड कम है और यह छोटे या लगभग सॉर्टेड इनपुट पर तेज़ है

यह उत्तर क्यों है

छोटे n के लिए इंसर्शन सॉर्ट का सरल लूप क्विकसॉर्ट या मर्ज सॉर्ट के रिकर्शन ओवरहेड को पीछे छोड़ देता है, भले ही वह O(n²) हो।

उत्तर

D · इंसर्शन सॉर्ट का ओवरहेड कम है और यह छोटे या लगभग सॉर्टेड इनपुट पर तेज़ है

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

उत्तर: C · Θ(n log² n)

यह उत्तर क्यों है

स्तर k लगभग n log(n / 2ᵏ) कार्य करता है, और log n स्तरों पर योग Θ(n log² n) देता है, जो मास्टर प्रमेय की विस्तारित दूसरी स्थिति है।

उत्तर

C · Θ(n log² n)

11.डेटा संरचनाएँ

उत्तर: A · 1 2 4 5 3

यह उत्तर क्यों है

प्रीऑर्डर 1, फिर उसका बायाँ सबट्री (2, 4, 5), फिर 3 देखता है; अन्य विकल्प इनऑर्डर, पोस्टऑर्डर और लेवल-ऑर्डर हैं।

उत्तर

A · 1 2 4 5 3

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

उत्तर: C · in-degree 0 वाले शीर्षों की एक क्यू (या कोई भी संग्रह)

यह उत्तर क्यों है

तैयार शीर्ष एक क्यू में रखे जाते हैं; एक को हटाने से उसके पड़ोसियों की in-degree घटती है, और जो 0 तक पहुँचें उन्हें जोड़ दिया जाता है, जिससे O(V + E) समय मिलता है।

उत्तर

C · in-degree 0 वाले शीर्षों की एक क्यू (या कोई भी संग्रह)

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

उत्तर: L = 16

यूलर, हैमिल्टन और वृक्ष: संबद्ध ग्राफ़ में यूलर परिपथ (हर कोर एक बार, शुरुआत पर वापसी) तब होता है जब हर शीर्ष की घात सम हो, और परिपथ न होने वाला यूलर पथ तब जब ठीक दो शीर्षों की घात विषम हो; तब पथ एक विषम शीर्ष से दूसरे तक चलता है। हैमिल्टन परिपथ हर शीर्ष पर एक बार जाता है; K_n में ऐसे (n − 1)!/2 होते हैं। n शीर्षों वाले वृक्ष में n − 1 कोरें होती हैं, और m कोरों वाला संबद्ध ग्राफ़ m − n + 1 कोरें हटाने के बाद स्पैनिंग ट्री रखता है।

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

L + 38 = 2(L + 12) − 2

L = 16

उत्तर

L = 16

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

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

उत्तर: N = 6

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

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

A: 0 1 1 0 0 0

B: 1 0 1 1 0 0

C: 1 1 0 0 1 0

D: 0 1 0 0 1 0

E: 0 0 1 1 0 1

F: 0 0 0 0 1 0

एक कदम और

(M³)_BC = 1·1 + 3·1 + 1·0 + 0·0 + 2·1 + 0·0 = 6

उत्तर

N = 6

15.डेटाबेस और SQL

उत्तर: C · उसे संदर्भित करने वाली चाइल्ड पंक्तियाँ स्वतः हट जाती हैं

यह उत्तर क्यों है

CASCADE हटाने को संदर्भित करने वाली पंक्तियों तक फैलाता है; अन्य विकल्प RESTRICT/NO ACTION (अस्वीकार) और SET NULL हैं।

उत्तर

C · उसे संदर्भित करने वाली चाइल्ड पंक्तियाँ स्वतः हट जाती हैं

16.डेटाबेस और SQL

उत्तर: A · हैश जॉइन

यह उत्तर क्यों है

हैश जॉइन एक इनपुट पर हैश टेबल बनाता है और दूसरे से उसकी जाँच करता है, जो बिना इंडेक्स के बड़े equi-join के लिए अच्छा काम करता है।

उत्तर

A · हैश जॉइन

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

उत्तर: C · सेशन पहचानकर्ता या टोकन रखने वाली कुकीज़ से

यह उत्तर क्यों है

सर्वर सेशन ID या टोकन वाली एक कुकी सेट करता है, और ब्राउज़र उसे हर अनुरोध के साथ लौटाता है ताकि सर्वर उपयोगकर्ता को पहचान सके।

उत्तर

C · सेशन पहचानकर्ता या टोकन रखने वाली कुकीज़ से

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

उत्तर: A · राउटर IPv6 पैकेटों को कभी विखंडित नहीं करते; केवल स्रोत path MTU discovery का उपयोग करके कर सकता है

यह उत्तर क्यों है

IPv6 राउटर बहुत बड़े पैकेट को गिरा देता है और ICMPv6 Packet Too Big लौटाता है। फिर स्रोत छोटे पैकेट भेजता है या fragment extension header का उपयोग करता है।

उत्तर

A · राउटर IPv6 पैकेटों को कभी विखंडित नहीं करते; केवल स्रोत path MTU discovery का उपयोग करके कर सकता है

19.IPv4 सबनेटिंग

उत्तर: p = 22

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

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

2⁹ − 2 = 510 < 953

2¹⁰ − 2 = 1022 ≥ 953 → h = 10

उपसर्ग लंबाई

p = 32 − 10 = 22

उत्तर

p = /22

20.IPv4 सबनेटिंग

उत्तर: x = 190

ब्लॉक आकार

2⁶ = 64

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

नेटवर्क: ⌊141/64⌋·64 = 128

ब्रॉडकास्ट: 128 + 64 − 1 = 191

उपयोगी होस्ट: 129 … 190

उत्तर

x = 190

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