ON THE ADVANTAGE OF STUDYING THE BASICS OF DYNAMIC PROGRAMMING IN HIGH SCHOOL AND UNIVERSITY

Abstract

The article substantiates the feasibility of studying the basics of dynamic programming in computer science lessons in high school and in programming classes in junior years of universities in the topics “Nested Loops”, “Arrays” and “Recursions”. A model problem is presented and the sequence of its solution is described to demonstrate the basics of the dynamic programming method: allocation of system states, where the last state corresponds to the solution of the entire problem; establishment of a criterion for optimality of states; sequential determination of the optimal result for each state with saving this result for further calculation of optimal results of subsequent states; formation of a path to achieve an optimal result for the entire problem through the reverse determination of the corresponding intermediate states. It is shown that the relationship between the states of the system does not necessarily have to be linear, the main thing is that the optimal result of the next state is determined through the saved optimal results of the previous states.Recursive formulas are determined for sequential calculation of optimal results of each state of the problem.The program fragments for implementing the developed algorithms of the main stages of solving the problem in the C# programming language are presented. The complexity of the given algorithms for implementing individual stages of solving the problem was assessed using algorithm theory methods. It was established that the asymptotic computational complexity of the forward and backward steps of the dynamic programming method based on recurrent formulas is at least an order of magnitude lower than the corresponding recursive calls of subroutines. The correctness of the theoretical calculations and the correctness of the given program fragments were confirmed experimentally using a remote independent computing environment on the website https://basecamp.eolymp.com. It is emphasized that studying the basics of dynamic programming will form regression testing skills and writing not only correct but also effective programs in students.