थ्रेडिंग चैलेंज समानांतर प्रोग्रामिंग प्रतियोगिता शुरू करना

एक Boomburum सहकर्मी ने पहले ही एक समान राक्षस के कार्य राक्षस का स्क्रीनशॉट दिखाया । चार सॉकेट, प्रत्येक में Intel® Xeon® प्रोसेसर E7-4860 24MB कैश के साथ, और शीर्ष पर - 64 गीगाबाइट रैम। इस सारी दौलत का क्या करें? मेरे पास कुछ विचार हैं!



हम थ्रेडिंग चैलेंज 2011 समानांतर प्रोग्रामिंग प्रतियोगिता शुरू कर रहे हैं। प्रतिभागी इस मशीन तक पहुंच प्राप्त करेंगे, और विजेता सैन फ्रांसिस्को में आईडीएफ जाएंगे, जहां, मुझे उम्मीद है, इन चित्रों को नहीं दिखाया जाएगा। प्रतियोगिता का कार्य सभी उपलब्ध गुठली को 100% से डाउनलोड करना है, एक स्क्रीनशॉट लेना है और इसे हैबे पर रखना है! एक चुटकुला । इतना सरल नहीं है।

तो, प्रतियोगिता के बारे में

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

प्रतियोगिता के नियम इस प्रकार हैं: जटिलता की दो श्रेणियां हैं, "प्रवेश स्तर" और "उन्नत स्तर"। प्रत्येक श्रेणी में तीन गंभीर एल्गोरिथम समस्याएं होंगी। प्रत्येक पहेली के लिए 22 दिन दिए जाते हैं, निर्णय के लिए अंक प्रदान किए जाते हैं। बेशक, मुख्य रूप से एक ही मशीन पर मापी गई गति के लिए, लेकिन सभी प्रकार के बोनस वाले हैं। अपनी श्रेणी में अधिक अंक हासिल करने वाले तीनों को छोटे पुरस्कार ($ 150 से $ 500 तक) प्राप्त होंगे।

जैसे ही न्यायाधीश अंतिम, तीसरे कार्य का मूल्यांकन समाप्त करते हैं, हम प्रतिभागियों के लिए कुल राशि की गणना करेंगे और दो विजेताओं की घोषणा करेंगे - एक "प्रारंभिक" श्रेणी में और एक "उन्नत" श्रेणी में। वे आईडीएफ 2011 के लिए कैलिफोर्निया जाएंगे।

कार्य। सच कहूँ तो, प्रतियोगिता तैयार करने की प्रक्रिया में एल्गोरिदम को बैठकर पता लगाने का समय नहीं था। वे बहुत जटिल नहीं हैं, लेकिन ... चलो एक साथ सोचते हैं?

"प्रवेश स्तर" श्रेणी में पहला कार्य

मुझे उम्मीद है कि हर कोई "जीवन" खेल के बारे में जानता होगा? उन लोगों के लिए जो नहीं जानते हैं - एक निश्चित सतह है, कोशिकाओं में टूट गई है। एक कोशिका दो अवस्थाओं में हो सकती है: जीवित या मृत होना। एक पिंजरे में आठ पड़ोसी हैं। "जीवन" का कार्य निम्नलिखित नियमों के अनुसार आने वाली पीढ़ियों की कोशिकाओं का अनुकरण करना है: एक मृत कोशिका, जिसके ठीक बगल में तीन जीवित कोशिकाएँ हैं, जीवन के लिए आता है। दो या तीन जीवित पड़ोसियों के साथ एक जीवित कोशिका जीवित रहती है। यदि दो से कम या तीन से अधिक पड़ोसी हैं, तो सेल क्रमशः अकेलेपन या अतिवृद्धि से मर जाता है। मॉडलिंग के लिए एल्गोरिदम के बारे में "जीवन" पढ़ा जा सकता है, उदाहरण के लिए, rsdn.ru पर । डेटा संग्रहण और समांतरिकरण के संदर्भ में, अनुकूलन की बहुत गुंजाइश है।

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

"उन्नत स्तर" श्रेणी में पहला कार्य

बहुत बड़ी Masyu पहेली को हल करें। पहेली का सार: आयताकार क्षेत्र की कोशिकाओं में सफेद और काले घेरे होते हैं, आपको मंडलियों को ऊर्ध्वाधर और क्षैतिज खंडों से जोड़ने की आवश्यकता होती है ताकि एक बंद रेखा प्राप्त हो। लाइन को खुद को पार नहीं करना चाहिए, शाखा या एक सेल से दो बार गुजरना चाहिए। दो अतिरिक्त स्थितियां हैं: काले सर्कल के साथ सेल से गुजरने वाली रेखा को इसमें 90 डिग्री घूमना चाहिए, और अगली और पिछली कोशिकाओं को सीधे पारित किया जाना चाहिए, आप घुमा नहीं सकते। एक सफेद सर्कल के साथ कोशिकाओं में, विपरीत सच है - आपको दिशा बदलने के बिना सीधे सेल के माध्यम से जाना चाहिए, और अगले सेल में 90 डिग्री या पिछले सेल में (यानी कम से कम एक तरफ) बारी। नीचे दी गई तस्वीर एक छोटी मासीउ पहेली को सुलझाने का एक उदाहरण है। स्पष्ट कारणों के लिए, परीक्षण डेटा सेट काफी बड़ा होगा। विजेता वह है जो पहेली को तेजी से हल करता है।



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

प्रश्न (टिप्पणियाँ, सुझाव) यहीं से या किसी विशेष फ़ोरम में पूछे जा सकते हैं। प्रविष्टियां स्वीकार करने की अंतिम तिथि 9 मई है ।

UPD : तस्वीर को सही किया।

सभी सफल एल्गोरिदम पाता है! और कृपया, सितंबर के लिए कुछ भी महत्वपूर्ण योजना न बनाएं - शायद आप में से कुछ इंटेल® डेवलपर्स फोरम में जाएंगे।