تم إصدار كتاب "برمجة الأولمبياد"

نشرت دار النشر "DMK Press" كتاب "برمجة الأولمبياد" بعنوان "دراسة وتحسين الخوارزميات في المسابقات". لقد أصبح نفسا منعشًا لكل من يهتم ويستعد ويستعد للمشاركة ، أو يخطط فقط في المستقبل ، في مثل هذا النوع من النشاط الفكري مثل مختلف أنشطة البرمجة الرياضية. في روسيا ، ليسوا على دراية جيدة.

تم نشر النسخة الروسية من كتاب "دليل البرمجة التنافسية" (Springer International Publishing AG) بدعم من معهد موسكو للفيزياء والتكنولوجيا ورئيسه أليكسي ماليف ، مجموعة Mail.Ru ، وكذلك مشروع Moscow Workshops ICPC.

"أصبحت برامج أوليمبياد تزداد شعبية بين الطلاب والطلاب كل عام. مثال رائع على ذلك هو أننا في عام 2019 ، سنقوم نحن ، في ورش عمل موسكو في ICPC ، في شهر نوفمبر بإجراء الاستعدادات العاشرة للمعسكر التدريبي لكأس العالم في أنحاء مختلفة من العالم ، لقد مروا بالفعل في سنغافورة وأوروبا وأمريكا الجنوبية وروسيا - من فلاديفوستوك إلى موسكو. في بداية شهر أكتوبر ، عقدت مسابقة البرمجة في موسكو في موسكو ، وشارك فيها 2284 شخصًا في 18 موقعًا في جامعات موسكو - وهذا رقم قياسي في المسابقة التي عقدت بدعم من Rosmolodezh.

نحن سعداء للغاية بالاهتمام الحيوي الذي يبديه الشباب ، ونحن مستعدون لدعمه بكل الطرق - على سبيل المثال ، بالنسبة لطلاب جامعات موسكو ، فإننا نقوم بإجراء تدريب مجاني لـ ICPC بمشاركة أفضل المدربين. وبالطبع ، من المفيد للمشاركين دائمًا دمج المواد وتفكيك المهام وتعزيز معارفهم. لذلك ، أنا سعيد جدًا أن كتابك قد ظهر ، وأهنئنا جميعًا على هذا. نأمل أن يكون في نهائيات ICPC في موسكو في يونيو 2020 ، أولئك الأشخاص الذين قرأوها ويصبحون أبطال النسخة الثانية المكملة. "

أليكسي ماليف ، مدير المباراة النهائية لكأس العالم ICPC 2020 في موسكو ، نائب رئيس MIPT ، مؤسس مشروع ورش عمل موسكو ICPC.

تمت ترجمة "دليل البرمجة التنافسية" إلى الروسية من الإنجليزية. بالإضافة إلى الإنجليزية والروسية ، تم إصدار المنشور باللغة الكورية.

مؤلف الكتاب هو أنتي لاكسونين ، وهو مدرس وباحث من جامعة هلسنكي آلتو (فنلندا) [3] يتمتع بخبرة واسعة في تدريس البرمجة والخوارزميات ، ومدرب فريق فنلندا في مسابقات البرمجة الدولية. لديه درجة عالية من 2347 وحالة "الدولية سيد" على بوابة Codeforces تحت لقب "pllk" [4]. في عام 2008 ، أصبح أ. لاكسونين أحد منظمي أولمبياد المعلوماتية في بلاده. في عام 2016 - المشرف العلمي لأولمبياد البلطيق في المعلوماتية.

جميع الجمهور المستهدف من الكتاب مهتمون و / أو يعملون في مجال برمجة الأولمبياد. ولكن ، من أجل الاستيعاب الكامل للمواد ، يلزم معرفة أساسيات البرمجة ، في حين أن المؤلف لا يطلب من القارئ تجربة تصميم الخوارزميات والمشاركة في المسابقات. كل هذا يسمح لنا أن نوصي بهذا العمل لمجموعة واسعة من القراء المهتمين. بالنسبة للمبتدئين ، ستصبح مقدمة لبرامج أوليمبياد الحديثة ، سيساعد المتخصصون المتمرسون في تنظيم المعرفة ، وسيصبحون أداة مرجعية لهم.

يتم تقديم المواد في الكتاب من البسيط إلى المعقد. أولاً ، تعرف على أهداف وغايات الكتاب ، وبرمجة الأولمبياد ، ومجموعة المهام CSES [5] وغيرها من الكتب ذات الصلة حول برمجة أوليمبياد.

بعد تلقي القاعدة النظرية اللازمة ، سيكون القارئ جاهزًا للممارسة. تقنية البرمجة هي الموضوع التالي. في ذلك ، تضمن المؤلف أساسيات لغة C ++ (معيار C11) ، والتي تنفذ جميع الأمثلة في الكتاب ؛ تحليل الخوارزميات العودية والعمليات bitwise.

في فصول الكتاب ، سيتمكن القارئ من العثور على معلومات حول معظم الموضوعات "القياسية" وأمثلة على تنفيذ الخوارزميات المقدمة للمشاركين في برمجة أولمبياد: هياكل البيانات ، البرمجة الديناميكية ، خوارزميات الرسم البياني وخوارزمية الأشجار ، واستعلامات النطاق ، ومعالجة الصفوف.

بشكل منفصل ، أود تسليط الضوء على عدد من فصول الكتاب. على سبيل المثال ، الفصل "قضايا تصميم مختارة للخوارزميات". وشملت الخوارزميات مع عرض مواز للتصريف ، وتحليل الاستهلاك ، وإيجاد الحد الأدنى من القيم. يُقدم للقارئ خوارزميات لإيجاد مسافة Hamming ، وحل مشكلة التحصيل في الرسوم البيانية ، وطريقة المؤشر المزدوج ، والبحث الثلاثي ، وتقليل المبالغ وغيرها من الموضوعات المثيرة للاهتمام لـ "Olympiad" والمدربين.

كمثال ، سأقدم مثالًا للمهام من الفصل "أسئلة مختارة لتصميم الخوارزميات".

دعونا نأخذ في الاعتبار الخوارزميات ذات العرض المتوازي للبتات التي تستخدم فيها عمليات البت في معالجة البيانات بكفاءة. في الحالة النموذجية ، يمكننا استبدال حلقة for بعمليات bitwise ، مما يقلل بشكل كبير من وقت تشغيل الخوارزمية.

خوارزميات التصفح المتوازي

تستند الخوارزميات ذات العرض المتوازي للأرقام إلى حقيقة أن الأرقام الفردية للرقم يمكن معالجتها بالتوازي باستخدام عمليات bitwise. لذلك ، تتمثل إحدى طرق تصميم الخوارزميات في تقديم خطوات الخوارزمية بطريقة يمكن تنفيذها بفعالية باستخدام عمليات bitwise.

هامينغ المسافة هامينج المسافة

هامينج (أ ، ب) بين السطور أ و ب من نفس الطول هو عدد المواضع التي تختلف فيها هذه السطور. على سبيل المثال:

هامينغ (01101 ، 11001) = 2.

ضع في اعتبارك المهمة التالية: إعطاء سلاسل n ذات طول k ، قم بحساب مسافة Hamming الدنيا بين سلسلتين. على سبيل المثال ، بالنسبة للسطور [00111 ، 01101 ، 11110] ، ستكون الإجابة 2 ، لأن

• هامينغ (00111 ، 01101) = 2 ؛
• هامينغ (00111 ، 11110) = 3 ؛
• هامينغ (01101 ، 11110) = 3.

يمكن حل المشكلة "وجهاً لوجه" عن طريق حساب المسافة Hamming بين كل سطرين. التعقيد الزمني لهذه الخوارزمية هو (ن

$$

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

ك). لحساب المسافة بين السطور a و b ، استخدم الوظيفة التالية:

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

ولكن بما أن السلاسل تتكون من وحدات بت ، يمكن تحسين الحل عن طريق تخزين السلاسل كأعداد صحيحة وحساب المسافة بينها باستخدام عمليات bitwise. على وجه الخصوص ، إذا كانت k ≤ 32 ، فيمكن عندئذٍ تخزين السلاسل كقيم من النوع int ولحساب المسافة ، استخدم هذه الوظيفة:

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

هنا تقوم العملية EXCLUSIVE OR ببناء خط تكون فيه الوحدات في المواضع التي تختلف فيها a و b. ثم يتم حساب عدد أرقام الوحدات بواسطة الدالة __builtin_popcount. يوضح الجدول نتائج مقارنة الخوارزمية الأصلية والخوارزمية مع عرض موازٍ للبتات من حيث وقت التشغيل على جهاز كمبيوتر حديث. تبين أن الخوارزمية ذات العرض المتوازي للبت أسرع بنحو 20 مرة.

جدول: مدة تشغيل الخوارزميات التي تحسب الحد الأدنى لمسافة Hamming لسلسلة n ذات طول k = 30



لا يستحق الفصلان "الرياضيات" و "الهندسة" الاهتمام. كما تخمين القارئ بالفعل ، فهي مكرسة لحل المشاكل الرياضية والهندسية عن طريق لغة البرمجة C ++ وبناء الخوارزميات المناسبة. في الفصل "الرياضي" ، تنتظرنا خمسة موضوعات رئيسية: "نظرية الأعداد" ، "Combinatorics" ، "المصفوفات" ، "الاحتمالات" و "نظرية الألعاب". وفي "الهندسية": "الوسائل التقنية في الهندسة" ، "الخوارزميات المبنية على خط الكنس". وبالتالي ، فإن العرض المعقد لبناء الخوارزميات لحل المشكلات الرياضية والهندسية يجعل الكتاب "اكتشافًا" لـ "olympiadniki" ، لأنه على خلفية نقص الكتب حول هذا الموضوع ، فإن هذا أمر نادر الحدوث.

بعدد من المشكلات ، قرر المؤلف أن يضع في الفصل "مواضيع إضافية". تطورهم "في بعض الأحيان يمكن أن يساعد في حل أصعب مشاكل أولمبياد". هذه هي "الجذر التربيعي في الخوارزميات" ، و "مرة أخرى حول أشجار المقاطع" ، و "دوقية" ، و "تحسين البرمجة الديناميكية" و "متنوعة". بناءً على اسم التفسير الإضافي ، فإنها تتطلب عناوين فرعية لأشجار المقاطع وأشياء مختلفة.

بالنسبة لأشجار الشرائح ، سيتعرف القارئ على الانتشار الكسول ، والأشجار الديناميكية ، وهياكل البيانات في القمم ، والأشجار ثنائية الأبعاد. وفي "متنوعة" ، ينتظر: اجتماع في الوسط (يقسم مساحة البحث إلى جزأين ، متساوٍ تقريبًا ، يُجري بحثًا في كل جزء ، ثم يجمع النتائج) ، مجموعات العد ، البحث الثنائي الموازي ، الاتصال الديناميكي.

أكمل معلومات مرجع الكتاب عن الرياضيات وببليوغرافيا واسعة النطاق (32 مصدرًا).

لذلك ، يعد كتاب "برمجة الأولمبياد" للمخرج Antti Laaxsonen مقدمة ممتازة لعالم البرمجة الرياضية. في الوقت نفسه ، دليل مرجعي رائع. الكتاب مناسب للمبتدئين "olympiadnikov" وسيساعد في تنظيم المعرفة من ذوي الخبرة. سيكون من المفيد للمدربين.

مرة أخرى ، نلاحظ أن جميع الأمثلة الواردة في الكتاب يتم تنفيذها بلغة برمجة C ++. هو الأكثر طلبا في الأولمبياد. لكن قد يجد شخص ما هذا عيبًا في الكتاب ، لأن اللغات الأخرى شائعة - Python، Java. يمكن لأولئك الذين يفضلون لغات البرمجة هذه حل المشكلات المقترحة في كتاب بلغتهم المفضلة. سيكون هذا تمرين جيد. في نهاية المطاف ، يتم تحديد مهام أوليمبياد بالتحديد في البحث عن الحل الأمثل.

تم إعداد المقال من قبل: إيغور Shtompel ، مؤلف ومقدم قسم "الوظيفي \ التعليم" في مجلة "مسؤول النظام"