|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Точный баланс между объемом памяти и шумом при вычислении эргодических мер
М. Браверманa, К. Рохасb, Дж. Шнайдерa a Princeton University, Princeton, NJ, USA
b Universidad Andrés Bello, Santiago, Chile
Аннотация:
Установлена точная оценка на сложность (по памяти) вычисления эргодической меры динамической системы малой размерности с дискретным временем, испытывающей влияние гауссовского шума. Если величина шума равна $\varepsilon$, а функция, описывающая эволюцию системы, не представляет трудностей с точки зрения вычислительной сложности, то функция плотности эргодической меры может быть приближена с точностью $\delta$ с использованием памяти, полиномиальной от $\log 1/\varepsilon+\log\log 1/\delta$. Также показано, что эта оценка точна с точностью до полиномиального множителя.
В процессе доказательства вышеназванного факта установлен представляющий независимый интерес факт о вычислениях с ограниченной памятью: матрицу размера $n\times n$ возможно возвести в экспоненциально большую степень с использованием памяти, полилогарифмической по $n$.
Библиография: 25 названий.
Ключевые слова:
динамические системы, вычисления с ограниченной памятью.
Поступила в редакцию: 15.12.2016 и 15.05.2017
Образец цитирования:
М. Браверман, К. Рохас, Дж. Шнайдер, “Точный баланс между объемом памяти и шумом при вычислении эргодических мер”, Матем. сб., 208:12 (2017), 42–69; M. Braverman, C. Rojas, J. Schneider, “Tight space-noise tradeoffs in computing the ergodic measure”, Sb. Math., 208:12 (2017), 1758–1783
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm8884https://doi.org/10.4213/sm8884 https://www.mathnet.ru/rus/sm/v208/i12/p42
|
|