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