Добавил четвёртую лабу

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}