path: root/lab5/report/lab5.tex

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

\begin{figure}[H]
  \centering
  \includegraphics[width=0.7\textwidth]{test2.png}
  \caption{Идеалы полугруппы и egg"=box"=диаграмма}
\end{figure}


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

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

Найдите подполугруппу $\langle x \rangle$, правый $[x)$, левый $(x]$ и
двусторонний $(x)$ идеалы полугруппы $S$, порожденные элементом $x$, и
определите порядок элемента $x$ для каждого элемента полугруппы, на которой
бинарная операция задана следующей таблицей Кэли:
\begin{table}[H]
  \small
  \centering
  \begin{tabular}{|c|cccc|}
    \hline
    $\cdot$ & a & b & c & d \\ \hline
    a       & a & b & c & d \\
    b       & b & c & d & a \\
    c       & c & d & a & b \\
    d       & d & a & b & c \\ \hline
  \end{tabular}
\end{table}
\begin{align*}
  [a) = \{a, b, c, d\}, \; (a] &= \{a, b, c, d\}, \; (a) = \{a, b, c, d\} \\
  [b) = \{b, c, d, a\}, \; (b] &= \{b, c, d, a\}, \; (b) = \{b, c, d, a\} \\
  [c) = \{c, d, a, b\}, \; (c] &= \{c, d, a, b\}, \; (c) = \{c, d, a, b\} \\
  [d) = \{d, a, b, c\}, \; (d] &= \{d, a, b, c\}, \; (d) = \{d, a, b, c\}
\end{align*}

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

Для полугрупп из Задания 1 найдите отношения Грина и <<egg-box>>-картины.
\begin{equation*}
  \mathfrak{R} =
    \begin{pmatrix}
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1
    \end{pmatrix}
  \quad
  \mathfrak{L} =
    \begin{pmatrix}
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1
    \end{pmatrix}
\end{equation*}

Тогда отношение Грина будет представлено матрицей $\mathfrak{D} = \mathfrak{R}
\lor \mathfrak{L}$:
\begin{equation*}
  \mathfrak{D} =
    \begin{pmatrix}
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1
    \end{pmatrix}
\end{equation*}

\begin{figure}[H]
  \centering
  \includegraphics[width=0.3\textwidth]{myegg2.png}
  \caption{<<egg"=box>>"=диаграмма}
\end{figure}

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

По копредставлению полугруппы S найдите отношения Грина и <<egg-box>>-картины.

Найдём полугруппу $S$ по ее копредставлению $\langle x, y : xy = yx, x^3 = x,
y^2 = x \rangle$. Выделим полную систему представителей классов конгруэнции
$\varepsilon$, которая определяется соотношениями данного копредставления. Для
этого последовательно рассмотрим слова фиксированной длины и выделим те, которые
не будут эквивалентны между собой относительно конгруэнции $\varepsilon$.

Слова длины 1 $\{ x, y \}$ не эквивалентны между собой относительно конгруэнции
$\varepsilon$.

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

Аналогично рассмотрим слова длины 3: $\{ x^3 = x, x^2y, xyx = x^2y, xy^2 = x^2
\}$. Из этих слов только слово $x^2y$ не эквивалентно относительно конгруэнции
$\varepsilon$ другим ранее выделенным словам.

Аналогично рассмотрим слова длины 4: $\{ x^2yx = x^3y = xy, x^2y^2 = x^3 = x
\}$. Все эти слова эквивалентны относительно конгруэнции $\varepsilon$ ранее
выделенным словам.

Получаем, $S = \{x, y, x^2, xy, x^2y \}$ "--- полная система представителей
классов конгруэнции $\varepsilon$. Операция умножения $\cdot$ таких слов
определяется с точностью до конгруэнции $\varepsilon$ по следующей таблице Кэли:
\begin{table}[H]
  \centering
  \begin{tabular}{|c|ccccc|}
  \hline
  $\cdot $ & $x$    & $y$    & $x^2$  & $xy$   & $x^2y$ \\ \hline
  $x$      & $x^2$  & $xy$   & $x$    & $x^2y$ & $xy$   \\ 
  $y$      & $xy$   & $x$    & $x^2y$ & $x^2$  & $x$    \\ 
  $x^2$    & $x$    & $x^2y$ & $x^2$  & $xy$   & $x^2y$ \\ 
  $xy$     & $x^2y$ & $x^2$  & $xy$   & $x$    & $x^2$  \\ 
  $x^2y$   & $xy$   & $x$    & $x^2y$ & $x^2$  & $x$    \\ \hline
  \end{tabular}
\end{table}

Получим таким образом $\mathfrak{R}$ и $\mathfrak{L}$:
\begin{equation*}
  \mathfrak{R} =
    \begin{pmatrix}
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1
    \end{pmatrix}
  \quad
  \mathfrak{L} =
    \begin{pmatrix}
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1
    \end{pmatrix}
\end{equation*}

Отношение Грина определяется матрицей $\mathfrak{D} = \mathfrak{R} \lor
\mathfrak{L}$:
\begin{equation*}
  \mathfrak{D} =
    \begin{pmatrix}
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1 \\
      1 & 1 & 1 & 1 & 1
    \end{pmatrix}
\end{equation*}

Исходя из полученной матрицы отношений Грина, можно построить
изображение <<egg"=box>>"=диаграммы:

\begin{figure}[H]
  \centering
  \includegraphics[width=0.3\textwidth]{myegg2.png}
  \caption{<<egg"=box>>"=диаграмма}
\end{figure}


\conclusion

В ходе выполнения данной лабораторной работы были рассмотрены понятия идеалов
полугруппы, соотношений Грина на полугруппах и их свойства,
<<egg"=box>>"=диаграммы. С использованием данных определений были разработаны
алгоритмы построения идеалов полугруппы по таблице Кэли, вычисления отношений
Грина и построения <<egg"=box>>"=диаграмм, а также была произведена оценка
сложности данных алгоритмов. Программная реализация на языке Python с
библиотекой numpy успешно прошла тестирование.

\end{document}