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

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

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



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






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


Дискрет. матем., 2005, том 17, выпуск 4, страницы 116–142 (Mi dm135)  

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

О сложности вычисления пары одночленов от двух переменных

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


Аннотация: Изучается обобщение задачи об эффективном вычислении степени $x^n$ по заданным $x$ и $n$ (или эквивалентной ей задачи о минимальной аддитивной цепочке для числа $n$), где $n\in\mathbf N$. Сложность вычисления системы одночленов $\{x^ay^b,x^cy^d\}$, то есть минимальное число операций умножения, достаточное для вычисления (допускается многократное использование промежуточных результатов) по переменным $x$ и $y$, а также заданным показателям $a$, $b$, $c$ и $d$ системы одночленов $\{x^ay^b,x^cy^d\}$, обозначим через $l(x^ay^b,x^cy^d)$. В работе доказано, что при выполнении условия $\max\{a,b,c,d\}\to\infty$, справедливо соотношение
$$ l(x^{a}y^{b},x^{c}y^{d})\sim\log_2(|ad-bc|+a+b+c+d). $$

Работа выполнена при поддержке Российского фонда фундаментальный исследований, проект 05-01-00994, программой Президента Российской Федерации поддержки ведущих научных школ, проект НШ–1807.2003.1, и программой Университеты России, проект УР.04.02.528.

DOI: https://doi.org/10.4213/dm135

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

Англоязычная версия:
Discrete Mathematics and Applications, 2005, 15:6, 547–572

Реферативные базы данных:

УДК: 519.7
Статья поступила: 28.04.2005

Образец цитирования: В. В. Кочергин, “О сложности вычисления пары одночленов от двух переменных”, Дискрет. матем., 17:4 (2005), 116–142; Discrete Math. Appl., 15:6 (2005), 547–572

Цитирование в формате AMSBIB
\RBibitem{Koc05}
\by В.~В.~Кочергин
\paper О сложности вычисления пары одночленов от двух переменных
\jour Дискрет. матем.
\yr 2005
\vol 17
\issue 4
\pages 116--142
\mathnet{http://mi.mathnet.ru/dm135}
\crossref{https://doi.org/10.4213/dm135}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2240547}
\zmath{https://zbmath.org/?q=an:05062019}
\elib{http://elibrary.ru/item.asp?id=9154208}
\transl
\jour Discrete Math. Appl.
\yr 2005
\vol 15
\issue 6
\pages 547--572
\crossref{https://doi.org/10.1515/156939205774939353}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm135
  • https://doi.org/10.4213/dm135
  • http://mi.mathnet.ru/rus/dm/v17/i4/p116

    ОТПРАВИТЬ: 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. В. В. Кочергин, “Об асимптотике сложности аддитивных вычислений систем целочисленных линейных форм”, Дискретн. анализ и исслед. опер., сер. 1, сер. 1, 13:2 (2006), 38–58  mathnet  mathscinet  zmath; V. V. Kochergin, “Asymptotics of the complexity of systems of integer linear forms for additive computations”, J. Appl. Industr. Math., 1:3 (2007), 328–342  crossref
    2. В. В. Кочергин, “О сложности совместного вычисления трёх элементов свободной абелевой группы с двумя образующими”, Дискретн. анализ и исслед. опер., 15:2 (2008), 23–64  mathnet  mathscinet  zmath
    3. Кочергин В.В., “Об одном соотношении двух мер сложности вычисления систем одночленов”, Вестн. Моск. ун-та. Сер. 1: Матем. Мех., 2009, № 4, 8–13  mathscinet  zmath; Kochergin V.V., “Relation between two measures of the computation complexity for systems of monomials”, Moscow Univ. Math. Bull., 64:4 (2009), 1440–149  crossref  mathscinet  scopus
    4. В. В. Кочергин, “Уточнение оценок сложности вычисления одночленов и наборов степеней в задачах Беллмана и Кнута”, Дискретн. анализ и исслед. опер., 21:6 (2014), 51–72  mathnet  mathscinet; V. V. Kochergin, “Improvement of complexity bounds of monomials and sets of powers computations in Bellman's and Knuth's problems”, J. Appl. Industr. Math., 9:1 (2015), 68–82  crossref
    5. Е. Н. Трусевич, “О сложности вычисления некоторых систем одночленов схемами композиции”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2014, № 5, 18–22  mathnet  mathscinet; E. N. Trusevich, “Complexity of certain systems of monomials in calculation by composition circuits”, Moscow University Mathematics Bulletin, 69:5 (2014), 193–197  crossref
    6. В. В. Кочергин, “О задачах Беллмана и Кнута и их обобщениях”, Фундамент. и прикл. матем., 20:6 (2015), 159–188  mathnet; V. V. Kochergin, “On Bellman's and Knuth's problems and their generalizations”, J. Math. Sci., 233:1 (2018), 103–124  crossref
  • Дискретная математика
    Просмотров:
    Эта страница:324
    Полный текст:111
    Литература:48
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020