Алгоритмы для NP-трудных задач: теория сложности и методы

Четвертая часть серии «Совершенный алгоритм» посвящена одной из самых фундаментальных тем в теоретической информатике — NP-трудным задачам. Книга адресована программистам, уже имеющим опыт в алгоритмах и желающим перейти на новый уровень понимания вычислительной сложности.

Автор, профессор Стэнфордского университета Тим Рафгарден, подробно объясняет, что такое NP-трудность, как распознать такие задачи на практике и какие стратегии можно применять для их решения, когда точный полиномиальный алгоритм неизвестен или невозможен. Рассматриваются классические NP-трудные задачи, такие как задача коммивояжера.

Книга учит не бояться NP-трудности, а грамотно подходить к ней: избегать решения «с нуля», искать эффективные аппроксимационные алгоритмы, эвристики и другие практические методы. Материал основан на популярных онлайн-курсах автора и изложен с акцентом на понимание общей картины и математических основ.