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