Эта книга посвящена анализу параметризированных алгоритмов - современному направлению в теории сложности вычислений. Параметризированные алгоритмы нацелены на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по сравнению с размером входных данных алгоритма. Роль этого параметра - учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-трудной задачи.
В книге представлена классификация параметризированных алгоритмов по вычислительной сложности на основе эластичностей функций сложности, описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей исследовано влияние параметра на время выполнения параметризированного алгоритма. Развиты методы анализа рекурсивных алгоритмов.
Книга предназначена для специалистов в области разработки, анализа и исследования алгоритмов, а также для студентов, аспирантов, научных работников и преподавателей высших учебных заведений.
В книге исследуется анализ параметризованных алгоритмов — современная теория вычислительной сложности. Исследуются алгоритмы на нахождение точных решений трудных задач и их роль в изменении сложности алгоритма под влиянием входных параметров. Представлена классификация алгоритмов по универсальности влияния параметра на сложность алгоритма. Разработка и исследование рекурсивных алгоритмических методов. Книга написана для специалистов в проектировании и исследовании сложных алгоритмов так же как для постетиции и учеников высшего уровня обучения.
Электронная Книга «Теоретические основы анализа параметризированных алгоритмов» написана автором Валентина Быкова в 2011 году.
Минимальный возраст читателя: 0
Язык: Русский
ISBN: 978-5-7638-2488-9
Описание книги от Валентина Быкова
Книга посвящена анализу параметризированных алгоритмов – современному направлению теории сложности вычислений. Параметризированные алгоритмы направлены на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по сравнению с длиной входа алгоритма. Роль этого параметра – учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-трудной задачи. В работе представлена классификация параметризированных алгоритмов по вычислительной сложности на основе эластичностей функций сложности, описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей исследовано влияние параметра на время выполнения параметризированного алгоритма. Развиты методы анализа рекурсивных алгоритмов. Для специалистов в области разработки, анализа и исследования алгоритмов, а также для студентов, аспирантов, научных работников, преподавателей высших учебных заведений.
