From e9319f8888b375dc0007d4825ced306fa14a8f89 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Sun, 1 May 2022 00:07:32 +0400
Subject: =?UTF-8?q?=D0=98=D1=81=D0=BF=D1=80=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD?=
 =?UTF-8?q?=D0=B8=D1=8F=20=D1=87=D0=B5=D1=80=D0=B2=D1=91=D1=80=D1=82=D0=BE?=
 =?UTF-8?q?=D0=B9=20=D0=BB=D0=B0=D0=B1=D1=8B?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab4/report/lab4.tex | 89 +++++++++++++++++++++++-----------------------------
 1 file changed, 39 insertions(+), 50 deletions(-)

(limited to 'lab4/report/lab4.tex')

diff --git a/lab4/report/lab4.tex b/lab4/report/lab4.tex
index 1790900..8f1df3d 100644
--- a/lab4/report/lab4.tex
+++ b/lab4/report/lab4.tex
@@ -87,6 +87,17 @@ $\phi(w_1) = \phi(w_2)$, то будем писать $w_1 = w_2$ и назыв
 $\rho$ и выражение $<A: {w_1 = w_2 : (w_1, w_2) \in \rho}>$ называется
 \textbf{копредставлением полугруппы $S$}.
 
+Обозначим символом $A^+$ множество всех непустых слов над алфавитом и символом
+$A^*$ "--- множество слов $A^* = A^+ \cup \{\Lambda\}$. На этих множествах слов
+определена операция умножения, которая называется операцией конкатенации слов и
+определяется по правилу: любым словам $w_1 = a_1 \dots a_n$ и $w_2 = b_1 \dots
+b_m$ операция конкатенации ставит в соответствие слово $w_1 \cdot w_2 = a_1
+\dots a_n b_1 \dots b_n$. В результате множество слов $A^+$ с операцией
+конкатенации образует полугруппу, которая называется полугруппой слов над
+алфавитом $A$, и множество слов $A^*$ с операцией конкатенации образует
+полугруппу с единичным элементом $\Lambda$, которая называется моноидом слов над
+алфавитом $A$.
+
 
 \section{Алгоритмы}
 
@@ -115,78 +126,56 @@ $\rho$ и выражение $<A: {w_1 = w_2 : (w_1, w_2) \in \rho}>$ назыв
 %
 \subsection{Алгоритм построения полугруппы бинарных отношений по заданному порождающему множеству}
 
-\textit{Вход.} Конечное множество $X$ бинарных отношений, заданное булевыми
-матрицами размерности $N \times N$.
+\textit{Вход.} Конечное множество $X$ бинарных отношений размерности $M$,
+заданное булевыми матрицами размерности $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)$.
+    Пусть каждому бинарному отношению $x_i \in X$ ($0 \leq i < M$) соответствует
+    матрица $A_i$. Зададим список $L$ так, что $L_i = A_i \, (0 \leq i < M)$.
     Полученный список $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$.
+    Зададим новый список $S$ так, что $S_i = L_j \odot L_k$
+    $(\forall 0 \leq i < |L|^2) \, (\forall 0 \leq j < |L|) \, 
+    (\forall 0 \leq k < |L|)$, где $|L|$ "--- количество элементов в 
+    списке $L$.
   \item
-    Шаг 3 необходимо повторить $k$ раз ($0 \leq k < (N^1 + N^2 + \dots + N^N)$).
+    Если $(\exists S_i \in S) \, (\forall L_j \in L) \, S_i \neq L_j$, то
+    добавим все элементы $S$ в список $L$ и переходим к шагу 2. Иначе,
+    заканчиваем алгоритм.
 \end{enumerate}
 
-Трудоёмкость алгоритма "--- $O((N^1 + N^2 + \dots + N^N) \cdot l)$, где $l$ "---
-количество элементов в $c_k \in C$.
+Трудоёмкость алгоритма "--- $O(N^M)$
 
 
 %
 \subsection{Алгоритм построения полугруппы по порождающему множеству и определяющим соотношениям}
 
 \textit{Вход.} Конечное множество символов $A$ мощности $N$ и конечное множество
-$R$ определяющих соотношений мощности $M$.
+$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$.
+  \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$, то конец алгоритма, иначе $M = \langle A | R \rangle$ и
+    возврат к шагу 2.
 \end{enumerate}
 
-Трудоёмкость алгоритма "--- $O((M^1 + M^2 + \dots + M^n) \cdot n^2 \cdot M)$.
+Трудоёмкость алгоритма "--- $O(N^M)$
 
 
 \section{Программная реализация}
-- 
cgit v1.2.3

