Книга посвящена анализу параметризированных алгоритмов - современному направлению теории сложности вычислений. Параметризированные алгоритмы направлены на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по сравнению с длиной входа алгоритма. Роль этого параметра - учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-трудной задачи. В работе представлена классификация параметризированных алгоритмов по вычислительной сложности на основе эластичностей функций сложности, описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей исследовано влияние параметра на время выполнения параметризированного алгоритма. Развиты методы анализа рекурсивных алгоритмов.Для специалистов в области разработки, анализа и исследования алгоритмов, а также для студентов, аспирантов, научных работников, преподавателей высших учебных заведений.
Kniga posvjaschena analizu parametrizirovannykh algoritmov - sovremennomu napravleniju teorii slozhnosti vychislenij. Parametrizirovannye algoritmy napravleny na poisk tochnykh reshenij NP-polnykh zadach, kogda parametr reshaemoj zadachi mal po sravneniju s dlinoj vkhoda algoritma. Rol etogo parametra - uchest informatsiju o strukture iskhodnykh dannykh algoritma i vydelit osnovnoj istochnik nepolinomialnoj slozhnosti NP-trudnoj zadachi. V rabote predstavlena klassifikatsija parametrizirovannykh algoritmov po vychislitelnoj slozhnosti na osnove elastichnostej funktsij slozhnosti, opisyvajuschikh potrebnosti algoritmov v neobkhodimykh resursakh. S pomoschju elastichnostej issledovano vlijanie parametra na vremja vypolnenija parametrizirovannogo algoritma. Razvity metody analiza rekursivnykh algoritmov.Dlja spetsialistov v oblasti razrabotki, analiza i issledovanija algoritmov, a takzhe dlja studentov, aspirantov, nauchnykh rabotnikov, prepodavatelej vysshikh uchebnykh zavedenij.
