एल्गोरिदम इंजीनियरिंग: Difference between revisions
No edit summary |
(Text) |
||
| Line 22: | Line 22: | ||
* पास में निहित एल्गोरिथम एल्गोरिथम सैद्धांतिक विश्लेषण के लिए कम उत्तरदायी है, | * पास में निहित एल्गोरिथम एल्गोरिथम सैद्धांतिक विश्लेषण के लिए कम उत्तरदायी है, | ||
* औपचारिक विश्लेषण निराशावादी रूप से सीमाओं का सुझाव देता है जिसमें प्रयोगात्मक हित के इनपुट्स पर प्रदर्शित होने की संभावना नहीं है, | * औपचारिक विश्लेषण निराशावादी रूप से सीमाओं का सुझाव देता है जिसमें प्रयोगात्मक हित के इनपुट्स पर प्रदर्शित होने की संभावना नहीं है, | ||
* एल्गोरिदम आधुनिक हार्डवेयर आर्किटेक्चर की पेचीदगियों पर निर्भर करता है जैसे डेटा स्थानीयता, शाखा भविष्यवाणी, निर्देश स्टॉल, निर्देश विलंबता, जिसे एल्गोरिदम सिद्धांत में प्रयुक्त मशीन मॉडल आवश्यक विवरण | * एल्गोरिदम आधुनिक हार्डवेयर आर्किटेक्चर की पेचीदगियों पर निर्भर करता है जैसे डेटा स्थानीयता, शाखा भविष्यवाणी, निर्देश स्टॉल, निर्देश विलंबता, जिसे एल्गोरिदम सिद्धांत में प्रयुक्त मशीन मॉडल आवश्यक विवरण को अधिकृत करने में असमर्थ है, | ||
* विभिन्न स्थिर लागतों और स्पर्शोन्मुख व्यवहारों के साथ प्रतिस्पर्धी एल्गोरिदम के बीच | * विभिन्न स्थिर लागतों और स्पर्शोन्मुख व्यवहारों के साथ प्रतिस्पर्धी एल्गोरिदम के बीच विनिमय को निर्धारित करने की आवश्यकता है।<ref name="AE"/><ref name="TDEA">"Towards a Discipline of Experimental Algorithmics", Bernard M. E. Moret, web: [http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf]</ref> | ||
| Line 38: | Line 38: | ||
=== डिजाइन === | === डिजाइन === | ||
एल्गोरिथम सिद्धांत की तुलना में, जो प्रायः एल्गोरिदम के स्पर्शोन्मुख व्यवहार पर केंद्रित होता है, | एल्गोरिथम सिद्धांत की तुलना में, जो प्रायः एल्गोरिदम के स्पर्शोन्मुख व्यवहार पर केंद्रित होता है, एल्गोरिदम इंजीनियरों को आगे की आवश्यकताओं को ध्यान में रखना होगा: एल्गोरिथम की सरलता, वास्तविक हार्डवेयर पर प्रोग्रामिंग भाषाओं में कार्यान्वयन, और कोड पुन: उपयोग की अनुमति है। इसके अतिरिक्त, एल्गोरिदम के निरंतर कारकों का वास्तविक दुनिया के इनपुट पर इतना अधिक प्रभाव पड़ता है कि कभी-कभी खराब स्पर्शोन्मुख व्यवहार वाला एल्गोरिदम कम स्थिर कारकों के कारण व्यवहार में बेहतर प्रदर्शन करता है। | ||
=== विश्लेषण === | === विश्लेषण === | ||
नियतात्मक एल्गोरिदम की तुलना में कुछ समस्याओं को सरल और अधिक कुशल तरीके से हेयुरिस्टिक्स और यादृच्छिक एल्गोरिदम के साथ हल किया जा सकता है। दुर्भाग्य से, | नियतात्मक एल्गोरिदम की तुलना में कुछ समस्याओं को सरल और अधिक कुशल तरीके से हेयुरिस्टिक्स और यादृच्छिक एल्गोरिदम के साथ हल किया जा सकता है। दुर्भाग्य से, इससे सरल यादृच्छिक एल्गोरिदम का भी विश्लेषण करना मुश्किल हो जाता है क्योंकि इसमें सूक्ष्म निर्भरताओं को ध्यान में रखना पड़ता है।<ref name="AEDef"/> | ||
=== कार्यान्वयन === | === कार्यान्वयन === | ||
सैद्धांतिक अंतर्दृष्टि, तैयार किए गए एल्गोरिदम, प्रोग्रामिंग भाषाओं और हार्डवेयर के बीच विशाल सिमेंटिक अंतराल सरल एल्गोरिदम के कुशल कार्यान्वयन के लिए एक चुनौती प्रस्तुत करते हैं, क्योंकि छोटे कार्यान्वयन विवरण निष्पादन व्यवहार पर | सैद्धांतिक अंतर्दृष्टि, तैयार किए गए एल्गोरिदम, प्रोग्रामिंग भाषाओं और हार्डवेयर के बीच विशाल सिमेंटिक अंतराल यहां तक कि सरल एल्गोरिदम के कुशल कार्यान्वयन के लिए एक चुनौती प्रस्तुत करते हैं, क्योंकि छोटे कार्यान्वयन विवरण निष्पादन व्यवहार पर व्यापक प्रभाव डाल सकते हैं। एक एल्गोरिथ्म के कई कार्यान्वयनों की तुलना करने का एकमात्र विश्वसनीय तरीका ट्यूनिंग और प्रोफाइलिंग पर काफी समय बिताना है, उन एल्गोरिदम को कई आर्किटेक्चर पर चलाना और उत्पन्न मशीन कोड को देखना है।<ref name="AEDef"/> | ||
| Line 52: | Line 52: | ||
=== एप्लीकेशन इंजीनियरिंग === | === एप्लीकेशन इंजीनियरिंग === | ||
प्रयोगों के लिए उपयोग किए जाने वाले एल्गोरिदम का कार्यान्वयन अनुप्रयोगों में प्रयोग करने योग्य कोड से महत्वपूर्ण तरीके से भिन्न होता है। जबकि पूर्व प्रयोगों के दौरान माप के लिए तेजी से प्रोटोटाइप, प्रदर्शन और | प्रयोगों के लिए उपयोग किए जाने वाले एल्गोरिदम का कार्यान्वयन अनुप्रयोगों में प्रयोग करने योग्य कोड से महत्वपूर्ण तरीके से भिन्न होता है। जबकि पूर्व प्रयोगों के दौरान माप के लिए तेजी से प्रोटोटाइप, प्रदर्शन और उपकरणीकरण को प्राथमिकता देता है, बाद वाले को इनपुट के विशेष वर्गों के लिए पूरी तरह से गहन परीक्षण, रखरखाव, सरलता और ट्यूनिंग की आवश्यकता होती है।<ref name="AEDef"/> | ||
Revision as of 12:15, 22 June 2023
एल्गोरिदम इंजीनियरिंग कंप्यूटर एल्गोरिदम के डिजाइन, विश्लेषण, कार्यान्वयन, अनुकूलन, प्रोफाइलिंग और प्रायोगिक मूल्यांकन पर केंद्रित है, सॉफ्टवेयर इंजीनियरिंग में एल्गोरिदम सिद्धांत और एल्गोरिदम के व्यावहारिक अनुप्रयोगों के बीच के अंतर को छोटा करता है।[1] यह एल्गोरिथम शोध के लिए एक सामान्य कार्यप्रणाली है।[2]
उत्पत्ति
1995 में, एक एनएसएफ-प्रायोजित कार्यशाला की एक रिपोर्ट "कंप्यूटिंग के सिद्धांत (टीओसी) समुदाय के वर्तमान लक्ष्यों और दिशाओं का आकलन करने के उद्देश्य से" एक महत्वपूर्ण विषय के रूप में अभ्यासकर्ताओं द्वारा सैद्धांतिक अंतर्दृष्टि को अपनाने की धीमी गति की पहचान की और उपायों का सुझाव दिया
- अभ्यासकर्ताओं द्वारा अनिश्चितता को कम करें कि क्या एक निश्चित सैद्धांतिक सफलता उनके कार्यक्षेत्र में व्यावहारिक लाभ में परिवर्तित होगी, और
- रेडी-टू-यूज़ एल्गोरिथम लाइब्रेरी की कमी से निपटना, जो एल्गोरिथम समस्याओं के लिए स्थिर, त्रुटि-मुक्त और अच्छी तरह से परीक्षण किए गए कार्यान्वयन प्रदान करते हैं और लाइब्रेरी उपभोक्ताओं के लिए उपयोग में आसान अंतरापृष्ठ को प्रदर्शित करते हैं।[3]
लेकिन साथ ही, गणितीय विश्लेषण में कठिनाइयों के कारण आशाजनक एल्गोरिथम दृष्टिकोण की उपेक्षा की गई है।[2]
"एल्गोरिदम इंजीनियरिंग" शब्द का पहली बार विशिष्टता के साथ प्रयोग 1997 में, एल्गोरिथम इंजीनियरिंग पर पहली कार्यशाला (WAE97) के साथ किया गया था, जिसका आयोजन जियूसेप एफ. इटालियानो द्वारा किया गया था।[4]
एल्गोरिथम सिद्धांत से अंतर
एल्गोरिथम इंजीनियरिंग एल्गोरिथम सिद्धांत को बदलने या उसके साथ प्रतिस्पर्धा करने का इरादा नहीं रखता है, लेकिन प्रायोगिक एल्गोरिथम (जिसे आनुभविक एल्गोरिथम भी कहा जाता है) के साथ अपने औपचारिक दृष्टिकोण को समृद्ध, परिष्कृत और सुदृढ़ करने का प्रयास करता है।
इस तरह यह उन स्थितियों में एल्गोरिदम की दक्षता और प्रदर्शन में नई अंतर्दृष्टि प्रदान कर सकता है जहां
- पास में निहित एल्गोरिथम एल्गोरिथम सैद्धांतिक विश्लेषण के लिए कम उत्तरदायी है,
- औपचारिक विश्लेषण निराशावादी रूप से सीमाओं का सुझाव देता है जिसमें प्रयोगात्मक हित के इनपुट्स पर प्रदर्शित होने की संभावना नहीं है,
- एल्गोरिदम आधुनिक हार्डवेयर आर्किटेक्चर की पेचीदगियों पर निर्भर करता है जैसे डेटा स्थानीयता, शाखा भविष्यवाणी, निर्देश स्टॉल, निर्देश विलंबता, जिसे एल्गोरिदम सिद्धांत में प्रयुक्त मशीन मॉडल आवश्यक विवरण को अधिकृत करने में असमर्थ है,
- विभिन्न स्थिर लागतों और स्पर्शोन्मुख व्यवहारों के साथ प्रतिस्पर्धी एल्गोरिदम के बीच विनिमय को निर्धारित करने की आवश्यकता है।[1][5]
कार्यप्रणाली
कुछ शोधकर्ता एल्गोरिथम इंजीनियरिंग की कार्यप्रणाली का वर्णन एल्गोरिथम डिज़ाइन, विश्लेषण, कार्यान्वयन और प्रायोगिक मूल्यांकन से युक्त एक चक्र के रूप में करते हैं, जो मशीन मॉडल या यथार्थवादी इनपुट जैसे अन्य पहलुओं से जुड़ते हैं। उनका तर्क है कि एल्गोरिथम इंजीनियरिंग को प्रायोगिक एल्गोरिथम के साथ समान करना बहुत सीमित है, क्योंकि डिजाइन और विश्लेषण, कार्यान्वयन और प्रयोग को अलग-अलग गतिविधियों के रूप में देखने से एल्गोरिथम इंजीनियरिंग के उन तत्वों के बीच महत्वपूर्ण फीडबैक लूप की उपेक्षा होती है।[2]
यथार्थवादी मॉडल और वास्तविक इनपुट
जबकि विशिष्ट अनुप्रयोग एल्गोरिथम इंजीनियरिंग की कार्यप्रणाली से बाहर हैं, वे समस्या के यथार्थवादी मॉडल और अंतर्निहित मशीन को आकार देने में महत्वपूर्ण भूमिका निभाते हैं, और प्रयोगों के लिए वास्तविक इनपुट और अन्य डिज़ाइन पैरामीटर प्रदान करते हैं।[2]
डिजाइन
एल्गोरिथम सिद्धांत की तुलना में, जो प्रायः एल्गोरिदम के स्पर्शोन्मुख व्यवहार पर केंद्रित होता है, एल्गोरिदम इंजीनियरों को आगे की आवश्यकताओं को ध्यान में रखना होगा: एल्गोरिथम की सरलता, वास्तविक हार्डवेयर पर प्रोग्रामिंग भाषाओं में कार्यान्वयन, और कोड पुन: उपयोग की अनुमति है। इसके अतिरिक्त, एल्गोरिदम के निरंतर कारकों का वास्तविक दुनिया के इनपुट पर इतना अधिक प्रभाव पड़ता है कि कभी-कभी खराब स्पर्शोन्मुख व्यवहार वाला एल्गोरिदम कम स्थिर कारकों के कारण व्यवहार में बेहतर प्रदर्शन करता है।
विश्लेषण
नियतात्मक एल्गोरिदम की तुलना में कुछ समस्याओं को सरल और अधिक कुशल तरीके से हेयुरिस्टिक्स और यादृच्छिक एल्गोरिदम के साथ हल किया जा सकता है। दुर्भाग्य से, इससे सरल यादृच्छिक एल्गोरिदम का भी विश्लेषण करना मुश्किल हो जाता है क्योंकि इसमें सूक्ष्म निर्भरताओं को ध्यान में रखना पड़ता है।[2]
कार्यान्वयन
सैद्धांतिक अंतर्दृष्टि, तैयार किए गए एल्गोरिदम, प्रोग्रामिंग भाषाओं और हार्डवेयर के बीच विशाल सिमेंटिक अंतराल यहां तक कि सरल एल्गोरिदम के कुशल कार्यान्वयन के लिए एक चुनौती प्रस्तुत करते हैं, क्योंकि छोटे कार्यान्वयन विवरण निष्पादन व्यवहार पर व्यापक प्रभाव डाल सकते हैं। एक एल्गोरिथ्म के कई कार्यान्वयनों की तुलना करने का एकमात्र विश्वसनीय तरीका ट्यूनिंग और प्रोफाइलिंग पर काफी समय बिताना है, उन एल्गोरिदम को कई आर्किटेक्चर पर चलाना और उत्पन्न मशीन कोड को देखना है।[2]
प्रयोग
देखें: प्रायोगिक एल्गोरिथम
एप्लीकेशन इंजीनियरिंग
प्रयोगों के लिए उपयोग किए जाने वाले एल्गोरिदम का कार्यान्वयन अनुप्रयोगों में प्रयोग करने योग्य कोड से महत्वपूर्ण तरीके से भिन्न होता है। जबकि पूर्व प्रयोगों के दौरान माप के लिए तेजी से प्रोटोटाइप, प्रदर्शन और उपकरणीकरण को प्राथमिकता देता है, बाद वाले को इनपुट के विशेष वर्गों के लिए पूरी तरह से गहन परीक्षण, रखरखाव, सरलता और ट्यूनिंग की आवश्यकता होती है।[2]
एल्गोरिथम लाइब्रेरीज
एलईडीए जैसी स्थिर, अच्छी तरह से जांची गई एल्गोरिथम लाइब्रेरी अनुप्रयोगों में नए एल्गोरिदम को अपनाने में तेजी लाकर प्रौद्योगिकी हस्तांतरण में महत्वपूर्ण भूमिका निभाती है। ऐसे लाइब्रेरी अभ्यासकर्ताओं के लिए आवश्यक निवेश और जोखिम को कम करते हैं, क्योंकि यह अकादमिक शोध के परिणामों को समझने और लागू करने के बोझ को हटा देता है।
सम्मेलन
एल्गोरिथम इंजीनियरिंग पर दो मुख्य सम्मेलन सालाना आयोजित किए जाते हैं, जिनके नाम हैं:
- 1997 में स्थापित प्रायोगिक एल्गोरिदम पर संगोष्ठी(एसइए) ( जिसे पहले डब्ल्यूइए के रूप में जाना जाता था)।
- 1999 में स्थापित एलगोरिदम इंजीनियरिंग एंड एक्सपेरिमेंट्स (एएलइएनइएक्स) पर एसआईएएम मीटिंग।
एल्गोरिदम इंजीनियरिंग पर 1997 कार्यशाला (डब्ल्यूएई'97) 11-13 सितंबर, 1997 को वेनिस (इटली) में आयोजित की गई थी। एल्गोरिथम इंजीनियरिंग पर तीसरी अंतर्राष्ट्रीय कार्यशाला (डब्ल्यूएई'99) जुलाई 1999 में लंदन, यूके में आयोजित की गई थी।[6] एल्गोरिदम इंजीनियरिंग और प्रयोग पर पहली कार्यशाला (एएलइएनइएक्स99) 15-16 जनवरी, 1999 को बाल्टीमोर, मेरीलैंड में आयोजित की गई थी।[7] यह डीआईएमएसीएस, असतत गणित और सैद्धांतिक कंप्यूटर विज्ञान केंद्र (रटगर्स विश्वविद्यालय में) द्वारा प्रायोजित किया गया था, एसआईजीएसीटी, एल्गोरिदम और संगणना सिद्धांत पर एसीएम विशेष रुचि समूह, और एसआईएएम, सोसाइटी फॉर इंडस्ट्रियल एंड एप्लाइड मैथमेटिक्स से अतिरिक्त समर्थन के साथ प्रायोजित किया गया था।[7]
संदर्भ
- ↑ 1.0 1.1 "Algorithm Engineering", Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, web: http://www.dis.uniroma1.it/~demetres/docs/ae.pdf
- ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 "Algorithm Engineering – An Attempt at a Definition", Peter Sanders, web: http://algo2.iti.kit.edu/documents/definition.pdf
- ↑ "Emerging Opportunities for Theoretical Computer Science", Aho, Johnson, Karp, Kosaraju, McGeoch, Papadimitriou, web: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9160
- ↑ Workshop on Algorithm Engineering
- ↑ "Towards a Discipline of Experimental Algorithmics", Bernard M. E. Moret, web: http://infoscience.epfl.ch/record/97865/files/dimacs_algorithmics.pdf
- ↑ Algorithm engineering: 3rd International Workshop, Jeffrey Scott Vitter, Christos D. Zaroliagis, 1999, web: BGoogle-sC.
- ↑ 7.0 7.1 "Workshop on Algorithm Engineering and Experiments" (overview), JHU.edu, 1999, web: JHU-ALENEX99.
