- Бизнес-Книги
- Боевики
- Детективы
- Детские книги
- Дом, Семья
- Зарубежная литература
- Искусство
- Классика
- Книги по психологии
- Компьютеры
- Любовные романы
- Наука, Образование
- Периодические издания
- Повести, рассказы
- Поэзия, Драматургия
- Приключения
- Публицистика
- Религия
- Современная проза
- Справочники
- Фантастика
- Фэнтези
- Юмор
Валентина Быкова — Теоретические основы анализа параметризированных алгоритмов
Понравилась книга? Поделись в соцсетях:
Автор: Валентина Быкова
Издатель: Сибирский федеральный университет
Год: 2011
ISBN: 978-5-7638-2488-9
Описание: Книга посвящена анализу параметризированных алгоритмов – современному направлению теории сложности вычислений. Параметризированные алгоритмы направлены на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по сравнению с длиной входа алгоритма. Роль этого параметра – учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-трудной задачи. В работе представлена классификация параметризированных алгоритмов по вычислительной сложности на основе эластичностей функций сложности, описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей исследовано влияние параметра на время выполнения параметризированного алгоритма. Развиты методы анализа рекурсивных алгоритмов. Для специалистов в области разработки, анализа и исследования алгоритмов, а также для студентов, аспирантов, научных работников, преподавателей высших учебных заведений.