Том 14, серия 1, номер 4, 2007 г., Стр. 57-75
УДК 519.7
И. С. Сергеев
О сложности градиента рациональной функции
Аннотация:
Из метода Баура–Штрассена следует, что$L(\nabla f)\leqslant4L(f)$ , где$L(f)$ – сложность реализации рациональной функции$f$ схемами над арифметическим базисом, а$\nabla f$ – градиент функции$f$ . Показано, что$L(\nabla f)\leqslant3L(f)+n$ , где$n$ – число переменных функции$f$ . Кроме того, получены оценки глубины схемы для градиента.
Библ. 17.
Сергеев И. С. 1
1. МГУ, мех.-мат. факультет, Ленинские горы, 119991 Москва, Россия
Статья поступила 26 марта 2007 г.
Исправленный вариант — 11 мая 2007 г.
