diff options
Diffstat (limited to 'lab4')
| -rw-r--r-- | lab4/lab4.py | 89 | ||||
| -rw-r--r-- | lab4/report/lab4.tex | 89 |
2 files changed, 94 insertions, 84 deletions
diff --git a/lab4/lab4.py b/lab4/lab4.py index b4c2e73..0f28157 100644 --- a/lab4/lab4.py +++ b/lab4/lab4.py @@ -70,22 +70,29 @@ def make_semigroup_binrel(): for _ in range(n): matrix.append(list(map(int, input().split()))) matrices[str(i + 1)] = np.array(matrix) - - combinations = [] - for i in range(1, q + 1): - combination = list(it.product(map(str, range(1, q + 1)), repeat=i)) - combinations.extend(combination) - - for combination in combinations: - matrix = matrices[combination[0]].copy() - word = combination[0] - for comb_i in range(1, len(combination)): - matrix *= matrices[combination[comb_i]] - word += combination[comb_i] - matrices[word] = matrix - find_correlation(matrices) + while True: + new_matrices = {} + for key_i, value_i in matrices.items(): + for key_j, value_j in matrices.items(): + new_matrices[key_i + key_j] = value_i * value_j + + already_exists = [] + for mat in new_matrices.values(): + flags = [] + for mat_old in matrices.values(): + flags.append(np.array_equal(mat, mat_old)) + already_exists.append(any(flags)) + if not any(flags): + break + + if all(already_exists): + break + matrices.update(new_matrices) + + find_correlation(matrices) + def make_semigroup(): print("Введите элементы полугруппы:") @@ -101,28 +108,42 @@ def make_semigroup(): print(f"Введите значения преобразования '{generators_list[i]}' " "элементов полугруппы:") print(*elements) - translations.append(input().split()) + translations.append((generators_list[i], input().split())) - combinations = [] - for i in range(1, gn + 1): - combinations.extend(it.product(''.join(generators_list), repeat=i)) + copresentation = translations.copy() + correlations = {} + while True: + is_inserted = False + for key_i, value_i in translations: + for key_j, value_j in copresentation: + new_word = key_i + key_j + + new_value = [] + for elem in value_i: + if elem == "*": + sec_sem = "*" + else: + sec_sem = value_j[int(elem) - 1] + new_value.append(sec_sem) + + find_corr = False + for k, v in copresentation: + if np.array_equal(new_value, v): + correlations[new_word] = k + find_corr = True + if not find_corr: + copresentation.append((new_word, new_value)) + is_inserted = True + if not is_inserted: + break - result = {} - for combination in combinations: - correlation = [] - for i in elements: - element = i - for generator in combination: - if element not in elements: - element = '*' - else: - gi = generators_list.index(generator) - si = elements.index(element) - element = translations[gi][si] - correlation.append(element) - result[combination] = correlation - - find_correlation(result) + print("Копредставление: ") + for key, value in copresentation: + print(key + ":", value) + + print("Полученные соотношения: ") + for key, value in correlations.items(): + print(key, "->", value) def main(): 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{Программная реализация} |