Algorithm Design Techniques MCQ Quiz in हिन्दी - Objective Question with Answer for Algorithm Design Techniques - मुफ्त [PDF] डाउनलोड करें

उत्तर : विकल्प 3

स्पष्टीकरण :

कथन 1: ग्रीडी तकनीक समस्या को सही ढंग से हल करती है और हमेशा समस्या का एक अनुकूलित समाधान प्रदान करती है।

यह कथन असत्य है। चूंकि ग्रीडी तकनीक हमेशा किसी समस्या का सही समाधान नहीं करती है।

कथन 2: बेलमैन फोर्ड, फ़्लॉइड-वारशाल और प्राइम के एल्गोरिदम पथ की समस्याओं को हल करने के लिए गतिशील प्रोग्रामिंग तकनीक का उपयोग करते हैं।

यह कथन भी असत्य है क्योंकि प्राइम का एल्गोरिथम गतिशील प्रोग्रामिंग तकनीक का उपयोग नहीं करता है।

प्राइम का एल्गोरिदम एक ग्रीडी एल्गोरिदम है जो भारित अप्रत्यक्ष ग्राफ के लिए न्यूनतम विस्तृत ट्री को ढूंढता है।

प्रमुख बिंदु

निश्चितता:

प्रत्येक चरण को सटीक रूप से परिभाषित किया जाना चाहिए; किए जाने वाले कार्यों को प्रत्येक मामले के लिए कड़ाई से और स्पष्ट रूप से निर्दिष्ट किया जाना चाहिए। इनपुट: एक एल्गोरिथ्म में शून्य या अधिक इनपुट होते हैं, जो वस्तुओं के एक निर्दिष्ट सेट से लिए जाते हैं। आउटपुट: एक एल्गोरिथ्म में एक या एक से अधिक आउटपुट होते हैं, जिनका इनपुट से एक निर्दिष्ट संबंध होता है।

इसलिए सही उत्तर निश्चितता है।

अतिरिक्त जानकारी

परिमितता:

किसी भी इनपुट के लिए, एल्गोरिथम को चरणों की एक निश्चित संख्या के बाद समाप्त होना चाहिए। निश्चितता: एल्गोरिथ्म के सभी चरणों को सटीक रूप से परिभाषित किया जाना चाहिए। प्रभावशीलता: एल्गोरिथम के प्रत्येक चरण को सही ढंग से और सीमित समय में करना संभव होना चाहिए।

प्रभावशीलता:

एक एल्गोरिथ्म के प्रभावी होने के लिए, इसका मतलब है कि आउटपुट प्राप्त करने के लिए आवश्यक सभी कदम उपलब्ध संसाधनों के साथ व्यवहार्य होने चाहिए। इसमें कोई भी अनावश्यक और निरर्थक कदम नहीं होने चाहिए जो एक एल्गोरिथम को अप्रभावी बना सकते हैं।

इनपुट:

एक एल्गोरिथ्म में शून्य या अधिक इनपुट होते हैं, जो वस्तुओं के निर्दिष्ट सेट से लिए जाते हैं।

आउटपुट:

एक एल्गोरिथम में एक या अधिक आउटपुट होते हैं, जिनका इनपुट से एक निर्दिष्ट संबंध होता है।

सही उत्तर उपरोक्त में से कोई नहीं है।

Key Points

विभाजन और कॉक्वेर एल्गोरिथम में आम तौर पर तीन मुख्य चरण शामिल होते हैं:

• विभाजन: समस्या को छोटी उप-समस्याओं में विभाजित किया जाता है जो मूल समस्या के समान होती हैं।
• कॉक्वेर: उप-समस्याओं को पुनरावर्ती रूप से हल किया जाता है। यदि वे काफी छोटी हैं, तो उन्हें सीधे हल किया जा सकता है।
• संयोजन: उप-समस्याओं के समाधानों को मूल समस्या का समाधान उत्पन्न करने के लिए संयोजित किया जाता है।

चूँकि तीनों विकल्प (संयोजन, कॉक्वेर और विभाजन) विभाजन और विजय एल्गोरिथम में आवश्यक चरण हैं, इसलिए उत्तर "उपरोक्त में से कोई नहीं" सही ढंग से इंगित करता है कि सूचीबद्ध विकल्पों में से कोई भी ऐसा चरण नहीं है जो एल्गोरिथम से संबंधित नहीं है।

सही उत्तर विकल्प 3 है।

Key Points

• फ्लोचार्ट में स्टार्ट /स्टॉप प्रतीक को अंडाकार या गोल आयत द्वारा दर्शाया जाता है।
• इस प्रतीक का उपयोग किसी प्रक्रिया की शुरुआत या अंत को दर्शाने के लिए किया जाता है।
• फ्लोचार्ट में, स्टार्ट बिंदु को आमतौर पर "शुरू" के रूप में लेबल किया जाता है और स्टॉप बिंदु को "समाप्त" या "बंद" के रूप में लेबल किया जाता है।

Additional Information 

• विकल्प 2: यह फ्लोचार्ट में एक प्रोसेस का प्रतिनिधित्व कर सकता है, जिसे आमतौर पर एक आयत के रूप में दिखाया जाता है। इसका उपयोग किसी विशेष क्रिया या संचालन को इंगित करने के लिए किया जाता है।
• विकल्प 4: यह विकल्प एक डिसिशन सिंबल हो सकता है, जिसे आमतौर पर एक हीरे के आकार द्वारा दर्शाया जाता है। इसका उपयोग प्रक्रिया में एक निर्णय बिंदु को दिखाने के लिए किया जाता है जहां विभिन्न स्थितियों के आधार पर प्रवाह शाखा हो सकता है।
• विकल्प 1: यह एक डेटा इनपुट/आउटपुट प्रतीक हो सकता है, जिसे आमतौर पर एक समांतर चतुर्भुज द्वारा दर्शाया जाता है। यह सिस्टम में प्रवेश करने या छोड़ने वाले डेटा को इंगित करता है।

सही उत्तर विकल्प 3 है।

संकल्पना:

ग्रीडी एल्गोरिथ्म:

एक ग्रीडी एल्गोरिथ्म एक सरल, सहज ज्ञान युक्त एल्गोरिथ्म है जिसका उपयोग अनुकूलन समस्याओं में किया जाता है। एल्गोरिथ्म प्रत्येक चरण में इष्टतम विकल्प बनाता है क्योंकि यह संपूर्ण समस्या को हल करने के लिए समग्र इष्टतम तरीका खोजने का प्रयास करता है।

प्रिम का एल्गोरिदम। प्रिम का एल्गोरिदम न्यूनतम स्पैनिंग ट्री को खोजने के लिए ग्रीडी दृष्टिकोण का भी उपयोग करता है।

उदाहरण:

• प्रिम का मिनिमल स्पैनिंग ट्री एल्गोरिथम।
• ग्राफ - मानचित्र रंग।
• क्रुस्कल का मिनिमल स्पैनिंग ट्री एल्गोरिथम।
• दिज्क्स्ट्रा का मिनिमल स्पैनिंग ट्री एल्गोरिथम।

अत: सही उत्तर ग्रीडी है

Additional Information

• डायनेमिक प्रोग्रामिंग (DP) एक अनुकूलन समस्या को सरल उप-समस्याओं में तोड़कर और इस तथ्य का उपयोग करके हल करने के लिए एक एल्गोरिथम तकनीक है कि समग्र समस्या का इष्टतम समाधान इसकी उप-समस्याओं के इष्टतम समाधान पर निर्भर करता है।
• फूट डालो और जीतो एक एल्गोरिथ्म डिजाइन प्रतिमान है। डिवाइड-एंड-कॉन्कर एल्गोरिथ्म एक समस्या को समान या संबंधित प्रकार की दो या दो से अधिक उप-समस्याओं में विभाजित करता है, जब तक कि ये सीधे हल करने के लिए पर्याप्त सरल न हो जाएं।
• बैकट्रैकिंग एक एल्गोरिथम तकनीक है जहां लक्ष्य ब्रूट फ़ोर्स दृष्टिकोण का उपयोग करके किसी समस्या के सभी समाधान प्राप्त करना है। इसमें क्रमिक रूप से सभी समाधानों का एक सेट तैयार करना शामिल है। चूंकि किसी समस्या में बाधाएँ होंगी, इसलिए जो समाधान उन्हें संतुष्ट नहीं करते हैं, उन्हें हटा दिया जाएगा।

अवधारणा:

फ़्लोचार्ट एक प्रक्रिया में विभिन्न प्रकार के कार्यों या चरणों का प्रतिनिधित्व करने के लिए विशेष आकृतियों का उपयोग करते हैं। रेखाएं और तीर चरणों का क्रम और उनके बीच के संबंधों को दिखाते हैं। इन्हें फ्लोचार्ट प्रतीक के रूप में जाना जाता है।

इसलिए विकल्प 4 सही है

स्पष्टीकरण:

• एक अंडाकार एक शुरुआत या अंत बिंदु का प्रतिनिधित्व करता है
• एक लाइन एक योजक है जो प्रतिनिधि आकृतियों के बीच संबंधों को दर्शाता है
• एक समांतर चतुर्भुज इनपुट और आउटपुट का प्रतिनिधित्व करता है
• एक आयत एक प्रक्रिया का प्रतिनिधित्व करती है
• एक हीरा निर्णय का संकेत देता है

दिए गए प्रतीक उप-नियमित या एक मॉड्यूल जैसे पूर्वनिर्धारित प्रक्रिया का प्रतिनिधित्व करते हैं।

• एक सॉर्टिंग एल्गोरिथ्म को स्थिर कहा जाता है यदि समान ऑब्जेक्ट्स वाली दो ऑब्जेक्ट सॉर्ट किए गए आउटपुट में उसी क्रम में दिखाई देते हैं जैसे वे इनपुट ऐरे में सॉर्ट किए जाते हैं।
• मतलब, एक सॉर्टिंग एल्गोरिथ्म को स्थिर कहा जाता है यदि दो समान तत्व सॉर्टिंग की प्रक्रिया के दौरान क्रम को नहीं बदलते हैं।
• कुछ सॉर्टिंग एल्गोरिथ्म प्रकृति द्वारा स्थिर होते हैं जैसे सन्निवेश सॉर्ट, मर्ज सॉर्ट, बबल सॉर्ट, आदि और कुछ सॉर्टिंग एल्गोरिदम नहीं हैं, जैसे हीप सॉर्ट, क्विक सॉर्ट, आदि।

व्याख्या:

• एक कलन विधि अच्छी तरह से परिभाषित कथनों का एक अच्छी तरह से परिभाषित परिमित अनुक्रम है (जिसे अक्सर निर्देश या आदेश कहा जाता है) जो इनपुट मानों के स्वीकार्य सेट के लिए किसी समस्या  या समस्याओं के एक विशिष्ट वर्ग को समाधान प्रदान करता है (यदि कोई इनपुट हैं)।
• एक कलन विधि एक दी गई समस्या को हल करने के लिए क्रमशः प्रक्रिया है।
• यहाँ "परिमित" शब्द का अर्थ है कि कलन विधि एक समापन बिंदु तक पहुंचनी चाहिए और वह हमेशा चलती नहीं रह सकती।
• एक कलन विधि ने निम्नलिखित गुणों को पूरा करना चाहिए
•  

• इनपुट: कलन विधि में निर्दिष्ट सेट से इनपुट मान प्राप्त होना चाहिए। 
• आउटपुट: कलन विधि को इनपुट मानों के एक निर्धारित सेट से आउटपुट मानों का उत्पादन करना चाहिए।

                     आउटपुट मान किसी समस्या का समाधान हो सकता है।

• सीमित्ता: किसी भी इनपुट के लिए, कलन विधि को कुछ  निश्चित / परिमित चरणों के सदस्य के बाद समाप्त होना चाहिए, अर्थात् समाप्त होना चाहिए और अनंत नहीं होना चाहिए।
• निश्चितता: कलन विधि के सभी चरणों को सटीक रूप से परिभाषित किया जाना चाहिए।
• प्रभावकारिता: कलन विधि के प्रत्येक चरण को सही ढंग से और निश्चित समय में निष्पादित करना संभव है। यह पर्याप्त नहीं है कि प्रत्येक चरण निश्चित (या ठीक से परिभाषित) है, लेकिन यह व्यवहार्य भी होना चाहिए।

कोड:

#include
int main() {
int ary[10] = {250,1,9,7,3,4,5,21,15,19};
/यदि हम एक सरणी में n अलग-अलग घटक से 3 घटक लेते हैं तो उनमें से न तो कोई अधिकतम होगा और न ही न्यूनतम।
int a = ary[0];
int b = ary[1];
int c = ary[2];
if((b > a && a >c) || (c > a && a > b)) 
printf("%d",a);
else if((a > b && b >c) || (c > b && b >a)) 
printf("%d",b);
else 
printf("%d",c);
}

आउटपुट: 9

9 न तो अधिकतम है और न ही न्यूनतम है

स्पष्टीकरण:

उपरोक्त कोड में न तो पुनरावृत्ति और न ही पुनरावृत्ति होती है, उपरोक्त प्रोग्राम में प्रत्येक कथन स्थिर समय लेता है

और इसलिए क्रम θ (1) है

नोट: सभी अवयव अलग-अलग हैं, कोई भी तीन संख्याएँ चुनें और उनमें से दूसरा सबसे बड़ा आउटपुट दें। यदि एक ही प्रश्न में 'विशिष्ट' कीवर्ड नहीं दिया गया है, तो हमें 3 अलग-अलग अवयव प्राप्त करने होंगे और सबसे खराब स्थिति में इसमें O(n) समय लगेगा। इन तीन अलग-अलग तत्वों में से मध्य तत्व न तो न्यूनतम है और न ही अधिकतम। इस मामले में यह O(n) है। हमें आशा है कि आपका संदेह दूर हो गया होगा।

8 - क्वीन की समस्या:

• इसमें 8 क्वींस को एक 8×8 शतरंज बोर्ड पर इस प्रकार रखा जाता है कि उनमें से कोई भी समान स्थान नहीं ले सकता।
• यह पश्चअनुमार्गण का दृष्टिकोण है। पश्चअनुमार्गण दृष्टिकोण में, सभी संभावित विन्यास की जाँच की जाती है और जाँच की जाती है कि परिणाम प्राप्त हुआ है या नहीं।
• एक क्वीन पर तभी हमला किया जा सकता है जब वह उसी पंक्ति या स्तंभ या दूसरी रानी के विकर्ण में हो।

एकल स्रोत न्यूनतम पथ:

• इसका उपयोग स्रोत से शुरू होकर अन्य सभी शीर्षों तक का न्यूनतम पथ खोजने के लिए किया जाता है।
• यह ग्रीडी दृष्टिकोण पर आधारित है।
• एकल स्रोत न्यूनतम पथ कलनविधि का उदाहरण दिज्क्स्ट्रा का कलनविधि है जो शुरू में अनंत से सभी दूरी और स्रोत से दूरी 0 पर विचार करता है।

स्ट्रैसन का आव्यूह गुणन:

• यह आव्यूह गुणन के लिए उपयोग की जाने वाली एक विधि है। यह आव्यूह को गुणा करने के लिए विभाजन और कॉन्कर दृष्टिकोण का उपयोग करती है।
• मानक गुणन विधि की तुलना में स्ट्रैसन की विधि का उपयोग करके समय की खपत में सुधार किया जाता है।
• यह मानक विधि से तेज है। स्ट्रैसन का गुणन केवल वर्ग आव्यूहों पर ही किया जा सकता है।

इष्टतम द्विआधारी खोज ट्री:

• इसे भार संतुलित द्विआधारी ट्री के रूप में भी जाना जाता है। इष्टतम द्विआधारी खोज ट्री में, पहले द्विआधारी खोज ट्री का निर्माण करके ट्री में डमी की जोड़ी जाती है।
• यह डायनामिक प्रोग्रामिंग दृष्टिकोण पर आधारित है। कुल लागत यथासंभव कम होना चाहिए।

संकल्पना:

एल्गोरिथ्म एक समस्या को हल करने या गणना करने के लिए इंस्ट्रक्शन का एक सेट है। एल्गोरिदम इंस्ट्रक्शन की एक सटीक सूची है, जो सॉफ़्टवेयर या हार्डवेयर-आधारित प्रक्रिया में इम्प्लीमेंट होने पर, अनुक्रमिक रूप से पूर्व निर्धारित गतिविधियों को पूरा करता है।

व्याख्या:

अच्छे एल्गोरिदम के की विशेषताएं निम्नवत हैं:-

• एल्गोरिदम निश्चित संख्या में आयट्रेसन के बाद समाप्त नहीं होता है।
• इनमे एम्बिगुइटी पाई जाती है। 
• एल्गोरिदम इनपुट प्राप्त करता है लेकिन इसे प्रोसेस नहीं कर पाता है।
• एल्गोरिथ्म में लॉजिकल फ्लॉ पाया जाता है।
• एल्गोरिदम इनवैलिड रिजल्ट उत्पन्न करता है।​
• एल्गोरिथ्म द्वारा आउटपुट प्रदर्शित नहीं किया जाता है।
• एल्गोरिदम एक्सेक्यूशन के चरणों को सटीक रूप से रेखांकित नहीं करता है।
• एल्गोरिथ्म ऑप्टीमल परफॉर्मन्स के लिए अनुकूलित नहीं होता है।

इसलिए, विकल्प 4) अच्छे एल्गोरिदम की विशेषता नहीं है। 

नैप्सैक समस्या के निम्नलिखित दो प्रकार हैं-

1. फ्रैक्शनल नैप्सैक प्रॉब्लेम
2. 0/1 नैप्सैक प्रॉब्लेम

समय जटिलता-

• तालिका की प्रत्येक प्रविष्टि की गणना के लिए स्थिर समय θ(1) की आवश्यकता होती है।
• (n+1)(w+1) प्रविष्टियों को भरने में θ(nw) समय लगता है। इसलिए, O(nw + n + w +1) = O(nw )
• समाधान का पता लगाने में θ(n) समय लगता है क्योंकि पता लगाने की प्रक्रिया n पंक्तियों का पता लगाती है।
• इस प्रकार, डायनेमिक प्रोग्रामिंग का उपयोग करके 0/1 नैप्सैक समस्या को हल करने में कुल θ(nw) समय लगता है।

सही उत्तर विकल्प 2 है।

अवधारणा:

क्विकसॉर्ट एक डिवाइड-एंड-कॉन्कर एल्गोरिथम है। यह एक तत्व को पिवट के रूप में चुनता है और चुने हुए पिवट के चारों ओर दिए गए सरणी को विभाजित करता है। क्विकसॉर्ट के कई अलग-अलग संस्करण हैं जो अलग-अलग तरीकों से पिवट चुनते हैं।

• हमेशा पहले तत्व को पिवट के रूप में चुनें।
• हमेशा अंतिम तत्व को पिवट के रूप में चुनें।
• पिवट के रूप में एक यादृच्छिक तत्व चुनें।
• माध्यिका को पिवट के रूप में चुनें।

यहाँ दिया गया है, मान लें कि एक डिवाइड-एंड-कॉन्कर क्विक सॉर्ट एल्गोरिथ्म है और विभाजन एल्गोरिथ्म में, सूचियों के पहले तत्व को पिवट-तत्व के रूप में लिया जाता है।

विकल्प 1: 40, 50, 10, 20, 30

असत्य, यहाँ पिवट तत्व 40 है। क्विक सॉर्ट चलाने के बाद क्रम 20, 50, 10, 40, 30 जैसा होगा। अतः संख्याओं का दिया गया क्रम X2,5 = 1 सही नहीं है।

विकल्प 2: 10, 20, 50, 30, 40

सत्य, यहां पिवट तत्व 10 है। क्विक सॉर्ट चलाने के बाद अनुक्रम 10, 20, 50, 30, 40 जैसा होगा। तो संख्याओं का दिया गया क्रम X2,5 = 1 सही क्रम है।

पिवट के 20 होने के बाद, यह अनुक्रम को 10, 20, 50, 30, 40 की तरह विभाजित करता है। और X 3,5 = 1

पिवट के 50 होने के बाद, यह अनुक्रम को 10, 20, 40, 30, 50 की तरह विभाजित करता है। और X 4,5 = 1। इसी तरह आगे भी।

विकल्प 3: 40, 20, 10, 30, 50

असत्य, यहाँ पिवट तत्व 40 है। क्विक सॉर्ट चलाने के बाद अनुक्रम 30, 20, 10, 40, 50 जैसा होगा। अतः संख्याओं X2,5 = 1 का दिया गया क्रम सही नहीं है।

विकल्प 4: 30, 20, 10, 40, 50

असत्य, यहां पिवट तत्व 30 है। क्विक सॉर्ट चलाने के बाद अनुक्रम 1 0, 20, 30, 40, 50 जैसा होगा। अतः संख्याओं X2,5 = 1 का दिया गया क्रम सही नहीं है।

अतः सही उत्तर 10, 20, 50, 30, 40 है।

 Additional Information

क्विकसॉर्ट:

यदि सरणी को क्रमबद्ध किया जाता है तो सबसे खराब स्थिति समय जटिलता क्विकसॉर्ट एल्गोरिथ्म O(n2) है।
T(n) = T(n-1) + cn

यही कारण है कि यादृच्छिक क्विक सॉर्ट प्रकार समय जटिलता O(N log N) बनाने के लिए आते हैं
यादृच्छिक क्विकसॉर्ट:
रैंडमाइज्ड क्विकसॉर्ट कहता है कि पिवट को पहले तत्व के रूप में चुनने के बजाय क्या होगा यदि मेरी पिवट को मेरी सरणी A[p...r] से यादृच्छिक तत्व बनने के लिए चुनें।

सही उत्तर विकल्प 1 है।

संकल्पना:

हफ़मैन कोडिंग एक हानिरहित डेटा संपीड़न एल्गोरिथम है। इनपुट अक्षरों के लिए परिवर्ती-लंबाई कोड असाइन करने का विचार है, असाइन किए गए कोड की लंबाई संबंधित अक्षरों की बारंबारता पर आधारित होती है। सबसे अधिक बार आने वाले अक्षर को सबसे छोटा कोड मिलता है और सबसे कम बार आने वाले अक्षर को सबसे बड़ा कोड मिलता है।

व्याख्या:

हफमैन कोडिंग एल्गोरिथम

1. स्ट्रिंग में प्रत्येक अक्षर की बारंबारता की गणना करें
2. बारंबारता के बढ़ते क्रम में अक्षरों को क्रमबद्ध करें। इन्हें प्राथमिकता पंक्ति Q में संग्रहित किया जाता है।
3. प्रत्येक अद्वितीय अक्षर का लीफ नोड बनाएं।
4. एक खाली नोड z बनाएँ। z के बाएँ चाइल्ड को न्यूनतम बारंबारता पर नियत करें और z के दाएँ चाइल्ड को दूसरी न्यूनतम बारंबारता पर नियत करें। z का मान उपरोक्त दो न्यूनतम बारंबारता के योग के रूप में निर्धारित करें।
5. Q से इन दो न्यूनतम बारंबारता को हटा दें और योग को बारंबारता की सूची में जोड़ें।
6. ट्री में नोड z रखे।
7. सभी अक्षरों के लिए चरण 3 से 5 दोहराएँ।
8. प्रत्येक गैर-लीफ नोड के लिए, बाएं किनारे पर 0 और दाएं किनारे पर 1 असाइन करें।

हफमैन का कोड ट्री है,

अक्षरों की दी गई बारंबारता,

अतः सही उत्तर 01 है।