RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Фундамент. и прикл. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Фундамент. и прикл. матем., 2015, том 20, выпуск 6, страницы 159–188 (Mi fpm1692)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

О задачах Беллмана и Кнута и их обобщениях

В. В. Кочергин

Московский государственный университет им. М. В. Ломоносова, Институт теоретических проблем микромира им. Н. Н. Боголюбова

Аннотация: Исследуются в асимптотической постановке различные обобщения классической задачи о наискорейшем возведении в степень, известной также как задача об аддитивных цепочках. Для двух наиболее известных обобщений — для задачи Ричарда Беллмана о сложности (наименьшем числе операций умножения) вычисления (исходя только из переменных) нормированного одночлена от $m$ переменных и для задачи Дональда Кнута о сложности совместного вычисления системы из $m$ степеней одной переменной — при слабых ограничениях предъявлено асимптотически точное решение. Кроме того, дан краткий обзор результатов по сложности вычислений, касающихся следующих трёх задач: вычисление системы из $p$ нормированных одночленов от $q$ переменных; аддитивные вычисления систем из $p$ линейных форм от $q$ переменных; вычисление системы из $p$ элементов свободной абелевой группы с $q$ порождающими.

Ключевые слова: аддитивные цепочки, векторные аддитивные цепочки, цепочки из сложений и вычитаний, цепочки слов, вычисление одночленов, вычисление степеней, задача Беллмана, задача Кнута.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 14-01-00598_a
Работа выполнена при финансовой поддержке РФФИ (проект 14-01-00598).


Полный текст: PDF файл (267 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Journal of Mathematical Sciences (New York), 2018, 233:1, 103–124

Тип публикации: Статья
УДК: 519.7

Образец цитирования: В. В. Кочергин, “О задачах Беллмана и Кнута и их обобщениях”, Фундамент. и прикл. матем., 20:6 (2015), 159–188; J. Math. Sci., 233:1 (2018), 103–124

Цитирование в формате AMSBIB
\RBibitem{Koc15}
\by В.~В.~Кочергин
\paper О задачах Беллмана и Кнута и их обобщениях
\jour Фундамент. и прикл. матем.
\yr 2015
\vol 20
\issue 6
\pages 159--188
\mathnet{http://mi.mathnet.ru/fpm1692}
\transl
\jour J. Math. Sci.
\yr 2018
\vol 233
\issue 1
\pages 103--124
\crossref{https://doi.org/10.1007/s10958-018-3928-4}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/fpm1692
  • http://mi.mathnet.ru/rus/fpm/v20/i6/p159

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. В. В. Кочергин, “Простое доказательство верхней оценки сложности вычисления трех одночленов трeх переменных”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2019, № 2, 3–8  mathnet  mathscinet  zmath; V. V. Kochergin, “A simple proof for the upper bound of the computational complexity of three monomials in three variables”, Moscow University Mathematics Bulletin, 74:2 (2019), 43–48  crossref  isi
  • Фундаментальная и прикладная математика
    Просмотров:
    Эта страница:111
    Полный текст:47
    Литература:24
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020