Параметризованные алгоритмы -- молодая область Computer Science с множеством интересных результатов и открытых задач. Основным объектом её исследования являются оценки на время работы алгоритмов относительно не только размера входа, но также и некоторого дополнительного параметра. Например, асимптотически самый быстрый известный алгоритм для NP-трудной задачи о вершинном покрытии имеет время работы $O^*(c^n)$, где $n$ -- количество вершин графа, а $1 < c < 2$ -- константа. Поскольку время работы экспоненциально, с ростом $n$ такой алгоритм довольно быстро становится непрактичным. В то же время довольно просто придумать алгоритм, который за время $O^*(2^k)$ проверят, есть ли в графе вершинное покрытие размера не более $k$. Такой алгоритм называется fixed-parameter tractable (FPT). Как видно, при небольшом $k$ данный алгоритм вполне может быть применён на практике. Формально, алгоритм называется fixed-parameter tractable, если его время растёт как $f(k)n^{O(1)}$. Другими словами, при фиксированном значении параметра $k$ время работы алгоритма растёт полиномиально. В примере выше в качестве параметра выступает размер выхода, но есть и много других естественных параметризаций. Интерес представляют параметризации, при которых сложные входы задач по-прежнему имеют небольшое значение параметра.

В курсе будет дан обзор известных результатов и открытых задач данной области. Заинтересованным студентам будут выданы статьи/главы книг для выступления на семинаре.