एल्गोरिदम इंजीनियरिंग: Difference between revisions
No edit summary |
(Text) |
||
| Line 20: | Line 20: | ||
इस तरह यह उन स्थितियों में एल्गोरिदम की दक्षता और प्रदर्शन में नई अंतर्दृष्टि प्रदान कर सकता है जहां | इस तरह यह उन स्थितियों में एल्गोरिदम की दक्षता और प्रदर्शन में नई अंतर्दृष्टि प्रदान कर सकता है जहां | ||
* एल्गोरिदम सैद्धांतिक विश्लेषण | * एल्गोरिदम सैद्धांतिक विश्लेषण एल्गोरिदम से कम उत्तरदायी है, | ||
* औपचारिक विश्लेषण निराशावादी रूप से सीमाओं का सुझाव देता है | * औपचारिक विश्लेषण निराशावादी रूप से सीमाओं का सुझाव देता है जिसमें व्यावहारिक हित के इनपुट पर प्रकट होने की संभावना नहीं है, | ||
* एल्गोरिदम आधुनिक हार्डवेयर आर्किटेक्चर की पेचीदगियों पर निर्भर करता है जैसे डेटा स्थानीयता, शाखा भविष्यवाणी, निर्देश स्टॉल, निर्देश विलंबता, जिसे एल्गोरिदम सिद्धांत में प्रयुक्त मशीन मॉडल आवश्यक विवरण में पकड़ने में असमर्थ है, | * एल्गोरिदम आधुनिक हार्डवेयर आर्किटेक्चर की पेचीदगियों पर निर्भर करता है जैसे डेटा स्थानीयता, शाखा भविष्यवाणी, निर्देश स्टॉल, निर्देश विलंबता, जिसे एल्गोरिदम सिद्धांत में प्रयुक्त मशीन मॉडल आवश्यक विवरण में पकड़ने में असमर्थ है, | ||
* विभिन्न स्थिर लागतों और स्पर्शोन्मुख व्यवहारों के साथ प्रतिस्पर्धी एल्गोरिदम के बीच क्रॉसओवर को निर्धारित करने की आवश्यकता है।<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> | * विभिन्न स्थिर लागतों और स्पर्शोन्मुख व्यवहारों के साथ प्रतिस्पर्धी एल्गोरिदम के बीच क्रॉसओवर को निर्धारित करने की आवश्यकता है।<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 28: | Line 28: | ||
== कार्यप्रणाली == | == कार्यप्रणाली == | ||
कुछ शोधकर्ता एल्गोरिथम इंजीनियरिंग की कार्यप्रणाली का वर्णन एल्गोरिथम डिज़ाइन, विश्लेषण, कार्यान्वयन और प्रायोगिक मूल्यांकन से युक्त एक चक्र के रूप में करते हैं, जो मशीन मॉडल या यथार्थवादी इनपुट जैसे अन्य पहलुओं से जुड़ते हैं। | कुछ शोधकर्ता एल्गोरिथम इंजीनियरिंग की कार्यप्रणाली का वर्णन एल्गोरिथम डिज़ाइन, विश्लेषण, कार्यान्वयन और प्रायोगिक मूल्यांकन से युक्त एक चक्र के रूप में करते हैं, जो मशीन मॉडल या यथार्थवादी इनपुट जैसे अन्य पहलुओं से जुड़ते हैं। उनका तर्क है कि एल्गोरिथम इंजीनियरिंग को प्रायोगिक एल्गोरिथम के साथ समान करना बहुत सीमित है, क्योंकि डिजाइन और विश्लेषण, कार्यान्वयन और प्रयोग को अलग-अलग गतिविधियों के रूप में देखने से एल्गोरिथम इंजीनियरिंग के उन तत्वों के बीच महत्वपूर्ण फीडबैक लूप की उपेक्षा होती है।<ref name="AEDef"/> | ||
उनका तर्क है कि एल्गोरिथम इंजीनियरिंग को प्रायोगिक एल्गोरिथम के साथ समान करना बहुत सीमित है, क्योंकि डिजाइन और विश्लेषण, कार्यान्वयन और प्रयोग को अलग-अलग गतिविधियों के रूप में देखने से एल्गोरिथम इंजीनियरिंग के उन तत्वों के बीच महत्वपूर्ण फीडबैक लूप की उपेक्षा होती है।<ref name="AEDef"/> | |||
| Line 39: | Line 38: | ||
=== डिजाइन === | === डिजाइन === | ||
एल्गोरिथम सिद्धांत की तुलना में, जो | एल्गोरिथम सिद्धांत की तुलना में, जो प्रायः एल्गोरिदम के स्पर्शोन्मुख व्यवहार पर केंद्रित होता है, एल्गोरिथम इंजीनियरों को आगे की आवश्यकताओं को ध्यान में रखने की आवश्यकता होती है: एल्गोरिथम की सरलता, वास्तविक हार्डवेयर पर प्रोग्रामिंग भाषाओं में कार्यान्वयन, और कोड पुन: उपयोग की अनुमति है। इसके अतिरिक्त, एल्गोरिदम के निरंतर कारकों का वास्तविक दुनिया के इनपुट पर इतना अधिक प्रभाव पड़ता है कि कभी-कभी खराब स्पर्शोन्मुख व्यवहार वाला एल्गोरिदम कम स्थिर कारकों के कारण व्यवहार में बेहतर प्रदर्शन करता है। | ||
इसके अतिरिक्त, एल्गोरिदम के निरंतर कारकों का वास्तविक दुनिया के इनपुट पर इतना अधिक प्रभाव पड़ता है कि कभी-कभी खराब स्पर्शोन्मुख व्यवहार वाला एल्गोरिदम कम स्थिर कारकों के कारण व्यवहार में बेहतर प्रदर्शन करता है। | |||
=== विश्लेषण === | === विश्लेषण === | ||
| Line 47: | Line 45: | ||
=== कार्यान्वयन === | === कार्यान्वयन === | ||
सैद्धांतिक अंतर्दृष्टि, तैयार किए गए एल्गोरिदम, प्रोग्रामिंग भाषाओं और हार्डवेयर के बीच विशाल सिमेंटिक अंतराल सरल एल्गोरिदम के कुशल कार्यान्वयन के लिए एक चुनौती | सैद्धांतिक अंतर्दृष्टि, तैयार किए गए एल्गोरिदम, प्रोग्रामिंग भाषाओं और हार्डवेयर के बीच विशाल सिमेंटिक अंतराल सरल एल्गोरिदम के कुशल कार्यान्वयन के लिए एक चुनौती प्रस्तुत करते हैं, क्योंकि छोटे कार्यान्वयन विवरण निष्पादन व्यवहार पर तरंगित प्रभाव डाल सकते हैं। एक एल्गोरिथ्म के कई कार्यान्वयनों की तुलना करने का एकमात्र विश्वसनीय तरीका ट्यूनिंग और प्रोफाइलिंग पर काफी समय बिताना है, उन एल्गोरिदम को कई आर्किटेक्चर पर चलाना और उत्पन्न मशीन कोड को देखना है।<ref name="AEDef"/> | ||
एक एल्गोरिथ्म के कई कार्यान्वयनों की तुलना करने का एकमात्र विश्वसनीय तरीका ट्यूनिंग और प्रोफाइलिंग पर काफी समय बिताना है, उन एल्गोरिदम को कई आर्किटेक्चर पर चलाना और उत्पन्न मशीन कोड को | |||
| Line 55: | Line 52: | ||
=== एप्लीकेशन इंजीनियरिंग === | === एप्लीकेशन इंजीनियरिंग === | ||
प्रयोगों के लिए उपयोग किए जाने वाले एल्गोरिदम का कार्यान्वयन अनुप्रयोगों में प्रयोग करने योग्य कोड से महत्वपूर्ण तरीके से भिन्न होता है। | प्रयोगों के लिए उपयोग किए जाने वाले एल्गोरिदम का कार्यान्वयन अनुप्रयोगों में प्रयोग करने योग्य कोड से महत्वपूर्ण तरीके से भिन्न होता है। जबकि पूर्व प्रयोगों के दौरान माप के लिए तेजी से प्रोटोटाइप, प्रदर्शन और उपकरण को प्राथमिकता देता है, बाद वाले को इनपुट के विशेष वर्गों के लिए पूरी तरह से परीक्षण, रखरखाव, सादगी और ट्यूनिंग की आवश्यकता होती है।<ref name="AEDef"/> | ||
जबकि पूर्व प्रयोगों के दौरान माप के लिए तेजी से प्रोटोटाइप, प्रदर्शन और उपकरण को प्राथमिकता देता है, बाद वाले को इनपुट के विशेष वर्गों के लिए पूरी तरह से परीक्षण, रखरखाव, सादगी और ट्यूनिंग की आवश्यकता होती है।<ref name="AEDef"/> | |||
Revision as of 12:08, 20 June 2023
एल्गोरिथम इंजीनियरिंग कंप्यूटर एल्गोरिदम के डिजाइन, विश्लेषण, कार्यान्वयन, अनुकूलन, प्रोफाइलिंग और प्रायोगिक मूल्यांकन पर केंद्रित है, सॉफ्टवेयर इंजीनियरिंग में एल्गोरिदम सिद्धांत और एल्गोरिदम के व्यावहारिक अनुप्रयोगों के बीच के अंतर को छोटा करता है।[1] यह एल्गोरिथम अनुसंधान के लिए एक सामान्य पद्धति है।[2]
उत्पत्ति
1995 में, एक एनएसएफ-प्रायोजित कार्यशाला की एक रिपोर्ट "कंप्यूटिंग के सिद्धांत (टीओसी) समुदाय के वर्तमान लक्ष्यों और दिशाओं का आकलन करने के उद्देश्य से" एक महत्वपूर्ण विषय के रूप में अभ्यासकर्ताओं द्वारा सैद्धांतिक अंतर्दृष्टि को अपनाने की धीमी गति की पहचान की और उपायों का सुझाव दिया
- अभ्यासकर्ताओं द्वारा अनिश्चितता को कम करें कि क्या एक निश्चित सैद्धांतिक सफलता उनके कार्यक्षेत्र में व्यावहारिक लाभ में परिवर्तित होगी, और
- रेडी-टू-यूज़ एल्गोरिथम लाइब्रेरी की कमी से निपटना, जो एल्गोरिथम समस्याओं के लिए स्थिर, त्रुटि-मुक्त और अच्छी तरह से परीक्षण किए गए कार्यान्वयन प्रदान करते हैं और लाइब्रेरी उपभोक्ताओं के लिए उपयोग में आसान अंतरापृष्ठ को उजागर करते हैं।[3]
लेकिन साथ ही, गणितीय विश्लेषण में कठिनाइयों के कारण आशाजनक एल्गोरिथम दृष्टिकोण की उपेक्षा की गई है।[2]
"एल्गोरिदम इंजीनियरिंग" शब्द का पहली बार विशिष्टता के साथ प्रयोग 1997 में, एल्गोरिथम इंजीनियरिंग पर पहली कार्यशाला (WAE97) के साथ किया गया था, जिसका आयोजन जियूसेप एफ. इटालियानो द्वारा किया गया था।[4]
एल्गोरिथम सिद्धांत से अंतर
एल्गोरिथम इंजीनियरिंग एल्गोरिथम सिद्धांत को बदलने या उसके साथ प्रतिस्पर्धा करने का इरादा नहीं रखता है, लेकिन प्रायोगिक एल्गोरिथम (जिसे अनुभवजन्य एल्गोरिथम भी कहा जाता है) के साथ अपने औपचारिक दृष्टिकोण को समृद्ध, परिष्कृत और सुदृढ़ करने का प्रयास करता है।
इस तरह यह उन स्थितियों में एल्गोरिदम की दक्षता और प्रदर्शन में नई अंतर्दृष्टि प्रदान कर सकता है जहां
- एल्गोरिदम सैद्धांतिक विश्लेषण एल्गोरिदम से कम उत्तरदायी है,
- औपचारिक विश्लेषण निराशावादी रूप से सीमाओं का सुझाव देता है जिसमें व्यावहारिक हित के इनपुट पर प्रकट होने की संभावना नहीं है,
- एल्गोरिदम आधुनिक हार्डवेयर आर्किटेक्चर की पेचीदगियों पर निर्भर करता है जैसे डेटा स्थानीयता, शाखा भविष्यवाणी, निर्देश स्टॉल, निर्देश विलंबता, जिसे एल्गोरिदम सिद्धांत में प्रयुक्त मशीन मॉडल आवश्यक विवरण में पकड़ने में असमर्थ है,
- विभिन्न स्थिर लागतों और स्पर्शोन्मुख व्यवहारों के साथ प्रतिस्पर्धी एल्गोरिदम के बीच क्रॉसओवर को निर्धारित करने की आवश्यकता है।[1][5]
कार्यप्रणाली
कुछ शोधकर्ता एल्गोरिथम इंजीनियरिंग की कार्यप्रणाली का वर्णन एल्गोरिथम डिज़ाइन, विश्लेषण, कार्यान्वयन और प्रायोगिक मूल्यांकन से युक्त एक चक्र के रूप में करते हैं, जो मशीन मॉडल या यथार्थवादी इनपुट जैसे अन्य पहलुओं से जुड़ते हैं। उनका तर्क है कि एल्गोरिथम इंजीनियरिंग को प्रायोगिक एल्गोरिथम के साथ समान करना बहुत सीमित है, क्योंकि डिजाइन और विश्लेषण, कार्यान्वयन और प्रयोग को अलग-अलग गतिविधियों के रूप में देखने से एल्गोरिथम इंजीनियरिंग के उन तत्वों के बीच महत्वपूर्ण फीडबैक लूप की उपेक्षा होती है।[2]
यथार्थवादी मॉडल और वास्तविक इनपुट
जबकि विशिष्ट अनुप्रयोग एल्गोरिथम इंजीनियरिंग की कार्यप्रणाली से बाहर हैं, वे समस्या के यथार्थवादी मॉडल और अंतर्निहित मशीन को आकार देने में महत्वपूर्ण भूमिका निभाते हैं, और प्रयोगों के लिए वास्तविक इनपुट और अन्य डिज़ाइन पैरामीटर प्रदान करते हैं।[2]
डिजाइन
एल्गोरिथम सिद्धांत की तुलना में, जो प्रायः एल्गोरिदम के स्पर्शोन्मुख व्यवहार पर केंद्रित होता है, एल्गोरिथम इंजीनियरों को आगे की आवश्यकताओं को ध्यान में रखने की आवश्यकता होती है: एल्गोरिथम की सरलता, वास्तविक हार्डवेयर पर प्रोग्रामिंग भाषाओं में कार्यान्वयन, और कोड पुन: उपयोग की अनुमति है। इसके अतिरिक्त, एल्गोरिदम के निरंतर कारकों का वास्तविक दुनिया के इनपुट पर इतना अधिक प्रभाव पड़ता है कि कभी-कभी खराब स्पर्शोन्मुख व्यवहार वाला एल्गोरिदम कम स्थिर कारकों के कारण व्यवहार में बेहतर प्रदर्शन करता है।
विश्लेषण
नियतात्मक एल्गोरिदम की तुलना में कुछ समस्याओं को सरल और अधिक कुशल तरीके से हेयुरिस्टिक्स और यादृच्छिक एल्गोरिदम के साथ हल किया जा सकता है। दुर्भाग्य से, यह विश्लेषण करने के लिए सरल यादृच्छिक एल्गोरिदम को भी कठिन बना देता है क्योंकि इसमें सूक्ष्म निर्भरताओं को ध्यान में रखा जाना है।[2]
कार्यान्वयन
सैद्धांतिक अंतर्दृष्टि, तैयार किए गए एल्गोरिदम, प्रोग्रामिंग भाषाओं और हार्डवेयर के बीच विशाल सिमेंटिक अंतराल सरल एल्गोरिदम के कुशल कार्यान्वयन के लिए एक चुनौती प्रस्तुत करते हैं, क्योंकि छोटे कार्यान्वयन विवरण निष्पादन व्यवहार पर तरंगित प्रभाव डाल सकते हैं। एक एल्गोरिथ्म के कई कार्यान्वयनों की तुलना करने का एकमात्र विश्वसनीय तरीका ट्यूनिंग और प्रोफाइलिंग पर काफी समय बिताना है, उन एल्गोरिदम को कई आर्किटेक्चर पर चलाना और उत्पन्न मशीन कोड को देखना है।[2]
प्रयोग
देखें: प्रायोगिक एल्गोरिथम
एप्लीकेशन इंजीनियरिंग
प्रयोगों के लिए उपयोग किए जाने वाले एल्गोरिदम का कार्यान्वयन अनुप्रयोगों में प्रयोग करने योग्य कोड से महत्वपूर्ण तरीके से भिन्न होता है। जबकि पूर्व प्रयोगों के दौरान माप के लिए तेजी से प्रोटोटाइप, प्रदर्शन और उपकरण को प्राथमिकता देता है, बाद वाले को इनपुट के विशेष वर्गों के लिए पूरी तरह से परीक्षण, रखरखाव, सादगी और ट्यूनिंग की आवश्यकता होती है।[2]
एल्गोरिथम पुस्तकालय
कुशल डेटा प्रकारों की लाइब्रेरी और एल्गोरिदम जैसे स्थिर, अच्छी तरह से परीक्षण किए गए एल्गोरिदम पुस्तकालय अनुप्रयोगों में नए एल्गोरिदम को अपनाने में तेजी लाकर प्रौद्योगिकी हस्तांतरण में महत्वपूर्ण भूमिका निभाते हैं। ऐसे पुस्तकालय चिकित्सकों के लिए आवश्यक निवेश और जोखिम को कम करते हैं, क्योंकि यह अकादमिक शोध के परिणामों को समझने और लागू करने के बोझ को हटा देता है।
सम्मेलन
एल्गोरिथम इंजीनियरिंग पर दो मुख्य सम्मेलन सालाना आयोजित किए जाते हैं, जिनके नाम हैं:
- प्रायोगिक एल्गोरिदम पर संगोष्ठी | 1997 में स्थापित प्रायोगिक एल्गोरिदम (SEA) पर संगोष्ठी (पहले WEA के रूप में जाना जाता था)।
- 1999 में स्थापित एलगोरिदम इंजीनियरिंग एंड एक्सपेरिमेंट्स (ALENEX) पर SIAM मीटिंग।
एल्गोरिदम इंजीनियरिंग पर 1997 कार्यशाला (डब्ल्यूएई'97) 11-13 सितंबर, 1997 को वेनिस (इटली) में आयोजित की गई थी। एल्गोरिथम इंजीनियरिंग पर तीसरी अंतर्राष्ट्रीय कार्यशाला (डब्ल्यूएई'99) जुलाई 1999 में लंदन, यूके में आयोजित की गई थी।[6] एल्गोरिदम इंजीनियरिंग और प्रयोग (ALENEX99) पर पहली कार्यशाला 15-16 जनवरी, 1999 को बाल्टीमोर, मेरीलैंड में आयोजित की गई थी।[7] यह DIMACS, असतत गणित और सैद्धांतिक कंप्यूटर विज्ञान केंद्र (रटगर्स विश्वविद्यालय में) द्वारा प्रायोजित किया गया था, SIGACT, एल्गोरिदम और संगणना सिद्धांत पर ACM विशेष रुचि समूह, और SIAM, औद्योगिक और अनुप्रयुक्त गणित के लिए सोसायटी से अतिरिक्त समर्थन के साथ।[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.
