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

मैं अकादमिक विश्वविद्यालय में एक अभिमानी और संकीर्ण छात्र की कहानी का वर्णन करना चाहता हूं, जिसमें से, मैं निश्चित रूप से नहीं हूं, लेकिन मुझे उनके विचारों और अनुभवों का एक अच्छा विचार है। हम इस छात्र को, उदाहरण के लिए, शूरिक कहेंगे। जिस समय शूरिक ने अकादमिक विश्वविद्यालय (एयू) में प्रवेश किया, उसके प्रोग्रामिंग रिज्यूमे के अनुसार, वह पहले से ही एल्गोरिदम के क्षेत्र में एक विशेषज्ञ था। उन्होंने गहराई से खोज एल्गोरिथ्म में महारत हासिल की, सरणियों को छांटने के कई तरीके जाने, और बाइनरी खोज के बारे में एक विचार था। स्वाभाविक रूप से, एल्गोरिदम के पाठ्यक्रम ने उन्हें बिल्कुल भी दिलचस्पी नहीं ली, और वास्तव में, थोड़ा प्रोग्रामर को पांच साल के अनुभव के साथ सिखाया जा सकता है। एयू में सैद्धांतिक सूचना विज्ञान के कार्यक्रम ने उन्हें इस तथ्य में रुचि दी कि उनके द्वारा ज्ञात विषयों पर विषयों में उनके लिए बहुत सारे शब्द अज्ञात थे। लेकिन यह पीटर है, वहां वे अंकुश को एक अजीब शब्द कहते हैं, शायद, और उन्होंने इसे सुंदर शब्दों की गहराई में खोज करने के लिए सोचा था। उन्होंने पाठ्यक्रमों की स्लाइड और वीडियो का ध्यानपूर्वक अध्ययन किया। यह पता चला कि वहाँ कुछ प्रकार का कंप्यूटर विज्ञान है, जो शूरिक के पास पूरी तरह से नहीं है। शुरिक ने किताबें, मोजे और पांच साल का अनुभव एकत्र किया और एक साक्षात्कार के लिए पीटर के पास गए। वहां उन्होंने ऐसे लोगों से मुलाकात की जो एक प्रोग्रामर को भी इस तरह के अनुभव के साथ कुछ सिखा सकते हैं। इस सभी ने दुनिया के Shurikov की तस्वीर को नष्ट कर दिया, जिसमें कंप्यूटर विज्ञान के ज्ञान को C # में लिखित कक्षाओं की संख्या से मापा गया था।
अपने स्नातक अध्ययन के दौरान, शरिक सर्किट जटिलता और घातीय एल्गोरिदम के क्षेत्र में अनुसंधान में लगे हुए थे। यह वास्तव में बहुत दिलचस्प है और, स्नातक विद्यालय में प्रवेश के लिए कोई कम महत्वपूर्ण, उपयोगी नहीं है।
फिलहाल, Shurik न्यूयॉर्क विश्वविद्यालय में एक खुश स्नातक छात्र है, "अंकुश" शब्द का उपयोग करता है, और अकादमिक विश्वविद्यालय को गहरी कृतज्ञता के साथ याद करता है। और स्वायत्त विश्वविद्यालय के गणितीय और सूचना प्रौद्योगिकी विभाग और अब "सैद्धांतिक सूचना विज्ञान" की दिशा में, विशेष रूप से नए स्नातक का एक सेट की ओर जाता है।
अब मैं शरिक शब्द को पास करता हूं, जो अपने एक शोध के बारे में बात करेगा।

एनपी-कठिन समस्याओं के लिए एल्गोरिदम

एनपी-कठिन समस्याएं अक्सर अभ्यास में सामना किए जाने वाले कार्य हैं जिनके लिए प्रभावी समाधान एल्गोरिदम अज्ञात हैं। ऐसी समस्याओं का अध्ययन बहुत रुचि का है, क्योंकि इनमें से किसी भी समस्या के लिए एक प्रभावी एल्गोरिथ्म का अस्तित्व क्लास एनपी से सभी समस्याओं के लिए प्रभावी एल्गोरिदम के अस्तित्व का मतलब है। और, इसके विपरीत, अगर हम यह साबित कर सकते हैं कि इनमें से कम से कम समस्याओं में एक प्रभावी एल्गोरिथ्म नहीं है, तो इसका मतलब यह होगा कि सभी एनपी-हार्ड समस्याओं के लिए ऐसे एल्गोरिदम मौजूद नहीं हैं। एयू की मजिस्ट्रेटिव में, हमने कुछ एनपी-हार्ड समस्याओं को हल करने के लिए सटीक और अनुमानित एल्गोरिदम की जांच की। उदाहरण के लिए, हम अधिकतम व्यवहार्यता समस्या, यात्रा विक्रेता समस्या और सबसे छोटी सामान्य अधिरचना समस्या को हल करने के लिए नए एल्गोरिदम प्राप्त करने में कामयाब रहे। आगे, मैं इनमें से एक एल्गोरिदम का वर्णन करना चाहता हूं, जिसका नाम है, ट्रैवलिंग सेल्समैन समस्या के अनुमानित समाधान के लिए एक एल्गोरिथ्म।

एनपी-हार्ड ऑप्टिमाइज़ेशन समस्या एनपी-हार्ड समस्या है, जिसमें सभी संभव समाधानों के बीच कुछ अर्थों में एक इष्टतम समाधान चुनना आवश्यक है। उदाहरण के लिए, किसी दिए गए भारित ग्राफ के प्रत्येक शीर्ष से गुजरने वाले सबसे छोटे चक्र को ठीक एक बार खोजें। शायद ग्राफ के चारों ओर जाने के कई तरीके हैं, प्रत्येक शीर्ष पर एक बार जाना, लेकिन हम केवल उन दौरों में रुचि रखते हैं जो वजन में न्यूनतम हैं। इस कार्य को ट्रैवलिंग सेल्समैन समस्या कहा जाता है। इस कार्य के लिए सबसे खराब ज्ञात एल्गोरिदम लगभग एक ही समय में चलते हैं। । हम इस तरह के कार्यों के लिए एल्गोरिदम के त्वरण में लगे हुए थे। उदाहरण के लिए, एक एल्गोरिथ्म जो समय में काम करता है , n के बड़े मूल्यों के लिए समस्या का समाधान करेगा। यह ध्यान रखना दिलचस्प है कि 1000 गुना तेजी से चलने वाले कंप्यूटर को खरीदने से इस तरह के त्वरण नहीं होगा जैसे कि रनटाइम में एक छोटे घातांक के साथ नया एल्गोरिदम। इस समस्या के लिए एक बहुपद एल्गोरिथ्म का अस्तित्व कक्षाओं पी और एनपी की समानता को दर्शाता है, और इस तरह के एल्गोरिथ्म की अनुपस्थिति के प्रमाण का मतलब होगा कि ये कक्षाएं समान नहीं हैं।

ट्रैवलिंग सेल्समैन की समस्या

ग्राफ का एक हैमिल्टन चक्र एक ऐसा चक्र होता है, जो ग्राफ के प्रत्येक शीर्ष पर ठीक एक बार जाता है। ट्रैवल सेल्समैन की समस्या ( TSP ) किसी दिए गए भारित ग्राफ में न्यूनतम वजन के हेमिल्टन चक्र को खोजना है। मूल ग्राफ के शीर्षों की संख्या और M के किनारे के अधिकतम वजन के आधार पर निरूपित करें। यात्रा सेल्समैन समस्या को हल करने के लिए कई तरीके हैं, लेकिन इस लेख में हम केवल सबसे खराब स्थिति में रनटाइम के लिए अनुमानित अनुमानों के साथ सैद्धांतिक एल्गोरिदम के बारे में बात करेंगे।

यात्रा विक्रेता समस्या को हल करने के लिए सटीक एल्गोरिदम

1962 में, एक गतिशील प्रोग्रामिंग एल्गोरिदम विकसित किया गया था जो समय में टीएसपी को हल करता है। लेकिन घातीय का उपयोग कर स्मृति। केवल बहुपद स्मृति का उपयोग करके सबसे अच्छा ज्ञात एल्गोरिथ्म रनटाइम है। । मध्यवर्ती परिणाम भी ज्ञात हैं, उदाहरण के लिए, किसी भी के लिए , समय के साथ समस्या को हल करने के लिए एक एल्गोरिथ्म है मेमोरी का उपयोग करना जहाँ । समय पर समस्या को हल करने वाले समावेश-अपवाद सूत्र के आधार पर ज्ञात एल्गोरिदम मेमोरी का उपयोग करना । इनपुट लंबाई से बहुपद कारकों को छिपाता है, अर्थात्। । टीएसपी के गैर-उन्मुख मामले के लिए ऑपरेटिंग समय के साथ एक मोंटे कार्लो एल्गोरिदम है और एक तेजी से त्रुटि की छोटी संभावना है।

पचास वर्षों से, निम्नलिखित प्रश्न खुले हैं:

1. रनटाइम के साथ टीएसपी के लिए एक एल्गोरिथ्म का अस्तित्व और बहुपद स्मृति।
2. रनटाइम के साथ टीएसपी के लिए एक एल्गोरिथ्म का अस्तित्व यात्रा विक्रेता समस्या के सामान्य (उन्मुख) मामले के लिए।

ट्रैवलिंग सेल्समैन समस्या को हल करने के लिए अनुमानित एल्गोरिदम

यह ज्ञात है कि धारणा के तहत कुल TSP को किसी भी बहुपद रूप से कम्प्यूटेशनल कारक के साथ नहीं लगाया जा सकता है। यही है, इस धारणा में, इष्टतम समाधान के केवल 10-सन्निकटन को खोजने के लिए असंभव है, लेकिन यहां तक ​​कि एन! एक विशेष मामला जिसमें एक ग्राफ के किनारों का वजन त्रिकोण की असमानता को संतुष्ट करता है, उसे मीट्रिक ट्रैवलिंग सेल्समैन समस्या कहा जाता है । गैर-मीट्रिक मीट्रिक समस्या के लिए, 1.5-सन्निकटन ज्ञात है। फिर भी इस विशेष मामले के लिए यह ज्ञात है कि धारणा के तहत , आप एक सन्निकटन बेहतर के साथ एक बहुपद एल्गोरिथ्म नहीं मिल सकता है (उन्मुख मामले में - )। समस्या के उन्मुख मीट्रिक संस्करण के लिए, हाल ही में सन्निकटन कारक में सुधार किया गया है ।

घातीय समय दृष्टिकोण

हम एक एल्गोरिथ्म का प्रस्ताव करते हैं जो किसी भी निश्चित के लिए है का उपयोग करता है कंप्यूटिंग के लिए कदम और बहुपद स्मृति उन्मुख मैट्रिक यात्रा विक्रेता समस्या के परिवर्तन। जैसा कि ऊपर उल्लेख किया गया है, टीएसपी के गैर-उन्मुख मीट्रिक संस्करण के लिए भी सबसे प्रसिद्ध बहुपद अनुमान है, 1.5 है (उन्मुख के लिए) )।
अगर , तो बहुपद के लिए समय नहीं मिल सकता है एक गैर-उन्मुख मीट्रिक टीएसपी का एकीकरण।
अगर हमें जरूरत है, उदाहरण के लिए, -प्रतिरोध, तो हमें सटीक एल्गोरिदम का उपयोग करना चाहिए जिसमें या तो घातीय मेमोरी या समय की आवश्यकता होती है । एक्सपोनेंशियल एल्गोरिदम का उपयोग शायद ही कभी किया जाता है, लेकिन किसी भी मामले में, हम उन्हें चलाने में सक्षम होते हैं और जवाब का इंतजार करते हैं। हालाँकि, यदि एल्गोरिथ्म घातीय मेमोरी का उपयोग करता है, तो हम एल्गोरिथ्म को उचित आकार के इनपुट पर भी नहीं चला सकते हैं।
प्रस्तावित एल्गोरिथ्म पा सकते हैं समय के साथ कुल TSP की अस्वीकृति केवल बहुपद स्मृति का उपयोग करना।

विकसित एल्गोरिथ्म इबारा, किम के काम में बैकपैक समस्या के लिए एक पूरी तरह से बहुपद अनुमानित योजना के निर्माण के लिए प्रस्तावित विचार का उपयोग करता है। लेखक समय के साथ काम करने वाली एक बैकपैक समस्या के लिए एक छद्म-बहुपद एल्गोरिथ्म का उपयोग करते हैं जहाँ n आइटमों की संख्या है और W बैकपैक की क्षमता है।
बैकपैक समस्या के लिए पूरी तरह से बहुपद सन्निकटन योजना पहले सभी वस्तुओं के वजन को विभाजित करती है , तो pseudopolynomial एल्गोरिथ्म कहता है। प्राप्त उत्तर इष्टतम नहीं हो सकता है, क्योंकि कुछ वजन सिर्फ में विभाजित नहीं हैं लेकिन यह भी गोल। हालांकि, एक सरल विश्लेषण से पता चलता है कि गोलाई परिणाम को बहुत प्रभावित नहीं करती है।

हम एक समान विचार का उपयोग करते हैं। ऑप्ट द्वारा हम इष्टतम समाधान TSP निरूपित करते हैं। मेमोरी एल्गोरिथ्म से एक अनुमानित बहुपद प्राप्त करने के लिए, हम पहले सभी किनारों के वजन को एक पर्याप्त संख्या में विभाजित करते हैं। , फिर समावेश-अपवाद सूत्र के आधार पर सटीक एल्गोरिथ्म चलाएं। परिणामी एल्गोरिथ्म का चलने का समय बराबर होगा और परिणामी चक्र की लंबाई अधिक नहीं होगी । अब हम चुनना चाहते हैं ताकि और । टीएसपी के मीट्रिक संस्करण को बहुपद समय में अनुमानित किया जा सकता है, उदाहरण के लिए, एक कारक के साथ । यानी हम पा सकते हैं कि और ले लो । फिर परिणामी एल्गोरिथ्म में एक रन समय होगा और मेमोरी का उपयोग करें । हम इस परिणाम को सामान्य (गैर-मीट्रिक उन्मुख) ट्रैवलिंग सेल्समैन समस्या के मामले में सामान्य बनाने में भी कामयाब रहे।