path: root/lab4/report/lab4.tex

\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$}.


\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$ бинарных отношений, заданное булевыми
матрицами размерности $N \times N$.

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

\begin{enumerate}
  \item
    Пусть каждому бинарному отношению $x_i \in X$ ($0 \leq i < N$) соответствует
    матрица $A_i$. Зададим список $L$ так, что $L_i = A_i \, (0 \leq i < N)$.
    Полученный список $L$ является полугруппой $\langle X \rangle$.
  \item
    Создать список $C$, элементы которого будут $c_k \in C$, где $0 \leq k <
    (N^1 + N^2 + \dots + N^N)$. То есть этот список является суммой размещений с
    повторениями. Каждая комбинация $c_k$ будет определять некоторую
    совокупность матрицы, которые будут обрабатываться на следующем шаге.
  \item
    Возьмём матрицу $A_i$ ($0 \leq i < N$) и поэлементно умножим её на матрицы
    $B_0, \dots, B_l$ согласно текущей комбинации $c_k$ ($0 \leq k < (N^1 + N^2
    + \dots + N^N)$), где матрицы $B_1, \dots, B_l$ составляют текущую комбинацию
    $c_k$ ($l$ -- количество элементов в $c_k$). Таким образом, получим матрицу
    $H = A_i \odot B_1 \odot \dots \odot B_l$, где $\odot$ -- операция
    поэлементного умножения. Добавим $H$ в список $L$ в качестве нового
    элемента полугруппы $\langle X \rangle$.
  \item
    Шаг 3 необходимо повторить $k$ раз ($0 \leq k < (N^1 + N^2 + \dots + N^N)$).
\end{enumerate}

Трудоёмкость алгоритма "--- $O((N^1 + N^2 + \dots + N^N) \cdot l)$, где $l$ "---
количество элементов в $c_k \in C$.


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

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

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

\begin{enumerate}
  \item
    Каждому преобразованию $r_i \in R$ ($0 \leq i \leq M - 1$) соответствует
    список элементов множества $A$, то есть $a_j \in A$ ($0 \leq j < N$) "---
    элементы, в которые осуществляется переход из исходных элементов множества
    $A$. Определим список $T$ как $T_i = \{ a_j \in A \}$ ($0 \leq i \leq N -
    1$), где $a_j$ соответствует некоторому $a'_j \in A$ (из исходного множества
    символов).
  \item
    Создать список $C$, элементы которого будут $c_k \in C$, где $0 \leq k \leq
    (M^1 + M^2 + \dots + M^N - 1)$. Этот список "--- сумма размещений с
    повторениями, каждая такая комбинация определяет некоторую упорядоченную
    совокупность соотношений, которые применяются к исходным элементам множества
    $A$.
  \item
    Инициализировать пустой словарь $D$, где ключом будет являться комбинация
    $c_k \in C$ ($0 \leq k \leq (M^1 + M^2 + \dots + M^N) - 1$), а значением
    список из элементов $b_j$, где $0 \leq j \leq N - 1$. Этот словарь будет
    определять полугруппу $\langle A | R \rangle$ (копредставление). Каждый
    элемент $b_j$ находится по списку $T$: $b_j = T_{ij}$, где $i$ -- индекс
    элемента $r_i \in R$ ($0 \leq i < M$), $j$ -- индекс элемента $a_j \in A$
    ($0 \leq j \leq N - 1$) (Например, последовательность определяющих
    соотношений $abc$ по сути определяет элемент, который задан как $T_{ip}$,
    где $p = T_{iv}$, где $v = T_{ij}$ при некоторых $0 \leq i, j, v, p \leq N -
    1$). Далее добавить в словарь по ключу $c_k$ список из элементов $b_j$ при
    $0 \leq j \leq N - 1$, т.е. $D[c_k] = [b_0, \dots, b_j, \dots, b_{N - 1}]$
    (где каждый элемент $b_j$ соответствует результату преобразований после
    применения определяющих соотношений к исходному элементу $a_j$ множества
    $A$), где $0 \leq j \leq N - 1$, $0 \leq k \leq (M^1 + M^2 + \dots + M^N) -
    1$.
\end{enumerate}

Трудоёмкость алгоритма "--- $O((M^1 + M^2 + \dots + M^n) \cdot n^2 \cdot 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}