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

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

1010 01108 bit

N =

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

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

782

b = bit

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

इसकी सत्यमान सारणी की 8 पंक्तियों में से कितनी में (¬r → q) ∧ (p → (r ∧ ¬p)) सत्य है? इस संख्या को N कहें।

(¬r → q) ∧ (p → (r ∧ ¬p))

N =

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

सत्यमान सारणी की 16 पंक्तियों में से कितनी ¬(¬r ∨ p) ∧ ((r → ¬p) → (s ∨ q)) को सत्य बनाती हैं? इस संख्या को N कहें।

¬(¬r ∨ p) ∧ ((r → ¬p) → (s ∨ q))

N =

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

एक 4-से-1 मल्टीप्लेक्सर के चयन निवेश S₁ = A और S₀ = B हैं, और उसके डेटा निवेश I₀ = 1, I₁ = C, I₂ = C′, I₃ = C′ से जुड़े हैं। A, B और C के 8 संयोजनों में से कितनों के लिए निर्गत F = 1 है? N ज्ञात करें।

I₀ = 1I₁ = CI₂ = C′I₃ = C′

N =

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

एक धनात्मक-कोर-ट्रिगर्ड JK फ़्लिप-फ़्लॉप Q = 0 से शुरू होता है और दिखाए गए निवेश पाता है। उस पहली क्लॉक कोर पर क्लिक करें जिस पर Q 1 से वापस 0 होता है।

Q₀ = 0JK

1क्लॉक कोर 1
2क्लॉक कोर 2
3क्लॉक कोर 3
4क्लॉक कोर 4
5क्लॉक कोर 5
6क्लॉक कोर 6
7क्लॉक कोर 7

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

सबसे छोटा धनात्मक पूर्णांक x ज्ञात करें जिसके लिए x ≡ 2 (mod 11) और x ≡ 0 (mod 13)।

x ≡ 2 (mod 11)x ≡ 0 (mod 13)

x =

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

71 अभाज्य है। 19³⁹⁰²⁹ mod 71 ज्ञात करने के लिए फर्मा के लघु प्रमेय का उपयोग करें।

p = 71k = 39029

19³⁹⁰²⁹ mod 71 =

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

मर्ज सॉर्ट के लिए डायनेमिक प्रोग्रामिंग कोई वास्तविक गति-वृद्धि क्यों नहीं देती?

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

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

सॉर्टेड ऐरे में किसी भी तुलना-आधारित खोज को वर्स्ट केस में Ω(log n) तुलनाएँ क्यों चाहिए?

Aहर तुलना में लघुगणकीय समय लगता है
Bn संभावित परिणामों वाले निर्णय वृक्ष (decision tree) की गहराई कम से कम log₂ n होनी चाहिए
Cबाइनरी सर्च ही एकमात्र संभव एल्गोरिदम है, और उसे log₂ n तुलनाएँ चाहिए
Dहर तत्व की कम से कम एक बार तुलना होनी चाहिए

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

क्षमता n वाले ऐरे में संग्रहीत सर्कुलर क्यू में इंडेक्स i के बाद अगली स्थिति कैसे निकाली जाती है?

A(i − 1) mod n
B(i + 1) mod n
Ci + 1
D2i + 1

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

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

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

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

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

|V| = 20|E| = 20

k =

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

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

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

d(E) =

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

एक टेबल हर ऑर्डर पंक्ति पर ग्राहक का पता संग्रहित करती है। एक पंक्ति में पता बदलना पर अन्य में नहीं, किसका उदाहरण है?

Aअपडेट विसंगति (update anomaly)
Bडिलीशन विसंगति (deletion anomaly)
Cफ़ैंटम रीड (phantom read)
Dइंसर्शन विसंगति (insertion anomaly)

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

कई DBMS स्ट्रिक्ट टू-फ़ेज़ लॉकिंग का उपयोग क्यों करते हैं, जिसमें एक्सक्लूसिव लॉक कमिट तक रखे जाते हैं?

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

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

ARP क्या करता है?

Aस्थानीय नेटवर्क से जुड़ने पर होस्टों को अपने आप IP पते आवंटित करता है
Bइंटरनेट पर पैकेट रूट करता है
Cस्थानीय नेटवर्क पर किसी IP पते से संबंधित MAC पता खोजता है
Dडोमेन नामों को resolve करता है

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

स्टेशन A और C दोनों एक्सेस पॉइंट B तक पहुँचते हैं पर एक-दूसरे को नहीं सुन सकते, इसलिए उनके फ़्रेम B पर टकराते हैं। 802.11 कैसे मदद करता है?

Aफ़्रेमों का TTL बढ़ाकर
BA के फ़्रेमों को C से होकर रूट करके
Cवैकल्पिक RTS/CTS आदान-प्रदान से: AP का CTS आसपास के सभी स्टेशनों को प्रतीक्षा करने को कहता है
DA और C से टकराव पता लगाने का उपयोग करवाकर, ताकि फ़्रेम के अतिव्यापन पर वे भेजना बंद कर दें

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

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

192.168.10.0/243 subnets

H =

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

एक होस्ट का पता 172.20.53.125/22 है। इसके नेटवर्क पते का तीसरा ऑक्टेट x क्या है?

172.20.53.125/22

x =

3विलयन

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

उत्तर: N = −90

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

मान जोड़ें

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

−128 + 32 + 4 + 2 = −90

उत्तर

N = −90

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

उत्तर: b = 10 bit

दो की घातें

2⁹ = 512 < 782

2¹⁰ = 1024 ≥ 782

उत्तर

b = 10

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

उत्तर: N = 3

सत्यमान सारणियाँ: n अलग-अलग चरों वाले सूत्र की 2ⁿ पंक्तियाँ होती हैं, सत्यमानों के हर संयोजन के लिए एक (1 = सत्य, 0 = असत्य)। भीतर से बाहर की ओर काम करें और हर उप-सूत्र को अपना स्तंभ दें। ¬a मान उलट देता है; a ∧ b केवल तब 1 होता है जब दोनों 1 हों; a ∨ b केवल तब 0 होता है जब दोनों 0 हों; a → b केवल तब 0 होता है जब a = 1 और b = 0; a ↔ b तब 1 होता है जब दोनों पक्ष बराबर हों।

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

p = 1, q = 1, r = 1: ¬r = 0, ¬r → q = 1, ¬p = 0, r ∧ ¬p = 0, p → (r ∧ ¬p) = 0, (¬r → q) ∧ (p → (r ∧ ¬p)) = 0

p = 1, q = 1, r = 0: ¬r = 1, ¬r → q = 1, ¬p = 0, r ∧ ¬p = 0, p → (r ∧ ¬p) = 0, (¬r → q) ∧ (p → (r ∧ ¬p)) = 0

p = 1, q = 0, r = 1: ¬r = 0, ¬r → q = 1, ¬p = 0, r ∧ ¬p = 0, p → (r ∧ ¬p) = 0, (¬r → q) ∧ (p → (r ∧ ¬p)) = 0

p = 1, q = 0, r = 0: ¬r = 1, ¬r → q = 0, ¬p = 0, r ∧ ¬p = 0, p → (r ∧ ¬p) = 0, (¬r → q) ∧ (p → (r ∧ ¬p)) = 0

p = 0, q = 1, r = 1: ¬r = 0, ¬r → q = 1, ¬p = 1, r ∧ ¬p = 1, p → (r ∧ ¬p) = 1, (¬r → q) ∧ (p → (r ∧ ¬p)) = 1

p = 0, q = 1, r = 0: ¬r = 1, ¬r → q = 1, ¬p = 1, r ∧ ¬p = 0, p → (r ∧ ¬p) = 1, (¬r → q) ∧ (p → (r ∧ ¬p)) = 1

p = 0, q = 0, r = 1: ¬r = 0, ¬r → q = 1, ¬p = 1, r ∧ ¬p = 1, p → (r ∧ ¬p) = 1, (¬r → q) ∧ (p → (r ∧ ¬p)) = 1

p = 0, q = 0, r = 0: ¬r = 1, ¬r → q = 0, ¬p = 1, r ∧ ¬p = 0, p → (r ∧ ¬p) = 1, (¬r → q) ∧ (p → (r ∧ ¬p)) = 0

मान 1 वाली पंक्तियाँ गिनें

(¬r → q) ∧ (p → (r ∧ ¬p)): 0, 0, 0, 0, 1, 1, 1, 0

N = 3

उत्तर

N = 3

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

उत्तर: N = 3

स्तंभ

¬r; ¬r ∨ p; ¬(¬r ∨ p); ¬p; r → ¬p; s ∨ q; (r → ¬p) → (s ∨ q); ¬(¬r ∨ p) ∧ ((r → ¬p) → (s ∨ q))

p पर बाँटें

p = 1: 0

p = 0: 3

N = 0 + 3 = 3

उत्तर

N = 3

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

उत्तर: N = 5

मल्टीप्लेक्सर: 2ⁿ-से-1 मल्टीप्लेक्सर अपने डेटा निवेशों में से एक को निर्गत तक पहुँचाता है; चयन लाइनें, द्विआधारी संख्या के रूप में पढ़ी जाकर, तय करती हैं कि कौन-सा। चयन S₁S₀ = AB वाले 4-से-1 MUX के लिए F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃। डेटा निवेशों को 0, 1, C या C′ से जोड़ने पर MUX A, B और C का कोई भी फलन बना सकता है, जो एक ही चिप से लॉजिक बनाने का आम तरीका है।

निर्गत व्यंजक

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

F = 1 वाली पंक्तियाँ

ABC = 000, 001, 011, 100, 110

N = 5

उत्तर

N = 5

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

उत्तर: क्लॉक कोर 3

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

हर कोर के बाद Q

JK फ़्लिप-फ़्लॉप: 00 स्थिर रखता है, 01 रीसेट करता है (Q = 0), 10 सेट करता है (Q = 1), 11 टॉगल करता है।

1: J = 0, K = 0 → Q = 0

2: J = 1, K = 0 → Q = 1

3: J = 1, K = 1 → Q = 0

4: J = 1, K = 0 → Q = 1

5: J = 0, K = 1 → Q = 0

6: J = 0, K = 0 → Q = 0

7: J = 1, K = 0 → Q = 1

1 से 0 का पहला परिवर्तन

क्लॉक कोर 3

उत्तर

क्लॉक कोर 3

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

उत्तर: x = 13

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

पहली सर्वांगसमता

x = 2 + 11k

दूसरी सर्वांगसमता

2 + 11k ≡ 0 (mod 13) → 11k ≡ 11 (mod 13)

k ≡ 6·11 ≡ 1 (mod 13)

परिणाम

x = 2 + 11·1 = 13

x = 13

जाँच: 13 mod 11 = 2, 13 mod 13 = 0

उत्तर

x = 13

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

उत्तर: 19³⁹⁰²⁹ mod 71 = 36

मॉड्यूलर घात और 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 से डिक्रिप्ट करें।

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

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

उत्तर: k = 1

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

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

20 − 1 = 19

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

k = 20 − 19 = 1

उत्तर

k = 1

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

उत्तर: d(E) = 25

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

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

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

A (0): B: 11, C: 14

B (11): C: 12, D: 24, G: 24

C (12): E: 25

D (24): F: 30

G (24)

E (25)

F (30)

सबसे छोटा पथ

A → B → C → E

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

2² = 4 ≥ 3 → b = 2, /26

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

2⁶ − 2 = 62

उत्तर

H = 62

20.IPv4 सबनेटिंग

उत्तर: x = 52

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

तीसरे ऑक्टेट में ब्लॉक आकार

2² = 4

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

नेटवर्क: 172.20.52.0

ब्रॉडकास्ट: 172.20.55.255

उत्तर

x = 52

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