"ओलंपियाड प्रोग्रामिंग" पुस्तक का विमोचन किया गया है

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

गाइड टू कॉम्पिटिटिव प्रोग्रामिंग (स्प्रिंगर इंटरनेशनल पब्लिशिंग एजी) के रूसी संस्करण को एमआईपीटी आईटी एजुकेशन डेवलपमेंट सेंटर और इसके निदेशक एलेक्सी मालेव, मेल.रू ग्रुप, साथ ही मॉस्को वर्कशॉप्स ICPC प्रोजेक्ट के समर्थन से प्रकाशित किया गया था।

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

हम लोगों की गहरी रुचि के बारे में बहुत खुश हैं, और हर तरह से इसका समर्थन करने के लिए तैयार हैं - उदाहरण के लिए, मास्को विश्वविद्यालयों के छात्रों के लिए हम सर्वश्रेष्ठ प्रशिक्षकों की भागीदारी के साथ ICPC के लिए मुफ्त प्रशिक्षण आयोजित करते हैं। और, ज़ाहिर है, यह प्रतिभागियों के लिए सामग्री को समेकित करने, कार्यों को इकट्ठा करने और उनके ज्ञान को बढ़ाने के लिए हमेशा उपयोगी होता है। इसलिए, मुझे बहुत खुशी है कि आपकी पुस्तक सामने आई है, और मैं हम सभी को इसके लिए बधाई देता हूं। हमें उम्मीद है कि जून 2020 में मास्को में ICPC के फाइनल में पहले से ही वे लोग होंगे जो इसे पढ़ेंगे और दूसरे, पूरक संस्करण के नायक बनेंगे। ”

एलेक्सी मालेव, मास्को में ICPC 2020 विश्व कप के फाइनल के निदेशक, MIPT के उप-रेक्टर, मास्को कार्यशालाओं ICPC परियोजना के संस्थापक।

"गाइड टू कॉम्पिटिटिव प्रोग्रामिंग" को अंग्रेजी से रूसी में अनुवादित किया गया है। अंग्रेजी और रूसी के अलावा, कोरियाई में प्रकाशन जारी किया गया था।

पुस्तक की लेखिका एंटिटी लैक्सनसन हैं, जो एक शिक्षक और हेलसिंकी ऑल्टो (फिनलैंड) विश्वविद्यालय से शोधकर्ता हैं [3] जो शिक्षण प्रोग्रामिंग और एल्गोरिदम में व्यापक अनुभव के साथ, और अंतरराष्ट्रीय प्रोग्रामिंग प्रतियोगिताओं में फिनलैंड टीम के कोच हैं। उनके पास 2347 की उच्च रेटिंग है और उपनाम "pllk" [4] के तहत कोडफोर्स पोर्टल पर "अंतर्राष्ट्रीय मास्टर" की स्थिति है। 2008 में, वह A. Laaxsonen अपने देश में Informatics Olympiad के आयोजकों में से एक बने। 2016 में - सूचना विज्ञान में बाल्टिक ओलंपियाड के वैज्ञानिक पर्यवेक्षक।

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

पुस्तक में सामग्री का प्रस्तुतिकरण सरल से जटिल तक किया जाता है। सबसे पहले, वह ओलंपियाड प्रोग्रामिंग, कार्यों सीएसईएस [5] और ओलंपियाड प्रोग्रामिंग पर अन्य प्रासंगिक पुस्तकों के संग्रह के साथ पुस्तक के लक्ष्यों और उद्देश्यों से परिचित हो जाता है।

आवश्यक सैद्धांतिक आधार प्राप्त करने के बाद, पाठक अभ्यास के लिए आगे बढ़ने के लिए तैयार होगा। प्रोग्रामिंग तकनीक अगला विषय है। इसमें, लेखक ने C ++ भाषा (C11 मानक) की मूल बातें शामिल की, जो पुस्तक में सभी उदाहरणों को लागू करता है; पुनरावर्ती एल्गोरिदम और बिटवाइज़ संचालन का विश्लेषण।

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

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

एक उदाहरण के रूप में, मैं "एल्गोरिदम डिजाइनिंग के चयनित प्रश्नों" अध्याय से कार्यों का एक उदाहरण दूंगा।

आइए हम बिट्स के समानांतर देखने के साथ एल्गोरिदम पर विचार करें जिसमें कुशल डेटा प्रोसेसिंग के लिए बिटवाइज़ ऑपरेशन का उपयोग किया जाता है। एक विशिष्ट मामले में, हम बिटवाइज़ ऑपरेशंस के लिए लूप की जगह ले सकते हैं, जो कि एल्गोरिथ्म के रनिंग टाइम को काफी कम कर देता है।

समानांतर ब्राउजिंग एल्गोरिदम

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

हैमिंग दूरी हैमिंग दूरी

एक ही लंबाई की लाइनों के बीच और बीच में हैमिंग (ए, बी) उन पदों की संख्या है, जिन पर ये रेखाएं भिन्न होती हैं। उदाहरण के लिए:

हैमिंग (01101, 11001) = 2।

निम्नलिखित कार्य पर विचार करें: लंबाई k के n स्ट्रिंग्स को देखते हुए, दो स्ट्रिंग्स के बीच न्यूनतम हेमिंग दूरी की गणना करें। उदाहरण के लिए, लाइनों के लिए [00111, 01101, 11110], उत्तर 2 होगा, क्योंकि

• हैमिंग (00111, 01101) = 2;
• हैमिंग (00111, 11110) = 3;
• हैमिंग (01101, 11110) = 3।

हर दो पंक्तियों के बीच हैमिंग दूरी की गणना करके समस्या को "हेड-ऑन" हल किया जा सकता है। इस तरह के एक एल्गोरिथ्म की समय जटिलता है (एन

$$

$$O (n ^ 2k) 2$$

ट)। लाइनों और बी के बीच की दूरी की गणना करने के लिए, निम्नलिखित फ़ंक्शन का उपयोग करें:

int hamming(string a, string b) { int d = 0 for (int i = 0; i < k; i++) { if (a[i] != b[i]) d++; } return d; } 

लेकिन चूंकि स्ट्रिंग्स बिट्स से युक्त होते हैं, इसलिए समाधान को स्ट्रिंग्स को पूर्णांकों के रूप में संग्रहीत करके और बिटवाइज़ संचालन का उपयोग करके उनके बीच की दूरी की गणना करके अनुकूलित किया जा सकता है। विशेष रूप से, यदि k, 32 है, तो स्ट्रिंग्स को प्रकार के मान के रूप में संग्रहीत किया जा सकता है और इस फ़ंक्शन का उपयोग करके दूरी की गणना करने के लिए:

 int hamming(int a, int b) { return __builtin_popcount(a^b); } 

यहाँ EXCLUSIVE या ऑपरेशन एक पंक्ति बनाता है जिसमें इकाइयाँ उन स्थितियों में होती हैं जहाँ a और b भिन्न होते हैं। तब इकाई अंकों की संख्या __builtin_popcount फ़ंक्शन द्वारा गणना की जाती है। तालिका एक आधुनिक कंप्यूटर पर रन टाइम के संदर्भ में बिट्स के समानांतर दृश्य के साथ मूल एल्गोरिथ्म और एल्गोरिथ्म की तुलना करने के परिणामों को दिखाती है। बिट्स के समानांतर देखने के साथ एल्गोरिथ्म लगभग 20 गुना तेजी से निकला।

तालिका: लंबाई k = 30 के बिट स्ट्रिंग्स के लिए न्यूनतम हैमिंग दूरी की गणना करने वाले एल्गोरिदम का समय चल रहा है



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

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

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

गणित और एक व्यापक ग्रंथ सूची (32 स्रोत) पर पुस्तक संदर्भ जानकारी को पूरा करें।

तो, एंटिटी लाक्सनसन की पुस्तक "ओलंपियाड प्रोग्रामिंग" खेल प्रोग्रामिंग की दुनिया के लिए एक उत्कृष्ट परिचय है। उसी समय, एक अद्भुत संदर्भ गाइड। पुस्तक शुरुआती "ओलंपियाडनिकोव" के लिए उपयुक्त है और अनुभवी ज्ञान को व्यवस्थित करने में मदद करेगी। यह कोचों के लिए उपयोगी होगा।

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

लेख द्वारा तैयार किया गया था: इगोर Shtompel, लेखक और "प्रशासक" पत्रिका में "कैरियर" शिक्षा के प्रस्तुतकर्ता "प्रशासक"