|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Уточнение оценок сложности вычисления одночленов и наборов степеней в задачах Беллмана и Кнутастатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Автор: Кочергин В.В.
- Журнал: Дискретный анализ и исследование операций
- Том: 21
- Номер: 6
- Год издания: 2014
- Издательство: Изд-во Ин-та математики
- Местоположение издательства: Новосибирск
- Первая страница: 51
- Последняя страница: 72
- Аннотация: Изучаются два обобщения классической задачи о наискорейшем возведении в степень - задача Ричарда Беллмана о сложности (наименьшем числе операций умножения) вычисления исходя только из переменных нормированного одночлена от m переменных, и задача Дональда Кнута о сложности совместного вычисления системы из m степеней одной переменной. В статье дается обзор некоторых результатов, связанных с этими двумя задачами, а также уточняются асимптотические оценки сложности в задачах Беллмана и Кнута в случае, когда поведение величины m сравнимо со сложностью (имеют одинаковый порядок роста). Для почти всех наборов степеней установленые верхняя и нижние оценки сложности для задач Р.~Беллмана и Д.~Кнута, помимо того, что при широком диапазоне соотношения параметров (число переменных или вычисляемых степеней, значение максимального показателя степени и произведение всех показателей степеней) дают асимптотику роста сложности, еще и гарантируют при любом соотношении параметров превышение верхней оценки над нижней оценкой асимптотически не более чем в 5/3 раз.
- Добавил в систему: Кочергин Вадим Васильевич