diff options
Diffstat (limited to 'lab4/report/lab4.tex')
| -rw-r--r-- | lab4/report/lab4.tex | 472 |
1 files changed, 472 insertions, 0 deletions
diff --git a/lab4/report/lab4.tex b/lab4/report/lab4.tex new file mode 100644 index 0000000..1790900 --- /dev/null +++ b/lab4/report/lab4.tex @@ -0,0 +1,472 @@ +\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} |