From 8e4c33ae45537211cbf50d236461fe6045f9ded1 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Sun, 29 May 2022 12:06:47 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B8?=
 =?UTF-8?q?=D0=B5=20=D0=B2=D1=82=D0=BE=D1=80=D0=BE=D0=B9=20=D0=BB=D0=B0?=
 =?UTF-8?q?=D0=B1=D1=8B=20=D0=B8=20=D1=82=D0=B5=D1=81=D1=82=D0=BE=D0=B2=20?=
 =?UTF-8?q?=D0=BA=20=D0=BE=D1=81=D1=82=D0=B0=D0=BB=D1=8C=D0=BD=D1=8B=D0=BC?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab2/report/tmp/algo.tex | 280 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 280 insertions(+)
 create mode 100644 lab2/report/tmp/algo.tex

(limited to 'lab2/report/tmp/algo.tex')

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
-- 
cgit v1.2.3

