diff options
Diffstat (limited to 'lab4/report')
| -rw-r--r-- | lab4/report/lab4.tex | 89 |
1 files changed, 39 insertions, 50 deletions
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{Программная реализация} |