Статья в сборнике "Математические вопросы кибернетики" №20, Москва, 2022
Авторы:Кочергин В.В.
Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках
Аннотация:
Для различных обобщений задачи об эффективном возведении в степень, в аддитивной постановке известной как задача об аддитивных цепочках, предпринята попытка с единых позиций оценить и сравнить результаты, а также используемые при их получении методы. В качестве таких обобщений рассматриваются задачи о сложности (минимальном числе необходимых операций) вычисления одночлена от многих переменных, набора степеней, элементов конечных абелевых групп, элементов свободных полугрупп, систем одночленов, систем целочисленных линейных форм, систем элементов свободных абелевых групп и некоторое другие задачи. По этим направлением дан обзор классических результатов, а также результатов автора и его учеников.
Ключевые слова:
аддитивная цепочка, векторная аддитивная цепочка, схемная сложность, сложность вычисления, функция Шеннона, задача Беллмана, задача Кнута, задача Лупанова, задача Пиппенджера, целочисленная линейная форма, схема конкатенации, вентильная схема
Язык публикации: русский, страниц:138 (с. 119-256)
