Эффективные алгоритмы и сложность вычислений: теория и анализ

Книга «Эффективные алгоритмы и сложность вычислений» представляет собой фундаментальное учебное пособие по теории алгоритмов и вычислительной сложности. Авторы, Н. Н. Кузюрин и С. А. Фомин, систематически излагают ключевые концепции, необходимые для анализа и проектирования эффективных алгоритмов.

В первой части рассматриваются базовые понятия алгоритмов, формальные модели вычислений (RAM-машины) и различные меры сложности: в худшем случае, в среднем. Подробно обсуждается важность полиномиальных алгоритмов и их связь с практической эффективностью. Разбираются классические задачи, такие как вычисление НОД, сортировка слиянием и быстрая сортировка, задачи на графах (коммивояжер, кратчайшие пути).

Значительная часть книги посвящена методам разработки приближенных алгоритмов с гарантированной точностью. Рассматриваются жадные алгоритмы для задач покрытия множеств и вершинного покрытия, алгоритмы для задачи о рюкзаке, включая алгоритм Кристофидеса для метрической задачи коммивояжера. Вводится понятие полностью полиномиальной приближенной схемы (FPTAS).

Отдельные главы охватывают вероятностный анализ детерминированных алгоритмов и сами вероятностные алгоритмы. Изучаются методы вероятностного округления, проверки тождеств, а также применение вероятностных методов в параллельных вычислениях. Завершает книгу раздел по основам теории сложности вычислений, включая классы сложности P, NP, понятия NP-полноты и сводимости, а также введение в вероятностные классы RP, coRP и BPP.