RUS  ENG
Полная версия
ЖУРНАЛЫ // Журнал Сибирского федерального университета. Серия «Математика и физика» // Архив

Журн. СФУ. Сер. Матем. и физ., 2011, том 4, выпуск 2, страницы 195–207 (Mi jsfu178)

Эта публикация цитируется в 1 статье

Analysis parameterized algorithms on the bases of elasticity to functions complexity

[Анализ параметризированных алгоритмов на основе эластичности функций сложности]

Valentina V. Bykova

Institute of Mathematics, Siberian Federal University, Krasnoyarsk, Russia

Аннотация: Дан краткий обзор результатов и проблем параметризированной алгоритмики – нового направления теории сложности вычислений. Предложен новый показатель вычислительной сложности параметризированного алгоритма, с помощью которого можно измерять темп роста функции сложности многих переменных. Этим показателем является частная эластичность функции сложности. Предложена двумерная классификация параметризированных алгоритмов для мультипликативной формы представления функций сложности. Математически обоснован метод анализа уровня влияния параметра на время работы параметризированного алгоритма.

Ключевые слова: сложность вычислений, параметризированные алгоритмы, анализ алгоритмов, эластичность алгоритмов.

УДК: 510.52

Получена: 30.10.2010
Исправленный вариант: 10.11.2010
Принята: 20.12.2010

Язык публикации: английский



© МИАН, 2024