Аннотация:
Получены точные по порядку квадратичные и чуть более высокие оценки сложности вычисления некоторых линейных преобразований схемами в базисе $\{x+y \}\cup \{ax: \vert a \vert \leq C \},$ состоящем из операции сложения и скалярных умножений на ограниченные константы, а также верхние оценки $O(n\log n)$ для сложности вычисления в базисе, состоящем из всех линейных функций $\{ax+by: a,b \in {\mathbb R}\}$. Нижние оценки вида $\Theta(n\log n)$ получены для базиса из всех монотонных линейных функций $\{ax+by: a, b > 0\}.$
Ключевые слова:биномиальное преобразование, преобразования Стирлинга, преобразование Лаха, треугольник Паскаля, треугольник Паскаля по простому модулю, матрица Серпинского, матрица Адамара–Сильвестра, треугольники Стирлинга 1-го и 2-го рода, коэффициенты Гаусса, коэффициенты Галуа, сложность вычисления, схемы в базисах из арифметических и линейных операций.
Полный текст:
PDF файл (400 kB)