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

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

\section{Постановка задачи}

Цель работы "--- изучение основных понятий теории полугрупп. Порядок выполнения
работы:
\begin{enumerate}
  \item
    Рассмотреть понятия полугруппы, подполугруппы и порождающего множества.
    Разработать алгоритм построения подполугрупп по таблице Кэли.
  \item
    Разработать алгоритм построения полугруппы бинарных отношений по заданному
    порождающему множеству.
  \item
    Рассмотреть понятия подгруппы, порождающего множества и определяющих
    соотношений. Разработать алгоритм построения полугруппы по порождающему
    множеству и определяющим соотношениям.
\end{enumerate}


\section{Теоретические сведения}

\begin{definition}
  Полугруппа "--- это алгебра $S = (S, \cdot)$ с одной
  ассоциативной бинарной операцией $\cdot$, т.е. выполняется $(x \cdot y) \cdot
  z = x \cdot (y \cdot z)$ для $\forall x, y, z \in S$. Если полугрупповая
  операция называется умножением (или сложением), то полугруппу называют
  мультипликативной (или аддитивной).
\end{definition}
\begin{definition}
  Подмножество $X$ полугруппы $S$ называется подполугруппой, если $X$ устойчиво
  относительно операции умножения, т.е. $\forall x, y \in X$ выполняется
  свойство: $x \cdot y \in X$. В этом случае множество $X$ с ограничением на нем
  операции умножения исходной полугруппы $S$ образует полугруппу.
\end{definition}

В силу общего свойства подалгебр пересечение любого семейства $X_i$ $(i \in I)$
подполугрупп полугруппы $S$ является подполугруппой $S$ и, значит, множество
$Sub(S)$ всех подполугрупп полугруппы $S$ является системой замыканий. множество
$X$. Такая полугруппа обозначается символом $\langle X \rangle$ и называется
подполугруппой $S$, порождённой множеством $X$. При этом множество $X$
называется также \textbf{порождающим множеством} подполугруппы $\langle X
\rangle$. В частности, если $\langle X \rangle = S$, то $X$ называется
порождающим множеством полугруппы $S$ и говорят, что множество $X$ порождает
полугруппу $S$.

Для любой конечной полугруппы $S$ найдется такой конечный алфавит A, что для
некоторого отображения $\phi : A \rightarrow S$ выполняется равенство $\langle
\phi(A) \rangle =S$ и, значит, $S \cong A^+/ \ker \phi$ этом случае множество A
называется множеством порождающих символов полугруппы S (относительно
отображения $\phi : A \rightarrow S$ ). Если при этом для слов $w_1,w_2 \in A$
выполняется равенство $\phi(w_1) = \phi(w_2)$, т.е. $w_1 \equiv w_2(\ker \phi)$ ,
то говорят, что на S выполняется соотношение $w_1 = w_2$ (относительно
отображения $\phi : A \rightarrow S$).

Очевидно, что в общем случае множество таких соотношений $w_1 = w_2$ для всех
пар $(w_1, w_2) \in \ker \phi$ будет бесконечным и не представляется возможности
эффективно описать полугруппу S в виде полугруппы классов конгруэнции $\ker \phi$
. Однако в некоторых случаях можно выбрать такое сравнительно простое
подмножество $\rho \subset \ker \phi$ , которое однозначно определяет конгруэнцию
$\ker \phi$ как наименьшую конгруэнцию полугруппы $A^+$ , содержащую отношение
$\rho$, т.е. $\ker \phi = f_{con}(\rho) = f_{eq}(f_{reg}(\rho))$.

Так как в случае $(w_1, w_2) \in \rho$ по-прежнему выполняется равенство
$\phi(w_1) = \phi(w_2)$, то будем писать $w_1 = w_2$ и называть такие выражения
\textbf{определяющими соотношениями}. Из таких соотношений конгруэнция $\ker \phi$
строится с помощью применения следующих процедур к словам $u,v \in A^+$:

\begin{enumerate}
  \item 
    слово $v$ непосредственно выводится из слова $u$, если $v$ получается из $u$
    заменой некоторого подслова $w_1$ на слово $w_2$, удовлетворяющее
    определяющему соотношению $w_1 = w_2$, т.е. $(u, v) = (xw_1y, xw_2y)$ для
    некоторых $x, y \in A^*$;
  \item
    слово $v$ выводится из слова $u$, если $v$ получается из $u$ с помощью
    конечного числа применения процедуры $1$.
\end{enumerate}

Если все выполняющиеся на $S$ соотношения выводятся из определяющих соотношений
совокупности $\rho$, то конгруэнция $\ker \phi$ полностью определяется отношением
$\rho$ и выражение $<A: {w_1 = w_2 : (w_1, w_2) \in \rho}>$ называется
\textbf{копредставлением полугруппы $S$}.

Обозначим символом $A^+$ множество всех непустых слов над алфавитом и символом
$A^*$ "--- множество слов $A^* = A^+ \cup \{\Lambda\}$. На этих множествах слов
определена операция умножения, которая называется операцией конкатенации слов и
определяется по правилу: любым словам $w_1 = a_1 \dots a_n$ и $w_2 = b_1 \dots
b_m$ операция конкатенации ставит в соответствие слово $w_1 \cdot w_2 = a_1
\dots a_n b_1 \dots b_n$. В результате множество слов $A^+$ с операцией
конкатенации образует полугруппу, которая называется полугруппой слов над
алфавитом $A$, и множество слов $A^*$ с операцией конкатенации образует
полугруппу с единичным элементом $\Lambda$, которая называется моноидом слов над
алфавитом $A$.


\section{Алгоритмы}

%
\subsection{Алгоритм построения построения подполугруппы по заданному порождающему множеству}

\textit{Вход.} Полугруппа $S$ с таблицей Кэли $A = (a_{ij})$ размерности $N
\times N$ и подмножество $X \subset S$.

\textit{Выход.} Подполугруппа $\langle X \rangle \subset S$.

\begin{enumerate}
  \item
    Положим $i = 0$, $X_0 = X$;
  \item
    Для $X_i$ вычислим $\overline{X}_l = \{ x \cdot y ~ | ~ x \in X_i \land y
    \in X \}$ и положим $X_{i + 1} = X_i \cup \overline{X}_l$ ($x \cdot y =
    a_{xy}$);
  \item
    Вычислим \[ \langle X \rangle = \bigcup^\infty_{i = 0} X_i \]
\end{enumerate}

Трудоёмкость алгоритма "--- $O(N^3)$.


%
\subsection{Алгоритм построения полугруппы бинарных отношений по заданному порождающему множеству}

\textit{Вход.} Конечное множество $X$ бинарных отношений размерности $M$,
заданное булевыми матрицами размерности $N \times N$.

\textit{Выход.} Полугруппа $\langle X \rangle$.

\begin{enumerate}
  \item
    Пусть каждому бинарному отношению $x_i \in X$ ($0 \leq i < M$) соответствует
    матрица $A_i$. Зададим список $L$ так, что $L_i = A_i \, (0 \leq i < M)$.
    Полученный список $L$ является полугруппой $\langle X \rangle$.
  \item
    Зададим новый список $S$ так, что $S_i = L_j \odot L_k$
    $(\forall 0 \leq i < |L|^2) \, (\forall 0 \leq j < |L|) \, 
    (\forall 0 \leq k < |L|)$, где $|L|$ "--- количество элементов в 
    списке $L$.
  \item
    Если $(\exists S_i \in S) \, (\forall L_j \in L) \, S_i \neq L_j$, то
    добавим все элементы $S$ в список $L$ и переходим к шагу 2. Иначе,
    заканчиваем алгоритм.
\end{enumerate}

Трудоёмкость алгоритма "--- $O(N^M)$


%
\subsection{Алгоритм построения полугруппы по порождающему множеству и определяющим соотношениям}

\textit{Вход.} Конечное множество символов $A$ мощности $N$ и конечное множество
$R$ мощности $M$ определяющих соотношений.

\textit{Выход.} Полугруппа $\langle A | R \rangle$.

\begin{enumerate}
  \item 
    Инициализируем $\langle A | R \rangle$ элементами множества $A$.
    Инициализируем множество определяющих соотношений $M$ множеством
    $\langle A | R \rangle$. Инициализируем флаг: $is\_inserted = False$.
  \item 
    Для каждого определяющего соотношения $x_i \in \langle A | R \rangle$ и $m_j
    \in M \; (0 \leq i < N, 0 \leq j < |M|)$ вычисляем $x_i m_j$. Если такого
    определяющего соотношения ещё нет в $\langle A | R \rangle$, то добавляем
    его в $\langle A | R \rangle$ и устанавливаем $is\_inserted = True$ (этот флаг
    означает, что добавлено хотя бы одно новое значение в полугруппу). Иначе
    записываем в список соотношений соотношение $x_i m_j \to m_j$.
  \item 
    Если $is\_inserted = False$, то конец алгоритма, иначе $M = \langle A | R \rangle$ и
    возврат к шагу 2.
\end{enumerate}

Трудоёмкость алгоритма "--- $O(N^M)$


\section{Программная реализация}

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


\section{Результаты тестирования}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.7\textwidth]{test1.png}
  \caption{Проверка построения подполугруппы по таблице Кэли}
\end{figure}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.8\textwidth]{test2.png}
  \caption{Проверка построения полугруппы бинарных отношений порождающему множеству}
\end{figure}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.75\textwidth]{test3_1.png}
  \caption{Проверка построения полугруппы по порождающему множеству и определяющим соотношениям (часть 1)}
\end{figure}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.75\textwidth]{test3_2.png}
  \caption{Проверка построения полугруппы по порождающему множеству и определяющим соотношениям (часть 2)}
\end{figure}


\section{Решение задач}

\subsection*{Задание 1}

Найдите полугруппу S = $\langle f, g \rangle$ преобразований множества $X = {1,
2, 3}$, порожденную следующими преобразованиями $f, g$ в симметрической
полугруппе $T(X)$ преобразований множества $X$:

\begin{equation*}
  f = \begin{pmatrix}
    1 & 2 & 3 \\
    1 & 1 & 1
  \end{pmatrix},
  g = \begin{pmatrix}
    1 & 2 & 3 \\
    2 & 3 & 2
  \end{pmatrix}
\end{equation*}

Известно, что множество преобразований $f, g$ порождает полугруппу S = $\langle
f, g \rangle$ преобразований множества X, которая состоит из элементов $f, g,
f^2, f g, gf, g^2, \dots$ и является подполугруппой конечной полугруппы $T(X)$.

$f^2 = 
\begin{pmatrix}
  1 & 2 & 3 \\
  1 & 1 & 1
\end{pmatrix} \cdot
\begin{pmatrix}
  1 & 2 & 3 \\
  1 & 1 & 1
\end{pmatrix} = 
\begin{tabular}{c c c c}
& 1 & 2 & 3 \\
f & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 1 & 1 & 1 \\
f & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 1 & 1 & 1 \\
\end{tabular} = 
\begin{pmatrix}
1 & 2 & 3 \\
1 & 1 & 1
\end{pmatrix}$

$fg = 
\begin{pmatrix}
  1 & 2 & 3 \\
  1 & 1 & 1
\end{pmatrix} \cdot
\begin{pmatrix}
  1 & 2 & 3 \\
  2 & 3 & 2
\end{pmatrix} = 
\begin{tabular}{c c c c}
& 1 & 2 & 3 \\
f & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 1 & 1 & 1 \\
g & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 2 & 2 & 2 \\
\end{tabular} = 
\begin{pmatrix}
1 & 2 & 3 \\
2 & 2 & 2
\end{pmatrix}$

$gf = 
\begin{pmatrix}
  1 & 2 & 3 \\
  2 & 3 & 2
\end{pmatrix} \cdot
\begin{pmatrix}
  1 & 2 & 3 \\
  1 & 1 & 1
\end{pmatrix} = 
\begin{tabular}{c c c c}
& 1 & 2 & 3 \\
g & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 2 & 3 & 2 \\
f & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 1 & 1 & 1 \\
\end{tabular} = 
\begin{pmatrix}
1 & 2 & 3 \\
1 & 1 & 1
\end{pmatrix}$

$g^2 = 
\begin{pmatrix}
  1 & 2 & 3 \\
  2 & 3 & 2
\end{pmatrix} \cdot
\begin{pmatrix}
  1 & 2 & 3 \\
  2 & 3 & 2
\end{pmatrix} = 
\begin{tabular}{c c c c}
& 1 & 2 & 3 \\
g & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 2 & 3 & 2 \\
g & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
& 3 & 2 & 3 \\
\end{tabular} = 
\begin{pmatrix}
1 & 2 & 3 \\
3 & 2 & 3
\end{pmatrix}$


\subsection*{Задание 2}

Найдите индекс и период следующих элементов $a$ полугруппы преобразований
множества $X = \{ 1, 2, 3, 4, 5 \}$:

\begin{equation*}
  a = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    2 & 4 & 1 & 2 & 1
  \end{pmatrix}
\end{equation*}

Вычислим $aa$:

\begin{equation*}
  aa = 
  \begin{tabular}{c c c c c c}
    & 1 & 2 & 3 & 4 & 5\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 2 & 4 & 1 & 2 & 1\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 4 & 2 & 2 & 4 & 2\\
  \end{tabular} = 
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5\\
    4 & 2 & 2 & 4 & 2
  \end{pmatrix}
\end{equation*}

Вычислим $aaa$:

\begin{equation*}
  aaa = 
  \begin{tabular}{c c c c c c}
    & 1 & 2 & 3 & 4 & 5\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 2 & 4 & 1 & 2 & 1\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 4 & 2 & 2 & 4 & 2\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 2 & 4 & 4 & 2 & 4\\
  \end{tabular} = 
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5\\
    2 & 4 & 4 & 2 & 4
  \end{pmatrix}
\end{equation*}

  Вычислим $aaaa$:
\begin{equation*}
  aaaa = 
  \begin{tabular}{c c c c c c}
    & 1 & 2 & 3 & 4 & 5\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 2 & 4 & 1 & 2 & 1\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 4 & 2 & 2 & 4 & 2\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 2 & 4 & 4 & 2 & 4\\
    a & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
    & 4 & 2 & 2 & 4 & 2\\
  \end{tabular} = 
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5\\
    4 & 2 & 2 & 4 & 2\\
  \end{pmatrix}
\end{equation*}

Можно заметить, что $aaaa \to aa$. Получаем, что каждый $2k$"=й элемент ($k \in
\mathbb{N}$) полугруппы будет иметь преобразование

\begin{equation*}
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    2 & 3 & 1 & 1 & 2
  \end{pmatrix}
\end{equation*}
    
Таким образом, период равен 2.


\subsection*{Задание 3}

Найдите полугруппу $S$ по следующему её копредставлению:
\begin{equation*}
  S = \langle x,y : xy = yx, x^2 = y, y^3 = x \rangle
\end{equation*}

Выделим полную систему представителей классов конгруэнции $\epsilon$, которая
определяется соотношениями данного копредставления. Для этого последовательно
рассмотрим слова фиксированной длины и выделим те, которые не будут эквивалентны
между собой относительно конгруэнции $\epsilon$.

Рассмотрим слова длины 1: $x$, $y$ –- эти слова не эквивалентны между собой
относительно конгруэнции $\epsilon$.

Рассмотрим слова длины 2, которые получаются из слов длины 1 путем
последовательного умножения их справа на буквы $x$ и $y$: $x^2 = y, xy, yx = xy,
y^2$ -- из этих слов только слова $xy$, $y^2$ не эквивалентны относительно
конгруэнции $\epsilon$ другим ранее выделенным словам.

Теперь рассмотрим слова длины $3$, которые получаются из выделенных слов длины
$2$ путем последовательного умножения их справа на буквы $x$ и $y$: $xyx = y^2$,
$xy^2$,  $y^2x = x^2y$, $y^3 = x$ –- из этих слов только слово $xy^2$ не
эквивалентно относительно конгруэнции $\varepsilon$ другим ранее выделенным
словам.

Наконец рассмотрим слова длины $4$, которые получаются из выделенного слова
длины $3$ путем последовательного умножения его справа на буквы $x$ и $y$:
$xy^2x = x^2y^2 = y^3 = x$, $xy^3 = x^2 = y$ - все эти слова эквивалентны
относительно конгруэнции $\varepsilon$ ранее выделенным словам.

Значит, $S = \{x, y, xy, y^2, xy^2 \}$ "--- полная система представителей
классов конгруэнции $\varepsilon$. Операция умножения $\cdot$ таких слов
определяется с точностью до конгруэнции $\varepsilon$ по следующей таблице Кэли:

\begin{table}[H]
  \centering
  \begin{tabular}{c|c|c|c|c|c}
             & $x$ & $y$  & $xy$  & $y^2$ & $xy^2$ \\ \hline
    $x$      & $x$ & $xy$ & $xy$  & $xy^2$ & $xy^2$ \\ \hline
    $y$      & $xy$ & $y^2$ & $xy^2$ & $y$ & $xy$ \\ \hline
    $xy$     & $xy$ & $xy^2$ & $xy^2$ & $xy$ & $xy$ \\ \hline
    $y^2$    & $xy^2$ & $y$ & $xy$ & $y^2$ & $xy^2$ \\ \hline
    $xy^2$   & $xy^2$ &  $xy$  &  $xy$ & $xy^2$ & $xy^2$ \\
  \end{tabular}
\end{table}


\conclusion

В ходе выполнения данной лабораторной работы были рассмотрены понятия
полугруппы, подполугруппы, порождающего множества, подгруппы и определяющих
соотношений. С использованием данных определений были разработаны алгоритмы
построения подполугрупп по таблице Кэли, построения полугруппы бинарных
отношений по заданному порождающему множеству, построения полугруппы по
порождающему множеству и определяющим соотношениям, а также была произведена
оценка сложности данных алгоритмов. Программная реализация на языке Python с
библиотекой numpy успешно прошла тестирование.

\end{document}