ГлавнаяАрхивВычислительная сложность построения композиционных моделей липшиц-ограниченных отображений

Вычислительная сложность построения композиционных моделей липшиц-ограниченных отображений | Прикладная дискретная математика. 2014. № 3 (25).

Работа посвящена вопросам численного построения композиционных моделей липшиц-ограниченных сюрьективных функций одного аргумента. Композиционные модели являются частным случаем функциональной аппроксимации, получаемым путём композиции функций из заданного множества. Доказывается NP-трудность задачи построения оптимальной композиционной модели при заданном множестве функций, используемых для построения модели, и определённой приближаемой функции. Рассматриваются различные алгоритмы нахождения приближённых композиционных моделей, часть из которых имеет полиномиальную сложность; оцениваются возможности применения данных подходов.
  • Title Вычислительная сложность построения композиционных моделей липшиц-ограниченных отображений
  • Headline Вычислительная сложность построения композиционных моделей липшиц-ограниченных отображений
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3 (25)
  • Date:
  • DOI
Ключевые слова
композиционные модели, композиция функций, NP-полнота, липшиц-ограниченность, вычислительная сложность, function composition, composition models, NP-completeness, Lipschitz-bounded, computational complexity
Авторы
Ссылки
Alenberg L. The schema theorem and Price's theorem // Foundations of Genetic Algorithms 3. San Francisco: Morgan Kaufmann, 1995. P. 23-49.
Zezula P., Amato G., Dohnal V., and Batko M. Similarity Search: The Metric Space Approach. N. Y.: Springer Verlag, 2006. 220 p.
Растригин Л. А., Рипа К. К, Тарасенко Г. С. Адаптация случайного поиска. Рига: Зи-натне, 1978. 243 с.
Chavez E., Navarro G., Baeza-Yates R., and Marroquin J. L. Search in metric spaces // ACM Computing Surveys. 2001. V.33. No. 3. P. 273-321.
Калинников И. С. Алгоритм построения декомпозиции непрерывной функции одного аргумента по заданному множеству функций // Инновации в науке, образовании и бизнесе: Х Междунар. научн. конф. Калининград: КГТУ, 2012. Ч.2. С. 160-163.
Alonso C., Gutierrez J., and Recio T. A rational function decomposition algorithm by near-separated polynomials // J. Symbolic Comput. 1995. V. 19. P. 527-544.
Even S. and Goldreich O. The minimum-length generator sequence problem is NP-hard // J. Algorithms. 1981. No. 2. P. 311-313.
Пападимитриу X. X., Стайглиц . Комбинаторная оптимизация: Алгоритмы и сложность. М.: Мир, 1987. 520 с.
Karp R.M. Reducibility among combinatorial problems // GJ-474 report. 1971. P. 87-103. http://www.seas.upenn.edu/~bhusnur4/cit596_spring2014/karp-1971.pdf
Seong J. K., Elber G., and Kim M. S. Polynomial decomposition and its applications. http: //cana.kaist.ac.kr/seong/decomposition.pdf. 2003.
Luke S. Essentials of metaheuristics. http://cs.gmu.edu/~sean/book/metaheuristics. 2009.
Лабутин С. А., Пугин М. В. Анализ сигналов и зависимостей: учеб. пособие. Н.Новгород: Нижегород. гос. тех. ун-т, 2001. 158с.
Koza J. R. Genetic Programming: on the Programming of Computers by Means of Natural Selection. London: A Bradford Book, 1998. 815 p.
Вычислительная сложность построения композиционных моделей липшиц-ограниченных отображений | Прикладная дискретная математика. 2014. № 3 (25).
Вычислительная сложность построения композиционных моделей липшиц-ограниченных отображений | Прикладная дискретная математика. 2014. № 3 (25).