\documentclass[spec, och, labwork]{SCWorks}
\usepackage{preamble}

\begin{document}
\include{titlepage.tex}

\section*{Описание работы алгоритма}

Пусть даны множество $S$ и разбиение $\pi$ множества $S$ на непересекающиеся
блоки $\{ B_1, B_2, \ldots, B_p \}$. Кроме того, дана функция $f: S \to S$.
Задача состоит в том, чтобы найти грубейшее (с наименьшим количеством блоков)
разбиение $\pi' = \{ E_1, E_2, \ldots, E_q \}$ множества $S$, что
\begin{enumerate}
    \item
        $\pi'$ "--- подразбиение разбиения $\pi$ (т. е. каждое множество
        является подмножеством некоторого блока $B_j$);
    \item
        если $a$ и $b$ принадлежат $E_i$, то $f(a)$ и $f(b)$ принадлежат $E_j$
        для некоторого $j$.
\end{enumerate}

Очевидное решение состоит в повторном утончении блоков исходного разбиения
следующим способом. Пусть $B_i$ "--- какой-нибудь блок. Рассмотрим $f(a)$ для
каждого $a$ из $B_i$. Разобьём $B_i$ так, чтобы два элемента $a$ и $b$ попадали
в один блок тогда и только тогда, когда $f(a)$ и $f(b)$ оба принадлежат
некоторому блоку $B_j$. Процесс повторяется до тех пор, пока уже нельзя будет
проводить дальнейшие утончения. 

Этот метод даёт алгоритм сложности $O(n^2)$, поскольку каждое утончение занимает
время $O(n)$, а всего может быть $O(n)$ утончений.

\subsection*{Реализация на языке Python}

\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../../partition.py}

\end{document}