From 662187638535772af24fc3384ce0b14397497b06 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 15 May 2022 16:37:29 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B8?= =?UTF-8?q?=D0=B5=20=D0=BE=D1=82=D1=87=D1=91=D1=82=D0=B0=20=D0=BF=D0=BE=20?= =?UTF-8?q?=D0=BF=D1=8F=D1=82=D0=BE=D0=B9=20=D0=BB=D0=B0=D0=B1=D0=B5?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- lab5/report/lab5.tex | 273 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 273 insertions(+) create mode 100644 lab5/report/lab5.tex (limited to 'lab5/report/lab5.tex') 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 + Разработать алгоритмы вычисления отношений Грина и построения + <>"=картины конечной полугруппы. +\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}$ можно изобразить + с помощью следующей <>"=диаграммы, клетки которой + являются классами эквивалентности $\mathfrak{H}$, лежащими в + $\mathfrak{D}$. + + \begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{egg-box.png} + \caption{<>"=диаграмма} + \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 + +В ходе выполнения данной лабораторной работы были рассмотрены понятия идеалов +полугруппы, соотношений Грина на полугруппах и их свойства, +<>"=диаграммы. С использованием данных определений были разработаны +алгоритмы построения идеалов полугруппы по таблице Кэли, вычисления отношений +Грина и построения <>"=диаграмм, а также была произведена оценка +сложности данных алгоритмов. Программная реализация на языке Python с +библиотекой numpy успешно прошла тестирование. + +\end{document} -- cgit v1.2.3