ЗАСТОСУВАННЯ МЕМОІЗАЦІЇ В ЗАДАЧАХ МІНІМІЗАЦІЇ КІЛЬКОСТІ ЗНАКІВ АРИФМЕТИЧНИХ ОПЕРАЦІЙ

Downloads

Downloads per month over past year

Шпортько, О. В. and Малаш, К. М. and Shportko, A. V. and Malash, K. M. (2020) ЗАСТОСУВАННЯ МЕМОІЗАЦІЇ В ЗАДАЧАХ МІНІМІЗАЦІЇ КІЛЬКОСТІ ЗНАКІВ АРИФМЕТИЧНИХ ОПЕРАЦІЙ. Вісник Національного університету водного господарства та природокористування (2(90)). pp. 127-143.

[img] Text
Vt9013.zax.pdf

Download(327kB)

Abstract

В статті порівнюються способи розв’язання задачі мінімізації кількості додавань із застосуванням мемоізації на основі методів рекурсії та динамічного програмування. Наведено рекурентні формули прямого і зворотного ходу методу динамічного програмування для розв’язування цієї задачі. Визначено і обґрунтовано обмеження на проміжні результати її розв’язків. Наведено фрагменти програм мовою C# для реалізації запропонованих способів мінімізації кількості додавань. Показано, що використання мемоізації для відсікання неефективних варіантів перебору дає змогу прискорити виконання відповідних алгоритмів в десятки разів.

Title in English

MEMOIZATION USING IN THE PROBLEMS OF MINIMIZATION OF SIGNS OF THE ARITHMETIC OPERATIONS NUMBER

English abstract

The article compares two ways of solving the arithmetic operations of placement of signs based on the use of memoization: method is based on recursion and dynamic programming. Limitations of the intermediate results of the problem solution are identified and justified. It is shown that the use of memoization in order to cut off ineffective search options makes it possible to accelerate the corresponding of algorithms execution for tens times. Analyzing the results of the study, the following conclusions were obtained: 1. Memoization should be used not only to speed up the execution of recursive calls, but also to implement the dynamic programming method and, in general, to reduce the number of nested cycles, which will significantly accelerate the execution of programs. At the same time, only the results of the calculations should be stored, which can be used in the future repeatedly. 2. In order to accelerate the solution of sequential decisionmaking problems, it is reasonable to use a dynamic programming method in the algorithmization process rather than recursive calls of subroutines. Although the implementations of this method require a large amount of memory to backfire, they do not store in the stack the values of all local variables for each recursive call every time. 3. To save RAM, the values of the state variables and the target function should be stored only for the current and previous steps of the dynamic programming method, and for all steps and states of the system, only a minimum of data should be stored to provide a solution during the reverse process of this method. 4. In the process of implementing the dynamic programming method, it is reasonable to consider not only the target function, but also the variable of each state. It takes a lot of machine time using the memorization method of solving the problem and not only saves memory while not storing the invalid values, but also speeds up calculations for the future states significantly.

Item Type: Article
Uncontrolled Keywords: мемоізація; задачі динамічного програмування; розстановка знаків арифметичних операцій; memoization; dynamical programming problems; arithmetic operations sign placement
УДК: 004.043
Бібліографічний опис: Шпортько О. В. Застосування мемоізації в задачах мінімізації кількості знаків арифметичних операцій / О. В. Шпортько, К. М. Малаш // Вісник НУВГП. Технічні науки : зб. наук. праць. – Рівне : НУВГП, 2020. – Вип. 2(90). – С. 127-143.
Subjects: Видання університету > Вісник НУВГП > серія "Технічні науки" > 2020 > Вісник 2
Видання університету > Вісник НУВГП > серія "Технічні науки" > 2020
Depositing User: С. В. Бойчук
Date Deposited: 10 Feb 2021 14:22
Last Modified: 10 Feb 2021 14:22
URI: http://ep3.nuwm.edu.ua/id/eprint/19764

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year