Задачи Р. Беллмана и Д. Кнута и их обобщения, Вадим Васильевич Кочергин

В монографии рассматриваются обобщения классической задачи о наискорейшем возведении в степень, т. е. задачи о нахождении сложности возведения в степень - минимального числа умножений, достаточного для вычисления по переменной заданной степени этой переменной. Эта задача также хорошо известна как задача об аддитивных цепочках. Помимо поставленной в 1963 г. Р. Беллманом задачи о сложности вычисления одночлена от многих переменных и поставленной в 1969 г. Д. Кнутом задачи о сложности вычисления системы степеней одной переменной в книге в асимптотической постановке исследуются и дальнейшие обобщения исходной задачи. Основное внимание уделено трем задачам - задаче о сложности вычисления систем одночленов, задаче о сложности вычисления систем целочисленных линейных форм (эта задача, как правило, рассматривается в аддитивной постановке) и задаче о сложности вычисления систем элементов свободной абелевой группы. Изучаются общие закономерности и различия между этими тремя задачами с точки...