path: root/lab2/report/tmp/algo.tex

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