From bc6fa2f8d7967acd859c0f660cad81199e53b0fb Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 19 May 2022 14:12:12 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B8?=
 =?UTF-8?q?=D0=B5=20=D0=BE=D1=82=D1=87=D1=91=D1=82=D0=BE=D0=B2=20=D0=BF?=
 =?UTF-8?q?=D0=BE=20=D0=BF=D0=B5=D1=80=D0=B2=D1=8B=D0=BC=20=D1=82=D1=80?=
 =?UTF-8?q?=D1=91=D0=BC=20=D0=BB=D0=B0=D0=B1=D0=B0=D0=BC?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 reports/lab3/lab3.tex | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
 create mode 100644 reports/lab3/lab3.tex

(limited to 'reports/lab3/lab3.tex')

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}
-- 
cgit v1.2.3