diff options
Diffstat (limited to 'lab2/report/tmp/algo.tex')
| -rw-r--r-- | lab2/report/tmp/algo.tex | 280 |
1 files changed, 280 insertions, 0 deletions
diff --git a/lab2/report/tmp/algo.tex b/lab2/report/tmp/algo.tex new file mode 100644 index 0000000..fb8b5d8 --- /dev/null +++ b/lab2/report/tmp/algo.tex @@ -0,0 +1,280 @@ +\subsection{Построение эквивалентного замыкания} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Матрица бинарного отношения $A' = (a'_{ij})$ с построенным на +нем эквивалентным замыканием. + +\begin{enumerate} + \item + Построить рефлексивное замыкание на бинарном отношении с матрицей $A = + (a_{ij})$ с помощью соответствующего алгоритма, описанного в лабораторной + работе №1. Полученную матрицу бинарного отношения обозначить как $A_1 = + (a_{ij})$. + \item + Построить симметричное замыкание на бинарном отношении с матрицей $A_1 = + (a_{ij})$ с помощью соответствующего алгоритма, описанного в лабораторной + работе №1. Полученную матрицу бинарного отношения обозначить как $A_2 = + (a_{ij})$. + \item + Построить транзитивное замыкание на бинарном отношении с матрицей $A_2 = + (a_{ij})$ с помощью соответствующего алгоритма, описанного в лабораторной + работе №1. Полученную матрицу бинарного отношения обозначить как $A' = + (a'_{ij})$. + \item + Согласно пункту 4 леммы 1 о замыканиях бинарных отношений, построенное + замыкание на данном бинарном отношении, определяемым матрицей, является + эквивалентным. Далее вернуть полученную матрицу $A' = (a'_{ij})$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^4)$. + + +\subsection{Построение системы представителей фактор-множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Система представителей $T$ фактор-множества $A/\varepsilon$ +бинарного отношения $\varepsilon$ на множестве $A$. + +\begin{enumerate} + \item + Получить фактор-множество $A/\varepsilon$ бинарного отношения $\varepsilon$ + для множества $A$. Для этого нужно получить классы эквивалентности + $\varepsilon(a)$, которые являются срезами по элементам множества $A$. + Срезом по каждому элементу $a \in A$ является совокупность таких элементов + множества $A$, значения которых в строке матрицы, определяющей связи между + элементом $a$ и другими элементами множества $A$, равны единице. Для этого + проверим элементы $a_{ij}$ матрицы $A$, и если $a_{ij} = 1$, где $0 \leq i, + j \leq n - 1$, то добавить значение $j$ в список, определяющий срез по + элементу $i$. В результате полученная совокупность всех таких срезов, + являющихся классами эквивалентности $\{[a]: a \in A\}$, будет определять + фактор-множество $A/\varepsilon$ бинарного отношения $A$. + \item + Отсортировать фактор-множество по возрастанию количества элементов в классах + эквивалентности. + \item + Проходясь по каждому элементу $a$ каждого класса эквивалентности $[a]$ + проверять: если элемент $a$ класса эквивалентности не находится в системе + представителей - добавить элемент в систему представителей как представителя + класса эквивалентности $[a]$, иначе - пропустить элемент. + \item + Вернуть полученную систему представителей. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление минимального элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Список минимальных элементов $L$ упорядоченного множества $(A, +\leq)$. + +\begin{enumerate} + \item + Определяем пустой список $L$. + \item + Пройти по элементам $a_{ij}$ матрицы $A$ (где $0 \leq i, j \leq n - 1$), и + для каждой строки определять переменную $f$, которая будет изначально равна + \textbf{True}. Если $a_{ji} \neq 0$ и $i \neq j$, то переменная $f$ + становится равной \textbf{False} (это означает, что $i$-ый элемент множества + не является минимальным). Если после прохождения по значениям $i$-ой строки + матрицы значение $f$ осталось равным \textbf{True}, то $i$-ый элемент + множества является минимальным, и его надо добавить в список $L$. + \item + Вернуть список минимальных элементов $L$ упорядоченного множества $(A, + \leq)$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление максимального элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times n$. + +\textit{Выход}: Список максимальных элементов $L$ упорядоченного множества $(A, \leq)$. + +\begin{enumerate} + \item + Определяем пустой список $L$. + \item + Пройти по элементам $a_{ij}$ матрицы $A$ (где $0 \leq i, j \leq n - 1$), и + для каждой строки определять переменную $f$, которая будет изначально равна + \textbf{True}. Если $a_{ij} \neq 0$ и $i \neq j$, то переменная $f$ + становится равной \textbf{False} (это означает, что $i$-ый элемент множества + не является максимальным). Если после прохождения по значениям $i$-ой строки + матрицы значение $f$ осталось равным \textbf{True}, то $i$-ый элемент + множества является максимальным, и его надо добавить в список $L$. + \item + Вернуть список максимальных элементов $L$ упорядоченного множества $(A, + \leq)$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление наименьшего элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times +n$. + +\textit{Выход}: Наименьший элемент $a_{min}$ упорядоченного множества $(A, +\leq)$ или <<Ничего>>. + +\begin{enumerate} + \item + Получить список $L$ минимальных элементов упорядоченного множества $(A, + \leq)$ с помощью алгоритма 3.3. + \item + Руководствуясь \textbf{Леммой 2}, если длина $L$ не равна $1$, вернуть + <<Ничего>>, иначе - вернуть единственный элемент $a_{min} = l \in L$, + являющийся наименьшим элементом множества $A$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Вычисление наибольшего элемента множества} + +\textit{Вход}: Матрица бинарного отношения $A = (a_{ij})$ размерности $n \times n$. + +\textit{Выход}: Наибольший элемент $a_{max}$ упорядоченного множества $(A, \leq)$ или ''Ничего''. + +\begin{enumerate} + \item + Получить список $L$ максимальных элементов упорядоченного множества $(A, + \leq)$ с помощью алгоритма 3.4. + \item + Руководствуясь \textbf{Леммой 2}, если длина $L$ не равна $1$, вернуть + ''Ничего'', иначе - вернуть единственный элемент $a_{max} = l \in L$, + являющийся наибольшим элементом множества $A$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2)$. + + +\subsection{Построение диаграммы Хассе} + +\textit{Вход}: Матрица бинарного отношения порядка $A = (a_{ij})$ размерности $n +\times n$. + +\textit{Выход}: Список $H$ длиной $n$, характеризующий диаграмму Хассе: каждый +элемент в списке представляет собой три значения: элемент $a \in A$, значение +его уровня $l$ на диаграмме, список $V$ элементов множества $A$, находящихся на +уровне $l + 1$ и связанных с элементом $a$. + +\begin{enumerate} + \item + Учитывая, что матрице $A = (a_{ij})$ соответствует множество $\overline{A}$ + определяется список $L$, в котором будут храниться значения уровня $l$ для + каждого элемента $a \in \overline{A}$. Изначально присвоить всем элементам + $l \in L$ уровень $1$. Также определить счетчик уровней $p = 0$ и сдвиг по + элементам множества как $b = 0$. + \item + Получить список $L_{min}$ минимальных элементов множества $\overline{A}$ с + помощью алгоритма 3.3, отправив ему на вход матрицу бинарного отношения + порядка $A = (a_{ij})$ (при этом не учитывая первые $b$ элементов + множества). Увеличить значение $p$ на $1$. + \item + Если список $L_{min}$ пуст, перейти к шагу $5$. Иначе перейти к шагу $4$. + \item + Для каждого элемента $a$ в $L_{min}$ соответствующее ему значение списка $l + \in L$ сделать равным $p$. Прибавить к сдвигу $b$ значение, равное + количеству элементов списка $L_{min}$. После этого перейти к шагу $2$. + \item + Определить пустой список $V$. Проходясь по элементам списка $L$, где $0 \leq + k \leq n - 1$, определять для каждого значения $l_k$ пустой список $v_k$ + связанных с элементом $g_k$ элементов множества $G$. Определяя такой список, + далее брать срез $S$ по атрибутам для конкретного объекта $g_k$ (это + осуществляется следующим образом: необходимо предварительно транспонировать + матрицу $B = A^T = (a_{ij})^T = b_{ij}$, затем проверить элементы $b_{ij}$ + матрицы $B$, и если $b_{ij} = 1$, то добавить значение атрибута $m_j$ в + список, определяющий срез по объекту $g_i$. В результате получить список + срезов $S_G = \{s_i = [g]: g \in G\}$, откуда необходимо взять срез для + объекта $g_k$), и затем пройтись по каждому элементу $s_p$ в этом срезе: + если уровень $l \in L$ очередного элемента в срезе равен $l_p + 1$, то + добавить элемент $s_p$ в список $v_k$. После этого отсортировать список + $v_k$ и добавить его в $V$. + \item + Создать список $H$ и поместить в него в качестве элемента $h_i \in H$ тройку + значений: $a_i \in A$, $l_i \in L$, $v_i \in V$, где $0 \leq i \leq n - 1$. + После этого вернуть список $H$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^3 + n^2) = O(n^3)$. + + +\subsection{Построение системы замыканий} + +\textit{Вход}: Контекст $K = (G, M, \rho)$ с множеством объектов $G$, множеством +атрибутов $M$ и отношением $\rho \subset G \times M$, заданного матрицей $A = +(a_{ij})$ размерности $n \times k$ (где $n$ - количество объектов, $k$ - +количество атрибутов). + +\textit{Выход}: Система замыканий $Z_{f_G}$ на множестве $G$. + +\begin{enumerate} + \item + Определить список $Z_{f_G}$ и положить туда $G$. + \item + Получить срезы по атрибутам $m \in M$ с помощью способа, описанного в + алгоритме 3.2: необходимо предварительно транспонировать матрицу $B = A^T = + (a_{ij})^T = b_{ij}$, затем проверить элементы $b_{ij}$ матрицы $B$, и если + $b_{ij} = 1$, где $0 \leq i \leq k - 1$ и $0 \leq j \leq n - 1$, то добавить + значение объекта $g_j$ в список, определяющий срез по атрибуту $m_i$. В + результате получить список срезов $S_G = \{s_i = [g]: g \in G\}$, размер + которого будет $k$. + \item + Для каждого атрибута $m_i \in M$: определить список $T$, в который поместить + $s_i \in S_G$. Далее для каждого замыкания $z_j$ из системы замыканий + $Z_{f_G}$: получить пересечение множеств $s_i$ и $z_j$ и обозначить его как + $X = s_i \cap z_j$. Если $X$ не содержится в списке $T$: добавить $X$ в + список $T$ (всё это осуществляется при $0 \leq i \leq k - 1$). Если $T + \notin Z_{f_G}$, то положить $T$ в $Z_{f_G}$. + \item + Вернуть систему замыканий $Z_{f_G}$ на множестве $G$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2 + n \cdot k)$. + + +\subsection{Построение решетки концептов} + +\textit{Вход}: Контекст $K = (G, M, \rho)$ с множеством объектов $G$, множеством +атрибутов $M$ и отношением $\rho \subset G \times M$, заданного матрицей $A = +(a_{ij})$ размерности $n \times k$ (где $n$ - количество объектов, $k$ - +количество атрибутов). + +\textit{Выход}: Решетка концептов $(C(K), \leq)$. + +\begin{enumerate} + \item + Построить систему замыканий $Z_{f_G}$ с помощью алгоритма 3.8, отправив ему на + вход контекст $K = (G, M, \rho)$. + \item + Определить пустой список $(C(K), \leq)$. + \item + Построить список $P$ следующим образом: если $z_i = \emptyset$, то $P = M$, + иначе - получить среды по объектам $G$ с помощью способа, описанного в + алгоритме 3.2: проверить элементы $a_{rt}$ матрицы $A$, и если $a_{rt} = 1$, + где $0 \leq t \leq k - 1$ и $0 \leq r \leq n - 1$, то добавить значение + $m_t$ в список, определяющий срез по объекту $g_r$. В результате получить + список срезов $S_M = \{s_i = [m]: m \in M\}$, размер которого будет $n$. + Определить пустой список $Y$. Далее для каждого объекта в замыкании $z_i$: + добавить срез $s_i$, соответствующий конкретному объекту, в список $Y$. + После этого осуществить пересечение всех срезов $s$, находящихся в списке + $Y$, и поместить результат пересечения в список $P$. После построения $P$ + добавить пару значений $z_i$ и $P$ в качестве элемента в список $(C(K), + \leq)$. + \item + Проделать шаг 3 для всех элементов $Z_{f_G}$. После этого вернуть + построенную решетку концептов $(C(K), \leq)$. +\end{enumerate} + +Трудоёмкость алгоритма "--- $O(n^2 + n \cdot k + n^3) = O(n \cdot k + n^3)$.
\ No newline at end of file |