1 files changed, 273 insertions, 0 deletions
diff --git a/lab5/report/lab5.tex b/lab5/report/lab5.tex
new file mode 100644
index 0000000..40995f3
--- /dev/null
+++ b/lab5/report/lab5.tex
@@ -0,0 +1,273 @@
+\documentclass[spec, och, labwork2]{SCWorks}
+\usepackage{preamble}
+
+\begin{document}
+\include{titlepage.tex}
+\tableofcontents
+
+\section{Постановка задачи}
+
+Цель работы "--- изучение строения полугрупп с помощью отношений Грина.
+Порядок выполнения работы:
+
+\begin{enumerate}
+  \item
+    Рассмотреть понятия идеалов полугруппы. Разработать алгоритмы построения
+    идеалов полугруппы по таблице Кэли.
+  \item
+    Рассмотреть понятия и свойства отношений Грина на полугруппах.
+  \item
+    Разработать алгоритмы вычисления отношений Грина и построения
+    <<egg"=box>>"=картины конечной полугруппы.
+\end{enumerate}
+
+
+\section{Теоретические сведения}
+
+\begin{definition}
+  Полугруппа "--- это алгебра $S = (S, \cdot)$ с одной ассоциативной бинарной
+  операцией $\cdot$, т.~е. выполняется
+  \begin{equation*}
+    (\forall ~ x, y, z \in S) ~ (x \cdot y) \cdot z = x \cdot (y \cdot z)
+  \end{equation*}
+\end{definition}
+
+\begin{definition}
+  Непустое подмножество $I \subset S$ называется правым (левым) идеалом
+  полугруппы $S$, если $(\forall ~ x \in I) ~ (\forall ~ y \in S)$ выполняется
+  условие $xy \in I$ ($yx \in I$), т.~е. $I \cdot S \subset I$ ($S \cdot I
+  \subset I$). Если $I$ "--- одновременно левый и правый идеал полугруппы $S$,
+  то $I$ называется двусторонним идеалом (или просто идеалом) полугруппы $S$.
+  Ясно, что в коммутативной полугруппе $S$ все эти определения совпадают.
+\end{definition}
+  
+\begin{lemma}
+  Множество всех идеалов $\text{Id} S$ (соответственно, левых идеалов
+  $\text{LId} S$ или правых идеалов $\text{RId} S$) любой полугруппы $S$
+  является системой замыкания. Пусть $X$ "--- подмножество полугруппы $S$. Тогда
+  наименьший правый идеал полугруппы $S$, содержащий подмножество $X$, равен
+  $(X] = XS^1 = X \cup XS$, наименьший левый идеал полугруппы $S$, содержащий
+  подмножество $X$, равен $[X) = S^1X = X \cup SX$ и наименьший идеал полугруппы
+  $S$, содержащий подмножество $X$, равен $[X] = S^1XS^1 = X \cup XS \cup SX
+  \cup SXS$.
+\end{lemma}
+
+В частности, любой элемент $a \in S$ определяет наименьшие правый, левый и
+двусторонний идеалы: $(a] = aS^1$, $[a) = S^1a$ и $[a] = S^1aS^1$, которые
+называются главными (соответственно, правыми, левыми и двусторонними) идеалами.
+Минимальные относительно теоретико"=множественного включения идеалы (левые или
+правые идеалы) называются минимальными идеалами (минимальными левыми или правыми
+идеалами).
+
+\begin{lemma}
+  Если полугруппа имеет минимальный идеал, то он является ее наименьшим идеалом
+  и называется ядром полугруппы.
+\end{lemma}
+
+\begin{example}
+  В полугруппе натуральных чисел с операцией сложения $\mathbb{N} = (\mathbb{N},
+  +)$ главные идеалы $(n] = {n, n + 1, n + 2, \dots}$ образуют бесконечную
+  последовательность с пустым пересечением.
+\end{example}
+
+Отображения $f: a \mapsto [a]$, $f_r: a \mapsto (a]$, $f_l: a \mapsto [a)$, $a
+\in S$ определяют ядра $\mathfrak{J} = \text{ker} ~ f$, $\mathfrak{R} =
+\text{ker} ~ f_r$, $\mathfrak{L} = \text{ker} ~ f_l$ по формулам:
+\begin{align*}
+    (a, b) \in \mathfrak{J} &\Longleftrightarrow [a] = [b] \\
+    (a, b) \in \mathfrak{R} &\Longleftrightarrow (a] = (b] \\
+    (a, b) \in \mathfrak{L} &\Longleftrightarrow [a) = [b)
+\end{align*}
+
+Все эти отношения, а также отношения $\mathfrak{D} = \mathfrak{R} \vee
+\mathfrak{L}$, $\mathfrak{H} = \mathfrak{R} \cap \mathfrak{L}$ являются
+эквивалентностями на множестве $S$, которые называются отношениями Грина
+полугруппы $S$. Классы этих эквивалентностей, порожденные элементом $a \in S$,
+обозначаются $J_a, R_a, L_a, D_a, H_a$ соответственно.
+
+\begin{lemma}
+  Отношения Грина полугруппы $S$ удовлетворяют следующим свойствам:
+  \begin{enumerate}
+    \item
+      эквивалентность $\mathfrak{R}$ регулярна слева и эквивалентность
+      $\mathfrak{L}$ регулярна справа, т.е.  $(a, b) \in \mathfrak{R}
+      \Rightarrow (xa, xb) \in \mathfrak{R}$ и $(a, b) \in \mathfrak{L}
+      \Rightarrow (ax, bx) \in \mathfrak{L}$ для любых $x \in S$;
+    \item
+      эквивалентности $\mathfrak{R}$, $\mathfrak{L}$ коммутируют;
+    \item
+      $\mathfrak{D} = \mathfrak{R} \cdot \mathfrak{L} = \mathfrak{L} \cdot
+      \mathfrak{R}$;
+    \item
+      если полугруппа $S$ конечна, то $\mathfrak{D} = \mathfrak{J}$;
+    \item
+      любой класс $\mathfrak{D}$ эквивалентности $\mathfrak{D}$ можно изобразить
+      с помощью следующей <<egg"=box>>"=диаграммы, клетки которой
+      являются классами эквивалентности $\mathfrak{H}$, лежащими в
+      $\mathfrak{D}$.
+
+      \begin{figure}[H]
+        \centering
+        \includegraphics[width=0.8\textwidth]{egg-box.png}
+        \caption{<<egg"=box>>"=диаграмма}
+      \end{figure}
+  \end{enumerate}
+\end{lemma}
+
+
+\section{Алгоритмы}
+
+%
+\subsection{Построение правых идеалов полугруппы по таблице Кэли}
+
+\textit{Вход} Конечная полугруппа $S$ с таблицей Кэли $A = (a_{ij})$ размерности
+$N \times N$ и элементом $x \in S$.
+
+\textit{Выход}: Правый идеал $\text{Id}_R$ полугруппы $S$, порожденный элементом
+$x \in S$.
+
+\begin{enumerate}
+  \item Правый идеал $\text{Id}_R$, порожденный элементом $x \in S$ состоит из
+  элементов $a_{xi} ~ (\forall i \in S)$
+\end{enumerate}
+
+Трудоёмкость алгоритма "--- $O(N)$
+
+%
+\subsection{Построение левых идеалов полугруппы по таблице Кэли}
+
+\textit{Вход} Конечная полугруппа $S$ с таблицей Кэли $A = (a_{ij})$ размерности
+$N \times N$ и элементом $x \in S$.
+
+\textit{Выход} Левый идеал $\text{Id}_L$ полугруппы $S$, порожденный элементом
+$x \in S$.
+
+\begin{enumerate}
+  \item Правый идеал $\text{Id}_L$, порожденный элементом $x \in S$ состоит из
+  элементов $a_{ix} ~ (\forall i \in S)$
+\end{enumerate}
+
+Трудоёмкость алгоритма "--- $O(N)$
+
+%
+\subsection{Построение двусторонних идеалов полугруппы по таблице Кэли}
+
+\textit{Вход} Конечная полугруппа $S$ с таблицей Кэли $A = (a_{ij})$ размерности
+$N \times N$ и элементом $x \in S$.
+
+\textit{Выход} Двусторонний идеал $\text{Id}$ полугруппы $S$, порожденный
+элементом $x \in S$.
+
+\begin{enumerate}
+  \item Построить правый идеал $\text{Id}_R$ с помощью алгоритма 3.1
+  \item Построить правый идеал $\text{Id}_L$ с помощью алгоритма 3.2
+  \item Двусторонний идеал $\text{Id} = \text{Id}_R \cup \text{Id}_L$
+\end{enumerate}
+
+Трудоёмкость алгоритма "--- $O(N)$
+
+%
+\subsection{Построение отношения Грина по таблице Кэли}
+
+\textit{Вход} Конечная полугруппа $S$ с таблицей Кэли $A = (a_{ij})$ размерности
+$N \times N$ и элементом $x \in S$.
+
+\textit{Выход} Матрица $D = (d_{ij})$ отношения Грина.
+
+\begin{enumerate}
+  \item
+    Построим матрицу $R = (r_{ij})$:
+    \begin{equation*}
+      (\forall i \in S) ~ (\forall j \in S) ~ r_{ij} = \begin{cases}
+        1, &\text{Id}_R(i) = \text{Id}_R(j) \\
+        0, &\text{иначе}
+      \end{cases}
+    \end{equation*}
+  \item
+    Аналогично построим матрицу $L = (l_{ij})$:
+    \begin{equation*}
+      (\forall i \in S) ~ (\forall j \in S) ~ l_{ij} = \begin{cases}
+        1, &\text{Id}_L(i) = \text{Id}_L(j) \\
+        0, &\text{иначе}
+      \end{cases}
+    \end{equation*}
+  \item
+    Матрица отношения Грина $D = R + L$
+\end{enumerate}
+
+Оценка сложности алгоритма равна $O(N^2)$.
+
+%
+\subsection{Алгоритм вычисления отношения Грина по порождающему множеству и определяющим соотношениям}
+
+\textit{Вход.} Конечное множество символов $A$ мощности $N$ и конечное множество
+$R$ мощности $M$ определяющих соотношений.
+
+\textit{Выход.} Отношение Грина $\mathfrak{D}$ полугруппы $\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$, то переход к шагу 4, иначе $M = \langle A | R
+    \rangle$ и возврат к шагу 2.
+  \item
+    По полугруппе $\langle A | R \rangle$ вычисляем матрицу $\mathfrak{D}$
+    отношения Грина с использованием алгоритма 3.4.
+\end{enumerate}
+
+Трудоёмкость алгоритма "--- $O(N^M)$
+
+
+\section{Программная реализация}
+
+\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../lab5.py}
+
+
+\section{Результаты тестирования}
+
+Картинки
+
+% \begin{figure}[H]
+%   \centering
+%   \includegraphics[width=0.7\textwidth]{test1.png}
+%   \caption{}
+% \end{figure}
+
+
+\section{Решение задач}
+
+\subsection*{Задание 1}
+
+решение
+
+\subsection*{Задание 2}
+
+решение
+
+\subsection*{Задание 3}
+
+решение
+
+
+\conclusion
+
+В ходе выполнения данной лабораторной работы были рассмотрены понятия идеалов
+полугруппы, соотношений Грина на полугруппах и их свойства,
+<<egg"=box>>"=диаграммы. С использованием данных определений были разработаны
+алгоритмы построения идеалов полугруппы по таблице Кэли, вычисления отношений
+Грина и построения <<egg"=box>>"=диаграмм, а также была произведена оценка
+сложности данных алгоритмов. Программная реализация на языке Python с
+библиотекой numpy успешно прошла тестирование.
+
+\end{document}