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