\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)$.