Новые результаты
в задачах Р. Беллмана и Д. Кнута
Получена: 09.11.2026 Принята: 09.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 27–45
Аннотация
В работе рассматриваются задача Беллмана о сложности (минимально возможном числе операций умножения, достаточном для вычисления) одночлена от \(m\) переменных и задача Кнута о сложности вычисления набора из \(m\) степеней одной переменной. Для любого фиксированного действительного числа \(a \ge 2\) и любой положительной функции \(\varphi (m)\), удовлетворяющей условию \(\lvert \log \varphi (m)\rvert =o(\log m)\), установлены асимптотически точные оценки соответствующих функций Шеннона, характеризующих максимально возможную сложность при ограничении показателей величиной \(A=\varphi (m)m^a\). Эти функции при \(m\to \infty\) асимптотически равны \(am\) и \((a-1)m\) соответственно.
Ключевые слова: аддитивные цепочки, векторные аддитивные цепочки, задача Беллмана, задача Кнута, схемная сложность.
BibTeX
@article{IS-Kochergin2026,
author = {Кочергин, Вадим Васильевич},
title = {{Новые результаты \\ в задачах Р. Беллмана и Д. Кнута}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {27--45},
}
AMSBIB
\RBibitem{IS-Kochergin2026}
\by В.\,В.~Кочергин
\paper Новые результаты \\ в задачах Р. Беллмана и Д. Кнута
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 27--45
EN