Теоретические основы анализа параметризированных алгоритмов

Описание

Тип публикации: монография

Год издания: 2011

Ключевые слова: анализ параметризированных алгоритмов, параметризированные алгоритмы, NP-полные задачи, эластичность функций сложности, анализ рекурсовных алгоритмов, рекукрсивные алгоритмы, алгоритмы

Аннотация: Книга посвящена – современному направлению теории сложности вычислений. Параметризированные алгоритмы направлены на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по сравнению с длиной входа алгоритма. Роль этого параметра – учесть информацию о структуре исходных данных алгоритма и выделить основной источнПоказать полностьюик неполиномиальной сложности NP-трудной задачи. В работе представлена классификация параметризированных алгоритмов по вычислительной сложности на основе эластичностей функций сложности, описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей исследовано влияние параметра на время выполнения параметризированного алгоритма. Развиты методы анализа рекурсивных алгоритмов.

Ссылки на полный текст

Издание

Место издания: Красноярск

Издатель: Федеральное государственное автономное образовательное учреждение высшего образования Сибирский федеральный университет

Авторы

Вхождение в базы данных