Abstract
The article analyzes the peculiarities of the Olympiad tasks on computer science: distracting story, placing various important components of the problem in different places of the condition, non-standard mathematical models, non-standard combination of standard approaches, etc. Taking this into account, as well as the rather high complexity of such tasks, there is the problem of working out methodological approaches to teaching to solve such problems. The general schemes of solving the Olympiad tasks on computer science, proposed by various scientists participating in the Olympiad movement, are considered. Based on the own experience, one of them has been selected. One of the areas of dynamic programming, the so-called Knapsack Problems, is considered. There are given various modifications of Knapsack Problem; the ability to solve them is necessary to understand the solution of a more complex task related to dynamic programming. For these tasks are given appropriate mathematical formulas or program code. There are presented all stages of the application of the given scheme to the solving of a specific Olympiad task on computer science, which belongs to the class of Knapsack Problems and proposed by one of the authors at the Open International Student Programming Olympiad “KPI-OPEN 2017” named after S.O. Lebediev and V.M. Glushkov “KPI-OPEN 2017”: the analysis of the condition, the construction of a mathematical model, the construction of a general scheme of solving, refinement, implementation, testing and debugging, sending the program to check. An effective author’s method for solving this task is demonstrated. The program code for the solution is given in C++. It is noted that the important point in preparing for the Olympiads on computer science is the analysis of the tasks after the completion of each competition. Applying the proposed methodological approaches to training pupils or students for the Olympiads on computer science (programming), in our opinion, will increase the effectiveness of such training.References
Ю. Горошко, Інформаційне моделювання у підготовці майбутніх учителів математики та інформатики. Чернігів, Україна: Видавець Лозовий В. М., 2012.
В. Мельник, Задачник з програмування. Київ, Україна: Видавничий дім ”Шкільний світ”, 2006.
Літня школа з програмування (Ужгород, 31 липня – 7 серпня 2016 року) :Матеріали лекцій, умови та розбір задач . За ред. Олександра Міци, Сергія Оришича. Ужгород: Видавництво “ФОП Сабов А.М.”, 2017.
С. Оршанский “О решении олимпиадных задач по программированию формата ACMICPC”, Мир ПК - диск, №9, 2005.
С. Жуковський, “Аналіз, дослідження та розв’язування конкурсних задач під час учнівської олімпіади з інформатики”, Інформаційні технології в освіті, №5, с. 152-159, 2010. DOI: 10.14308/ite.
A. Chargueraud, M. Hiron “Teaching Algorithmics for Informatics Olympiads: The French Method” , OLYMPIADS IN INFORMATICS Tasks and Training Volume 2 2008 Selected papers of the International Conference joint with the XX International Olympiad in Informatics Cairo, Egypt, August 16–23, 2008. [Електронний ресурс]. Доступно: https://www.mii.lt/olympiads_in_informatics/files/volume2.pdf. Дата звернення: Вер. 27, 2018.
В. Мельник, Ю. Горошко, О. Міца “Огляд систем підготовки до олімпіад з інформатики в деяких країнах”, Актуальні питання сучасної інформатики, №5, с. 21-23, 2017.
Дванадцята відкрита міжнародна студентська олімпіада з програмування імені С. О Лебедєва і В. М. Глушкова “KPI-OPEN 2017” [Електронний ресурс]. Доступно: http://kpi-open.org/. Дата звернення: Лип. 17, 2018.
Інтернет-портал організаційно-методичного забезпечення дистанційних олімпіад з програмування для обдарованої молоді навчальних закладів України e-olimp [Електронний ресурс]. Доступно: https://www.e-olymp.com/. Дата звернення: Лип. 17, 2018.
REFERENCES (TRANSLATED AND TRANSLITERATED)
Y. Horoshko. Information modeling in the training of future teachers of mathematics and computer science. Chernihiv, Ukraine: Vydavets Lozovyi V.M., 2012. (in Ukrainian)
V. Melnyk. Taskbook on programming. Kyiv, Ukraina: Vydavnychyi dim :Shkilnyi svit”, 2006. (in Ukrainian)
Summer programming school (Uzhhorod, july 31 – august 7, 2016) :Materials of lectures, conditions and analysis of tasks .Edited by Oleksandr Mitsa, Serhii Oryshych. Uzhhorod: Vydavnytstvo “FOP Sabov A. M.”, 2017. (in Ukrainian)
S. Orshanskyi “About the solvingolympiad tasks on programming of format ACMICPC”, Mir P:K - disk,№9, 2005. (in Russian)
S. Zhukovskyi, “The analysis, research and solution of problems during the students Olympiad in informatics”, Informatsiini tekhnolohii v osviti, №5, p. 152-159, 2010. DOI: 10.14308/ite. (in Ukrainian)
A. Chargueraud, M. Hiron “Teaching Algorithmics for Informatics Olympiads: The French Method” , OLYMPIADS IN INFORMATICS Tasks and Training Volume 2 2008 Selected papers of the International Conference joint with the XX International Olympiad in Informatics Cairo, Egypt, August 16–23, 2008. [online]. Available: https://www.mii.lt/olympiads_in_informatics/files/volume2.pdf. Accessed on: Sept. 27, 2018. (in English)
V. Melnyk, Y. Horoshko, О. Міца “Overview of the training system for Informatics Olympiads in some countries”, Actual issues of modern informatics, №5, с. 21-23, 2017. (in Ukrainian)
12th Open International Student Programming Olympiad “KPI-OPEN 2017” named after S.O. Lebediev and V.M. Glushkov “KPI-OPEN 2017” [online ]. Available: http://kpi-open.org/. Accessed on: Jul. 17, 2018. (in Ukrainian)
Internet portal of organizational and methodological support of distance Olympiads on programming for gifted youth of educational institutions of Ukraine e-olimp [online]. Available: https://www.e-olymp.com/. Accessed on: Jul. 17, 2018. (in Ukrainian)
Authors who publish in this journal agree to the following terms:
- Authors hold copyright immediately after publication of their works and retain publishing rights without any restrictions.
- The copyright commencement date complies the publication date of the issue, where the article is included in.
Content Licensing
- Authors grant the journal a right of the first publication of the work under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License (CC BY-NC-SA 4.0) that allows others freely to read, download, copy and print submissions, search content and link to published articles, disseminate their full text and use them for any legitimate non-commercial purposes (i.e. educational or scientific) with the mandatory reference to the article’s authors and initial publication in this journal.
- Original published articles cannot be used by users (exept authors) for commercial purposes or distributed by third-party intermediary organizations for a fee.
Deposit Policy
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) during the editorial process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (see this journal’s registered deposit policy at Sherpa/Romeo directory).
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Post-print (post-refereeing manuscript version) and publisher's PDF-version self-archiving is allowed.
- Archiving the pre-print (pre-refereeing manuscript version) not allowed.