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}


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

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

решение

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

решение

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

решение


\conclusion

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

\end{document}