1 files changed, 36 insertions, 0 deletions
diff --git a/reports/lab3/lab3.tex b/reports/lab3/lab3.tex
new file mode 100644
index 0000000..4f26e2b
--- /dev/null
+++ b/reports/lab3/lab3.tex
@@ -0,0 +1,36 @@
+\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}