|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
On the complexity of approximate computation of real numbers by schemes and formulae in different rational basesстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 3 мая 2017 г.
- Автор: GASHKOV S.B.
- Журнал: Discrete Mathematics and Applications
- Том: 2
- Номер: 3
- Год издания: 1992
- Издательство: de Gruyter
- Местоположение издательства: Germany
- Первая страница: 259
- Последняя страница: 283
- DOI: 10.1515/dma.1992.2.3.259
- Аннотация: Для ряда рациональных, полиномиальных или линейных базисов получены асимптотики сложности и глубины εε-приближения почти всех чисел схемами в этих базисах и установлен континуальный аналог эффекта Шеннона из теории сложности булевых функций, а для некоторых монотонных линейных базисов – так называемый полуэффект Шеннона в случае реализации чисел формулами (для мультипликативных аналогов линейных базисов подобные утверждения верны для равномерного приближения степенных функций xa∈C[0,1])xa∈C[0,1]). При этом базис {x−y,xy,1/2}{x−y,xy,1/2} и некоторые базисы вида {x−y,a0,…,am}{x−y,a0,…,am} оказываются параллелизуемыми (т.е. для них глубина по порядку равна логарифму сложности реализации формулами), а базис {x−y,x/2,1}{x−y,x/2,1} – нет. Показано, что для почти всех базисов {x−y,ax,1}{x−y,ax,1} сложность εε-приближения схемами почти всех чисел бесконечно мала при ε→0ε→0 по сравнению с таковой для базисов, состоящих из линейных функций, у которых коэффициенты – алгебраические числа, а также что не существует универсальной верхней оценки функций Шеннона для базисов вида {x−y,a,1}{x−y,a,1}.
- Добавил в систему: Гашков Сергей Борисович