1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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}
|
