Журналы
Email: Пароль: Войти Регистрация
Оптимизация алгоритмов вычислений значений многочленов, точнее мономов, эквивалентна задаче построения для заданного числа минимальной аддитивной цепочки. Для поиска таких цепочек не известно никаких алгоритмов, кроме перебора. Рост сложности перебора очень велик. Среди цепочек одинаковой длины очень много эквивалентных, то есть заканчивающихся одинаковым числом. В статье приведен достаточный признак эквивалентности цепочек и показано, как использование признака позволяет сократить процедуру формирования всех аддитивных цепочек фиксированной длины. С. 5-18.

Optimization of algorithms for computing the values of polynomials, more precisely, of monomials, is equivalent to the problem of constructing for a given number a minimal additive chain. To search for such chains, no algorithms are known except brute force. The increase in the complexity of the brute force algorithm is very large. Among chains of the same length there are a lot of equivalent ones, that is, those ending with the same number. The article provides a sufficient criterion for the equivalence of chains and shows how the use of the criterion reduces the procedure for the formation of all additive chains of a fixed length.

Ключевые слова: аддитивные цепочки, эквивалентные цепочки, пассивный интервал, существенное перемешивание.
Keywords: additive chain, equivalent chain, passive interval, essential randomisation.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть