Метод сокращения перебора в алгоритмах построения минимальных аддитивных цепочекетод сокращения перебора в алгоритмах построения минимальных аддитивных цепочек

  • Александр Михайлович Коточигов Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), ул. Профессора Попова, д. 5, корп. 3, 197376, Санкт-Петербург, Россия
  • Андрей Сучков
Ключевые слова: аддитивные цепочки , эквивалентные цепочки , пассивный интервал, существенное перемешивание

Аннотация

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

Биографии авторов

Александр Михайлович Коточигов, Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина), ул. Профессора Попова, д. 5, корп. 3, 197376, Санкт-Петербург, Россия

Доктор физико-математических наук, профессор, заведующий кафедрой АМ, amkotochigov@gmail.com

Андрей Сучков

Аспирант

Литература

D. Knuth, Iskusstvo programmirovaniya [The Art of Computer Programming], K. I. Babenko and Yu. M. Bayakovskii, eds., vol. 1, Moscow: Iz-vo Mir, 1974 (in Russian).

N. Pippenger, “On the evaluation of powers and monomials,” SIAM J. Comput., vol. 9, no. 2, pp. 230–250, 1980; doi:10.1137/0209022

N. N. Vassiliev, “Evaluations of sparse polynomials and the synthesis of evaluating programs,” in Proc. Internat. Conf. on Comp. Algebra and Appl. Thtor. Phys., Dubna, 1984, pp. 154–159.

V. V. Kochergin, “Utochnenie otsenok slozhnosti vychisleniya odnochlenov i naborov stepenei v zadachakh Bellmana i Knuta” [Improvement of the estimates of the computational complexity for monomials and sets of powers in Bellman’s and Knuth’s problems], J. Appl. Industr. Math., vol. 9, no. 1, pp. 68–82, 2015 (in Russian); doi: 10.1134/S1990478915010081

A. M. Kotochigov, “Algoritmy fraktal’nogo analiza izobrazhenii” [Fractal Image Analysis Algorithms], Computer tools in education, no. 2, pp. 34–39, 2012 (in Russian).

Опубликован
2020-03-28
Как цитировать
Коточигов, А. М., & Сучков, А. (2020). Метод сокращения перебора в алгоритмах построения минимальных аддитивных цепочекетод сокращения перебора в алгоритмах построения минимальных аддитивных цепочек. Компьютерные инструменты в образовании, (1), 5-18. https://doi.org/10.32603/2071-2340-2020-1-5-18
Выпуск
Раздел
Алгоритмическая математика и математическое моделирование