ओलंपियाड प्रोग्रामिंग कार्य: किस तरह का जानवर?

हाल ही में, हमने खेल प्रोग्रामिंग में कार्यों की एक प्रतियोगिता की घोषणा की। प्रतियोगिता के आयोजकों ने एबीबीवाई ब्लॉग पर प्रतियोगिता के बारे में एक छोटी घोषणा लिखने के लिए कहा, लेकिन सख्त संपादक ने यह बताते हुए घोषणा को छापने से इनकार कर दिया कि ओलंपियाड समस्या क्या है। इससे एक संपूर्ण लेख का जन्म हुआ। आइए एक ओलंपियाड समस्या के उदाहरण से शुरू करें।

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

ओलंपियाड समस्या का समाधान प्रोग्रामिंग भाषाओं में से एक में लिखा गया प्रोग्राम है। सबसे लोकप्रिय भाषाएं हैं: सी ++, सी #, जावा, पास्कल। आप कह सकते हैं कि पास्कल लंबे समय से बाहर हैं। हालांकि, इसे कम मत समझना! अनुभवी खेल प्रोग्रामर पास्कल में मानक एल्गोरिदम लिखने में सक्षम हैं, जो पहले से ही सी ++ में हैं, एक सामान्य व्यक्ति की तुलना में तेजी से कार्य की स्थिति पढ़ेगी :) वैसे, क्योंकि प्रतिभागी अपने आप एक प्रोग्रामिंग भाषा चुनते हैं, एक जोखिम है जो गैर-इष्टतम विकल्प बनाता है । सबसे पहले, सभी भाषाओं में समाधान मौजूद नहीं हैं, और दूसरी बात, कुछ भाषाओं में लिखे गए समाधान दूसरों की तुलना में कम कुशलता से काम कर सकते हैं।

वापस शर्तों की चर्चा के लिए। ओलंपियाड कार्य बहुत औपचारिक हैं :

• सख्त इनपुट / आउटपुट प्रारूप, कभी-कभी रिक्त स्थान और लाइन फ़ीड के लिए भी सटीक;
• नियम, एक नियम के रूप में, एक सख्त स्पष्ट व्याख्या है। जहाँ ग्राहक टीके लिखना सीख सकते हैं!
• रनटाइम और उपयोग की गई मेमोरी पर सख्त सीमाएँ। वास्तविक विकास में, वे " हम चाहते हैं कि इस तरह के हार्डवेयर और ऐसे ओएस पर काम करना चाहते हैं " या " सुनो, तुम्हारा कार्यक्रम बहुत अधिक स्मृति खाता है " की शैली में कुछ कहेंगे। बहुत कम बार आप वाक्यांशों को सुन सकते हैं जैसे " आपका कार्यक्रम 1.5 सेकंड से अधिक नहीं चलना चाहिए " या " क्या आप 64 मेगाबाइट से अधिक मेमोरी का उपयोग करने की हिम्मत नहीं करते हैं ";
• सभी प्रारंभिक मूल्य सख्ती से सीमित हैं।

ऐसी सख्त औपचारिकता जायज है। प्रतियोगिता के प्रतिभागियों के सभी फैसलों की जाँच एक निश्चित सेट पर की जाती है, जो ओलंपियाड की जूरी द्वारा तैयार किया जाता है और आमतौर पर प्रतिभागियों को पहले से पता नहीं होता है।

अगली विशेषता कार्य विश्लेषण है। ओलंपियाड समस्या के लेखक के बारे में सोचता है कि कितने प्रतिशत प्रतिभागी इस तरह की समस्या को हल करेंगे, कितने समय तक (मिनटों तक), यह समस्या किस विषय से संबंधित है (उदाहरण के लिए, ग्राफ़ कार्य या लालची एल्गोरिथम कार्य)।

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

"क्लासिक" कार्यों के लिए समाधान का मूल्यांकन करने के कई तरीके हैं:

• यदि प्रतिभागी का समाधान सभी परीक्षणों पर सही तरीके से काम करता है, तो कार्य को हल माना जाता है। ऐसी रेटिंग प्रणाली का उपयोग एसीएम प्रतियोगिताओं में किया जाता है।
• निर्णय के लिए अंक प्रदान किए जाते हैं, जो कार्यक्रम द्वारा सफलतापूर्वक पारित किए गए परीक्षणों की संख्या पर निर्भर करते हैं। इस दृष्टिकोण का उपयोग अक्सर स्कूल ओलिंपियाड्स में किया जाता है: कोई भी प्रतियोगिता से नाराज नहीं होगा और कम से कम 0.5 अंक प्राप्त करेगा।
• परीक्षणों को समूहों में संयोजित किया जाता है, जिनमें से प्रत्येक के लिए निश्चित संख्या में अंक प्रदान किए जाते हैं। यह ध्यान दिया जाना चाहिए कि समूह के लिए अंक केवल तभी प्रदान किए जाते हैं जब समाधान समूह से सभी परीक्षणों पर सही ढंग से काम करता है। यह न्याय और प्रतिभागियों की संतुष्टि के बीच एक उचित समझौता है। एबीबीवाई कप ने निर्णयों के मूल्यांकन के इस रूप को बिल्कुल स्पष्ट किया;
• कभी-कभी प्रतिभागी को प्राप्त अंकों की संख्या उस समय पर निर्भर करती है जो समस्या को हल करने पर खर्च किया गया था। उदाहरण के लिए, इस तरह की प्रणाली का उपयोग कोडफोर्स और टॉपकोडर पर किया जाता है।

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

बेशक, कोई ओलिंपियाड समस्याओं की ख़ासियत के बारे में अंतहीन बात कर सकता है। हमने केवल सबसे महत्वपूर्ण बिंदुओं पर प्रकाश डाला। यदि आपके कोई प्रश्न या टिप्पणी है, तो टिप्पणियों में आपका स्वागत है। और अगर आप जानते हैं कि लेख में वर्णित कार्यों की रचना कैसे और प्यार करता है, तो हम इसके बारे में यहां बात कर सकते हैं ।

व्लादिमीर मिनियालोव, एनएलसी प्रौद्योगिकी विभाग,
रुज़ाना मिनीखमेटोवा, शैक्षिक परियोजनाओं का एक समूह।