क्या किसी को कैनोलिक सीएस समस्याओं के लिए एक अच्छा संदर्भ पता है?कैननिकल समस्याएं सूची
मैं "सॉर्टिंग समस्या", "बिन पैकिंग समस्या", "उत्पीड़ित विक्रेता समस्या" और क्या नहीं जैसी चीजों के बारे में सोच रहा हूं।
संपादित करें: वेबसाइटों को प्राथमिकता दी
आप शायद Introduction to Algorithms की तरह एक एल्गोरिदम पाठ्यपुस्तक में सबसे अच्छा मिल सकता है। यद्यपि मैंने कभी भी उस विशेष पुस्तक को कभी नहीं पढ़ा है, यह पूरी तरह से होने के लिए काफी प्रसिद्ध है और शायद आपको जिन समस्याओं का सामना करना पड़ सकता है उनमें से अधिकांश में शामिल होंगे।
"Computers and Intractability: A guide to the theory of NP-Completeness" गैरी और जॉनसन द्वारा इस तरह की चीज के लिए एक महान संदर्भ है, हालांकि "हल" समस्याओं (पी में) स्पष्ट रूप से पुस्तक में अधिक ध्यान नहीं दिया जाता है।
मुझे किसी भी अच्छे ऑन-लाइन संसाधनों से अवगत नहीं है, लेकिन कटौती और जटिलता पर कार्प का मौलिक पेपर Reducibility among Combinatorial Problems (1972) शायद हार्ड समस्याओं के लिए "कैननिकल" संदर्भ है।
क्या आपने विकिपीडिया के Category:Computational problems और Category:NP Complete Problems पृष्ठों पर देखा है? यह शायद पूरा नहीं है, लेकिन वे अच्छे शुरुआती बिंदुओं की तरह दिखते हैं। विकिपीडिया सीएस विषयों में बहुत अच्छा प्रदर्शन करता प्रतीत होता है।
@rcreswick उन अच्छे संदर्भों की तरह ध्वनि है लेकिन मैं जो सोच रहा हूं उसके बारे में थोड़ा शर्म आती है। (हालांकि, मुझे पता है कि यह सबसे अच्छा है)
मैं उम्मीद में स्वीकार्य कुछ भी चिह्नित नहीं कर रहा हूं कि लोगों को बेहतर संदर्भ मिल सकता है।
इस बीच, मैं यहाँ कुछ समस्याओं को सूचीबद्ध करने के लिए जा रहा हूँ, और अधिक
छँटाई समस्या को जोड़ने के लिए मुक्त गिर गया एक सेट है कि किसी भी तरह से
का इन monotonic है के लिए एक आदेश का पता लगाएं बिन पैकिंग समस्या विभाजन एक सेट सेट की एक न्यूनतम संख्या जहां प्रत्येक सबसेट "छोटे" कुछ सीमा से अधिक है
travailing विक्रेता की समस्या एक weig में एक Hamiltonian चक्र का पता लगाएं में न्यूनतम कुल वजन
मुझे लगता है कि आपको केवल एक ही पुस्तक में उन सभी समस्याओं का उत्तर मिल जाएगा। मैंने कभी भी एल्गोरिदम पर कोई सभ्य, व्यापक वेबसाइट नहीं देखी है, इसलिए मैं आपको पुस्तकों से चिपकने की सलाह दूंगा। उस ने कहा, आप हमेशा कैनोलिक एल्गोरिदम ग्रंथों पर कुछ प्रारंभिक सामग्री प्राप्त कर सकते हैं (हमेशा तीन बार मैं अनुशंसा करता हूं: CLRS, Manber, Aho, Hopcroft and Ullman (यह कुछ महत्वपूर्ण विषयों में थोड़ा सा पुराना है, लेकिन यह बहुत औपचारिक और अच्छी तरह से लिखा गया है कि यह एक जरूरी है)। उनमें से सभी महत्वपूर्ण संयोजन संबंधी समस्याएं हैं, कुछ अर्थों में, कंप्यूटर विज्ञान में कैनोलिक समस्याएं हैं। ग्राफ सिद्धांत में कुछ बुनियादी सिद्धांतों को सीखने के बाद आप नेटवर्क प्रवाह और रैखिक प्रोग्रामिंग में स्थानांतरित करने में सक्षम होंगे। तकनीकों का एक सेट शामिल है जो अंततः आपको सबसे अधिक समस्याओं का समाधान करेगा (पूर्णांक मानों तक सीमित चर के साथ रैखिक प्रोग्रामिंग एनपी-हार्ड है)। नेटवर्क बहुत दिलचस्प अनुप्रयोगों के साथ ग्राफ (भारित/कैपेसिटेड किनारों के साथ) पर परिभाषित समस्याओं से निपटता है उन क्षेत्रों में जो प्रतीत होता है कि ग्राफ सिद्धांत के साथ कोई संबंध नहीं है। इस पर पाठ्यपुस्तक Ahuja, Magnanti and Orlin's है। रैखिक प्रोग्रामिंग है नेटवर्क प्रवाह के किसी प्रकार का सुपरसेट, और समीकरणों के रैखिक तंत्र के रूप में प्रतिबंधों के अधीन चर पर एक रैखिक कार्य को अनुकूलित करने के साथ सौदों।एक पुस्तक जो नेटवर्क प्रवाह के संबंधों पर जोर देती है वह Bazaraa's है। फिर आप पूर्णांक प्रोग्रामिंग पर जा सकते हैं, एक बहुत ही मूल्यवान टूल जो बिन पैकिंग, कार्य शेड्यूलिंग, knapsack समस्या, आदि जैसे मॉडलिंग समस्याओं के लिए कई प्राकृतिक तकनीक प्रस्तुत करता है। एक अच्छा संदर्भ L. Wolsey's पुस्तक होगी।
आप निश्चित रूप से एनआईएसटी के Dictionary of Algorithms and Data Structures पर देखना चाहते हैं। यह traveling salesman problem, Byzantine generals problem, dining philosophers' problem, knapsack problem (= अपने "बिन पैकिंग समस्या", मुझे लगता है), cutting stock problem, eight queens problem, knight's tour problem, busy beaver problem, halting problem, आदि आदि
यहमिला है firing squad synchronization problem (मुझे उस चूक के बारे में हैरान है) या Jeep problem (कंप्यूटर विज्ञान से अधिक रसद) नहीं है।
दिलचस्प बात यह है कि codinghorror.com पर एक ब्लॉग है जो इनमें से कुछ के बारे में पहेली रूप में बात करता है। (मैं याद कर सकते हैं नहीं है कि क्या मैं पढ़ा है Smullyan के किताब ब्लॉग में उद्धृत है, लेकिन वह पहेली का एक अच्छा संकलक & दार्शनिक चिंतन है। मार्टिन गार्डनर और डगलस होफस्टैड्टर और H.E. Dudeney अन्य।)
भी हो सकता है की जाँच Stony Brook Algorithm Repository।
(या गूगल पर "मिश्रित समस्याओं", को देखने या Wolfram Mathworld में "समस्या" के लिए खोज या Hilbert's problems को देखो, लेकिन इन सभी लिंक में उनमें से कई कंप्यूटर विज्ञान की तुलना में अधिक शुद्ध गणित कर रहे हैं।)
बिन पैकिंग एक नापसंद है, लेकिन आप सब कुछ डालते हैं और बिन गिनती को कम करते हैं – BCS
नोट : मैं समाधान की सूची की तुलना में समस्याओं की सूची की तलाश में हूं। वैसे भी अच्छा जवाब। – BCS