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

सूत्र-पत्रक, हर विषय के मुख्य विधि-चरण और 20 अभ्यास प्रश्न, पूरे हल पीछे दिए गए हैं।

नए प्रश्नकोर्स पर वापस जाएँ

प्रिंट विंडो में “PDF के रूप में सहेजें” चुनें, ताकि एक प्रति आपके डिवाइस पर रहे।

1सूत्र और विधियाँ

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

स्थानीय मान
बाइनरी 2k, ऑक्टल 8k, हेक्स 16k
दशमलव में
Σ dk·bk
दशमलव से
आधार से भाग दें, शेषफल नीचे से ऊपर पढ़ें
हेक्स ↔ बाइनरी
एक हेक्स अंक = 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

विधि

  1. अलग-अलग चरों को गिनें: सत्यमान सारणी में 2ⁿ पंक्तियाँ होती हैं, जो सभी के 1 होने से शुरू होती हैं।
  2. हर उप-सूत्र को अपना अलग स्तंभ दें और स्तंभों को भीतर से बाहर की ओर भरें।
  3. हर संयोजक का नियम लगाएँ: → केवल 1 → 0 के लिए 0 होता है, ↔ तब 1 होता है जब दोनों पक्ष समान हों।
  4. तुल्यता के लिए अंतिम स्तंभों की पंक्ति-दर-पंक्ति तुलना करें; किसी तर्क के लिए केवल उन्हीं पंक्तियों को देखें जिनमें हर आधार-वाक्य 1 हो।
  5. परिमाणक वाले कथन का निषेध करने के लिए ¬ को भीतर ले जाएँ, ∀ और ∃ आपस में बदलें, और भीतरी सूत्र का निषेध करें।

डिजिटल लॉजिक: गेट, 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′I0 + A′BI1 + AB′I2 + ABI3
फ़्लिप-फ़्लॉप
D: Q⁺ = D, T: Q⁺ = T ⊕ Q, JK: Q⁺ = JQ′ + K′Q
काउंटर
n-बिट: 2ⁿ अवस्थाएँ; mod-N: सबसे छोटा n जिसमें 2ⁿ ≥ N; fout = fclk/N
रिपल काउंटर
fmax = 1/(n·tpd)
रिंग और जॉनसन काउंटर
n और 2n अवस्थाएँ

विधि

  1. परिपथ के लिए निवेशों से निर्गत तक एक-एक गेट करके काम करें और हर तार पर मान लिखें, या उसका व्यंजक लिखें और सत्यमान सारणी भरें।
  2. सरलीकरण के लिए 1 (और डोंट-केयर को X के रूप में) को ग्रे-कोड पंक्तियों और स्तंभों वाले कार्नो मानचित्र में रखें: 00, 01, 11, 10।
  3. 1 को 1, 2, 4, 8 या 16 खानों के जितने कम और जितने बड़े संभव हों उतने समूहों से ढकें, किनारों से लिपटते हुए; हर समूह एक गुणन पद है जो उन चरों से बना है जो स्थिर रहते हैं। POS रूप के लिए 0 को समूहित करें।
  4. फ़्लिप-फ़्लॉप और काउंटरों के लिए हर सक्रिय क्लॉक कोर पर निवेश पढ़ें, हर कोर के बाद अवस्था लिखें, और याद रखें कि 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

विधि

  1. पहले हर संख्या को n के मापांक में घटाएँ; शेषफल 0 से n − 1 के बीच होते हैं।
  2. gcd के लिए यूक्लिड एल्गोरिथ्म से बार-बार भाग दें; अंतिम अशून्य शेषफल ही gcd है।
  3. प्रतिलोम के लिए विस्तारित एल्गोरिथ्म चलाएँ और a का गुणांक रखें; ऋणात्मक हो तो n जोड़ें।
  4. a·x ≡ b को हल करने के लिए a⁻¹ से गुणा करें; दो सर्वांगसमताओं को x = r₁ + m₁k लिखकर मिलाएँ।
  5. घातों के लिए घातांक को द्विआधारी में लिखें और बार-बार वर्ग करें; RSA में d = e⁻¹ mod φ(n) होता है, जहाँ φ(n) = (p − 1)(q − 1)।

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

हैंडशेक लेमा
Σ deg(v) = 2|E|
पूर्ण ग्राफ़
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
नियमित ग्राफ़
|E| = n·k/2
वृक्ष और वन
|E| = n − 1, |E| = n − c
वृक्ष के पत्ते
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
यूलर
परिपथ: सभी घात सम; पथ: ठीक 2 घात विषम
Kn में हैमिल्टन परिपथ
(n − 1)!/2
डाइक्स्ट्रा अद्यतन
d(v) = min(d(v), d(u) + w(u, v))
लंबाई L की वॉक
(Mᴸ)ij

विधि

  1. हर शीर्ष की घात लिखें; घातों का योग कोरों की संख्या का दोगुना होता है।
  2. यूलर के प्रश्नों में जाँचें कि ग्राफ़ संबद्ध है और विषम घात वाले शीर्षों को गिनें।
  3. वृक्षों के लिए n − 1 कोरों और हैंडशेक लेमा का उपयोग करें।
  4. डाइक्स्ट्रा के लिए अस्थायी दूरियों की सारणी रखें और हर चक्र में सबसे छोटी दूरी वाले अनिर्धारित शीर्ष को निर्धारित करें।
  5. न्यूनतम स्पैनिंग ट्री के लिए कोरों को भार के अनुसार क्रमबद्ध करें और चक्र बनाने वाली हर कोर छोड़ दें (क्रुस्कल), या किसी प्रारंभिक शीर्ष से एक वृक्ष बढ़ाएँ (प्रिम)।

IPv4 सबनेटिंग

प्रति सबनेट होस्ट
2(32 − prefix) − 2 (/31: 2, /32: 1)
ब्लॉक आकार
256 − (mask octet)
नेटवर्क पता
IP AND मास्क
ब्रॉडकास्ट पता
IP OR (NOT mask): सभी होस्ट बिट 1
n उधार लिए बिट से सबनेट
2n

2अभ्यास प्रश्न

1.संख्या पद्धतियाँमध्यम
8-बिट दो का पूरक0−12806403201608040201

बिट इस तरह सेट करें कि वे 8-बिट 2 के पूरक में −12 संग्रहीत करें। चिह्नरहित संख्या के रूप में पढ़ने पर पैटर्न का मान U क्या है?

N = −128 bit
U =
2.संख्या पद्धतियाँकठिन
16-बिट 2 का पूरक, N = ??चिह्न???????????????

16-बिट दो के पूरक में संग्रहीत की जा सकने वाली सबसे छोटी (सबसे ऋणात्मक) पूर्णांक N क्या है?

16 bit
N =
3.प्रस्ताविक तर्क और उपपत्तियाँमध्यम
c ∧ ¬(b ∧ a)¬c ∧ ¬(b ∧ a)¬c → ¬(b ∧ a)¬c ∧ (b ∧ a)

आप c → (b ∧ a) को विरोधाभास द्वारा सिद्ध करना चाहते हैं। शुरू में कौन-सा कथन मानेंगे? उस पर क्लिक करें।

c → (b ∧ a)
  1. 1c ∧ ¬(b ∧ a)
  2. 2¬c ∧ ¬(b ∧ a)
  3. 3¬c → ¬(b ∧ a)
  4. 4¬c ∧ (b ∧ a)
4.प्रस्ताविक तर्क और उपपत्तियाँकठिन
prp → rrp11100100

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

p → rr∴ p
  1. 1p = 1, r = 1
  2. 2p = 1, r = 0
  3. 3p = 0, r = 1
  4. 4p = 0, r = 0
5.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपमध्यम
ABCD000111100001111000011312040517060121131151141819011110

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

F(A, B, C, D) = Σm(2, 3, 7, 8, 9, 10, 13, 14, 15)
L =
6.डिजिटल लॉजिक: गेट, K-मानचित्र और फ़्लिप-फ़्लॉपकठिन
ABCD0001111000011110X01113120415X7060121131150140819011X10

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

F(A, B, C, D) = Σm(1, 2, 3, 5, 9, 13, 15) + d(0, 7, 10)
N =
7.संख्या सिद्धांत और मॉड्यूलर अंकगणितमध्यम

35x ≡ 5 (mod 97) हल करें। हल x दें, जहाँ 0 < x < 97।

35x ≡ 5 (mod 97)
x =
8.संख्या सिद्धांत और मॉड्यूलर अंकगणितकठिन
mc = me​ mod ncm = cd​ mod nm(n, e) = (1739, 5)d = ?

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

p = 37q = 47e = 5
d =
9.एल्गोरिदम और जटिलतामध्यम

वर्स्ट केस में तुलना-आधारित (comparison-based) सॉर्टिंग की निचली सीमा क्या है?

  1. AΩ(log n)
  2. BΩ(n²)
  3. CΩ(n)
  4. DΩ(n log n)
10.एल्गोरिदम और जटिलताकठिन

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

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

बाइनरी सर्च ट्री में न्यूनतम कुंजी कैसे खोजते हैं?

  1. Aहर लीफ़ पर जाकर उनकी तुलना करें
  2. Bकेवल रूट को देखें
  3. Cरूट से दाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई दायाँ चाइल्ड न रहे
  4. Dरूट से बाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई बायाँ चाइल्ड न रहे
12.डेटा संरचनाएँकठिन

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

  1. Aअसंतुलित नोड पर एक एकल बायाँ रोटेशन
  2. Bनोड और उसके चाइल्ड का रंग बदलना
  3. Cअसंतुलित नोड पर एक एकल दायाँ रोटेशन
  4. Dचाइल्ड पर बायाँ रोटेशन, फिर नोड पर दायाँ रोटेशन
13.ग्राफ़ सिद्धांतमध्यम

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

|V| = 19|E| = 24
k =
14.ग्राफ़ सिद्धांतकठिन
1331413153763ABCDEFG

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

प्रारंभ: Aअंत: F
d(F) =
15.डेटाबेस और SQLमध्यम

SQL इंजेक्शन (SQL injection) क्या है?

  1. Aएक हमला जिसमें उपयोगकर्ता इनपुट SQL क्वेरी की संरचना बदल देता है
  2. Bइंडेक्स जोड़ने का एक तरीका
  3. Cएक अकेले INSERT स्टेटमेंट से कई पंक्तियाँ जल्दी डालने की विधि
  4. Dडेटाबेस बैकअप की एक तकनीक
16.डेटाबेस और SQLकठिन

R(A, B, C, D) में फ़ंक्शनल डिपेंडेंसी A → B और C → D हैं। कैंडिडेट की क्या है?

  1. A{A, C}
  2. B{A}
  3. C{C}
  4. D{B, D}
17.कंप्यूटर नेटवर्कमध्यम

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

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

कंटेंट डिलीवरी नेटवर्क (CDN) मुख्य रूप से वेब प्रदर्शन कैसे सुधारता है?

  1. Aयह उपयोगकर्ताओं के अपने घरेलू कनेक्शनों की बैंडविड्थ बढ़ाता है
  2. Bयह DNS लुकअप की आवश्यकता समाप्त करता है
  3. Cयह TCP को एक तेज़ ट्रांसपोर्ट प्रोटोकॉल से बदल देता है
  4. Dयह उपयोगकर्ताओं के पास स्थित सर्वरों से कैश की गई सामग्री देता है
19.IPv4 सबनेटिंगमध्यम
/24 → /2811111111111111111111111111110000नेटवर्क बिटहोस्ट बिट

नेटवर्क 192.168.244.0/24 को /28 सबनेटों में बाँटा गया है, जिन्हें सबसे निचले पते से 1, 2, 3, … क्रमांकित किया गया है (सबनेट 1 .0 से शुरू होता है)। सबनेट 4 के नेटवर्क पते का चौथा ऑक्टेट x क्या है?

192.168.244.0/24/28सबनेट 4 (सबनेट 1 .0 से शुरू होता है)
x =
20.IPv4 सबनेटिंगकठिन
तीसरा ऑक्टेट 14 … 17012806403201618141201साझाभिन्न

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

10.27.14.0/24 … 10.27.17.0/24
p =

3विलयन

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

उत्तर: U = 244

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

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

12 = 0000 1100
उलटा हुआ: 1111 0011
+1 → 1111 0100

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

1111 0100₂ = 256 − 12 = 244

उत्तर

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

उत्तर: N = −32768

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

सबसे ऋणात्मक मान

−215 = −32768

उत्तर

N = −32768
3.प्रस्ताविक तर्क और उपपत्तियाँ

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

निहितार्थ के भाग

a = c, b = b ∧ a

निहितार्थ का निषेध

¬(a → b) ≡ a ∧ ¬b = c ∧ ¬(b ∧ a)

उत्तर

c ∧ ¬(b ∧ a)

यदि मान्यता विरोधाभास की ओर ले जाए, तो निहितार्थ सत्य होना चाहिए।

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

उत्तर: p = 0, r = 1

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

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

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

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

p = 0, r = 1

उत्तर

p = 0, r = 1

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

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

उत्तर: L = 15

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

ABCD000111100001111000011312040517060121131151141819011110

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

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

BCD
AC′D
ACD′
AB′D′
A′B′C

न्यूनतम SOP रूप

F = BCD + AC′D + ACD′ + AB′D′ + A′B′C
L = 15

उत्तर

L = 15

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

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

उत्तर: N = 3

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

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

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

C′D, BD, B′CD′, A′D, A′B′
ABCD0001111000011110X01113120415X7060121131150140819011X10

न्यूनतम आवरण

F = C′D + BD + A′B′
N = 3

उत्तर

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

उत्तर: x = 14

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

35 का प्रतिलोम

r = 97, t = 0
r = 35, q = 2, t = 1
r = 27, q = 1, t = −2
r = 8, q = 3, t = 3
r = 3, q = 2, t = −11
r = 2, q = 1, t = 25
r = 1, q = 2, t = −36
35−1 ≡ 61 (mod 97)

हल करें

x ≡ 61·5 = 305 ≡ 14 (mod 97)
जाँच: 35·14 = 490 ≡ 5 (mod 97)

उत्तर

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

उत्तर: d = 1325

मॉड्यूलर घात और 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 = 37·47 = 1739
φ(n) = 36·46 = 1656

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

r = 1656, t = 0
r = 5, q = 331, t = 1
r = 1, q = 5, t = −331

निजी घातांक

d = 1325
जाँच: 5·1325 = 6625 = 4·1656 + 1

उत्तर

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

उत्तर: D · Ω(n log n)

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

किसी भी तुलना-आधारित सॉर्ट को वर्स्ट केस में कम से कम log₂(n!) ≈ n log n तुलनाओं की आवश्यकता होती है। काउंटिंग सॉर्ट इससे बेहतर है क्योंकि यह तुलना नहीं करता।

उत्तर

D · Ω(n log n)
10.एल्गोरिदम और जटिलता

उत्तर: A · नहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं

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

सीमा कहती है कि हर तुलना-आधारित सॉर्ट को n आकार के किसी इनपुट पर लगभग n log n तुलनाएँ चाहिए; विशेष इनपुट बहुत तेज़ हो सकते हैं।

उत्तर

A · नहीं, निचली सीमा सभी इनपुट पर वर्स्ट केस पर लागू होती है, हर इनपुट पर नहीं
11.डेटा संरचनाएँ

उत्तर: D · रूट से बाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई बायाँ चाइल्ड न रहे

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

सबसे बाएँ नोड से छोटी कोई कुंजी ट्री में नहीं होती, इसलिए वही न्यूनतम है; लागत ऊँचाई के अनुपाती है।

उत्तर

D · रूट से बाएँ चाइल्ड का अनुसरण तब तक करें जब तक कोई बायाँ चाइल्ड न रहे
12.डेटा संरचनाएँ

उत्तर: C · असंतुलित नोड पर एक एकल दायाँ रोटेशन

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

Left-left स्थिति में एक दायाँ रोटेशन बाएँ चाइल्ड को ऊपर उठाकर संतुलन बहाल करता है; zig-zag स्थितियों में दोहरा रोटेशन चाहिए।

उत्तर

C · असंतुलित नोड पर एक एकल दायाँ रोटेशन
13.ग्राफ़ सिद्धांत

उत्तर: k = 6

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

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

19 − 1 = 18

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

k = 24 − 18 = 6

उत्तर

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

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

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

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

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

A (0): C: 13
C (13): B: 16, E: 26, G: 19
B (16): D: 30
G (19): D: 22
D (22)
E (26): F: 29
F (29)

सबसे छोटा पथ

A → C → E → F
d(F) = 29

उत्तर

d(F) = 29
15.डेटाबेस और SQL

उत्तर: A · एक हमला जिसमें उपयोगकर्ता इनपुट SQL क्वेरी की संरचना बदल देता है

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

जब उपयोगकर्ता इनपुट को SQL में जोड़ा जाता है, तो हमलावर कमांड डाल सकते हैं। पैरामीटर वाले प्रिपेयर्ड स्टेटमेंट डेटा को कोड से अलग रखते हैं।

उत्तर

A · एक हमला जिसमें उपयोगकर्ता इनपुट SQL क्वेरी की संरचना बदल देता है
16.डेटाबेस और SQL

उत्तर: A · {A, C}

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

A और C किसी से निर्धारित नहीं होते, इसलिए हर की में दोनों होने चाहिए, और {A, C}+ = {A, B, C, D}।

उत्तर

A · {A, C}
17.कंप्यूटर नेटवर्क

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

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

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

उत्तर

A · सेशन पहचानकर्ता या टोकन रखने वाली कुकीज़ से
18.कंप्यूटर नेटवर्क

उत्तर: D · यह उपयोगकर्ताओं के पास स्थित सर्वरों से कैश की गई सामग्री देता है

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

CDN सामग्री की प्रतियाँ कई edge स्थानों पर रखते हैं और उपयोगकर्ताओं को, अक्सर DNS के माध्यम से, पास के सर्वर पर भेजते हैं। इससे लेटेंसी और मूल सर्वर पर भार घटता है।

उत्तर

D · यह उपयोगकर्ताओं के पास स्थित सर्वरों से कैश की गई सामग्री देता है
19.IPv4 सबनेटिंग

उत्तर: x = 48

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

ब्लॉक आकार

24 = 16

सबनेट संख्या 4

नेटवर्क: (4 − 1)·16 = 48
ब्रॉडकास्ट: 48 + 16 − 1 = 63

उत्तर

x = 48
20.IPv4 सबनेटिंग

उत्तर: p = 19

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

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

14 = 00001110
17 = 00010001
साझा अग्रणी बिट: 3

उपसर्ग लंबाई

p = 16 + 3 = 19

उत्तर

p = /19

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

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