path: root/lab1/report/lab1.tex

\documentclass[spec, och, labwork2]{SCWorks}
\usepackage{preamble}

\begin{document}
\include{titlepage.tex}
\tableofcontents

\section{Постановка задачи}

Цель работы --- изучение основных свойств бинарных отношений и операций
замыкания бинарных отношений. Порядок выполнения работы:
\begin{enumerate}
    \item 
        Разобрать основные определения видов бинарных отношений и разработать
        алгоритмы классификации бинарных отношений;
    \item
        Изучить свойства бинарных отношений и рассмотреть основные системы
        замыкания на множестве бинарных отношений;
    \item Разработать алгоритмы построения основных замыканий бинарных отношений.
\end{enumerate}

\section{Теоретические сведения}

\subsection{Основные определения видов бинарных отношений}

Подмножества декартова произведения $A_1 \times \dots \times A_n$ множеств
$A_1, \dots, A_n$ называются $n$-ыми отношениями между элементами множеств
$A_1, \dots, A_n$.

Подмножества декартова произведения $A \times B$ множеств $A$ и $B$ называются
бинарными отношениями между элементами множеств $A$ и $B$.

Для бинарного отношения $\rho \subset A \times B$ область определения $D_\rho$ и
множество значений $E_\rho$ определяется как подмножества соответствующих
множеств $A$ и $B$ по следующим формулам:
\begin{align*}
    D_\rho &= \left\{ a: (a, b) \in \rho \text{ для некоторого } b \in B \right\} \\
    E_\rho &= \left\{ b: (a, b) \in \rho \text{ для некоторого } a \in A \right\}
\end{align*}

Бинарное отношение $\rho \subset A \times A$ называется:
\begin{enumerate}
    \item \textit{рефлексивным}, если $(\forall a \in A) ~ (a, a) \in \rho$;
    \item 
        \textit{антирефлексивным}, если 
        $(\forall a \in A) ~ (a, a) \not\in \rho$;
    \item 
        \textit{симметричным}, если 
        $(\forall a, b \in A) ~ (a, b) \in \rho \implies (b,a) \in \rho$;
    \item 
        \textit{антисимметричным}, если 
        $(\forall a, b \in A) ~ (a, b) \in \rho \land (b, a) \in \rho \implies a = b$;
    \item 
        \textit{транзитивным}, если 
        $(\forall a, b, c \in A) ~ (a, b) \in \rho \land (b, c) \in \rho \implies (a, c) \in \rho$.
\end{enumerate}

Символом $\Delta_A$ обозначается тождественное отношение на множестве $A$,
которое определяется по формуле: $\Delta_A = \{ (a, a) | a \in A \}$.

Тогда бинарное отношение $\rho \subset A \times A$ является:
\begin{itemize}
    \item 
        \textit{рефлексивным} $\iff$ $\Delta_A \subset \rho$. Это означает, что
        бинарное отношение $\rho$ рефлексивно, если $M(\rho) \geq E$, где $E$
        --- единичная матрица. Если же матрица $M(\rho)$ несравнима с единичной
        матрицей, то бинарное отношение $\rho$ не является рефлексивным;
    \item 
        \textit{симметричным} $\iff$ $\rho^{-1} \subset \rho$. Это означает, что
        бинарное отношение $\rho$ симметрично, если $M(\rho) \geq M(\rho)^T$,
        где $M(\rho)^T$ – транспонированная матрица бинарного отношения $\rho$.
        Если же матрица $M(\rho)$ несравнима с $M(\rho)^T$, то бинарное
        отношение $\rho$ не является симметричным;
    \item 
        \textit{антисимметричным} $\iff$ $\rho \cap \rho^{-1} \subset \Delta_A$.
        Это означает, что бинарное отношение $\rho$ антисимметрично, если 
        $E \geq M(\rho) \otimes M(\rho)^T$ (значения элементов вне главной
        диагонали матрицы $M(\rho) \otimes M(\rho)^T$ равны нулю), где $\otimes$
        --- операция поэлементного умножения матриц;
    \item 
        \textit{транзитивным} $\iff$ $\rho \rho \subset \rho$. Это означает, что
        бинарное отношение $\rho$ транзитивно, если $M(\rho)M(\rho) \leq
        M(\rho)$.
\end{itemize}

Классификация бинарных отношений:
\begin{enumerate}
    \item 
        Рефлексивное и транзитивное отношение называется отношением
        \textit{квазипорядка}.
    \item
        Рефлексивное, симметричное и транзитивное отношение называется
        отношением \textit{эквивалентности}.
    \item
        Рефлексивное, антисимметричное и транзитивное отношение называется
        отношением \textit{частичного порядка}.
    \item
        Антирефлексивное, антисимметричное и транзитивное отношение называется
        отношением \textit{строгого порядка}.
\end{enumerate}

\subsection{Основные системы замыкания на множестве бинарных отношений}

\begin{definition}
    Оператором замыкания на множестве A называется отображение $f$ множества
    всех подмножеств $P(A)$ в себя, удовлетворяющее условиям:
    \begin{enumerate}
        \item $X \subset Y \implies f(X) \subset f(Y)$;
        \item $X \subset f(X)$;
        \item $ff(X) = f(X)$.
    \end{enumerate}
    $\forall X, Y \in P(A)$.
\end{definition}

\begin{definition}
    Для подмножества $X \in A$ значение $f(X)$ называется замыканием
    подмножества $X$.
\end{definition}

\begin{definition}
    Множество Z подмножеств множества A называется \textit{системой замыканий},
    если оно замкнуто относительно пересечений, т.е. выполняется
    \begin{equation*}
        (\forall B \subset Z) ~ \bigcap B \in Z
    \end{equation*}        
\end{definition}

\begin{lemma}[О системах замыканий бинарных отношений]
    На множестве $P(A^2)$ всех бинарных отношений между элементами множества $A$
    следующие множества являются системами замыканий:
    \begin{enumerate}
        \item
            $Z_r$ - множество всех рефлексивных бинарных отношений между
            элементами множества $A$;
        \item
            $Z_s$ – множество всех симметричных бинарных отношений между
            элементами множества $A$;
        \item
            $Z_t$ – множество всех транзитивных бинарных отношений между
            элементами множества $A$;
        \item
            $Z_{eq} = Eq(A)$ – множество всех отношений эквивалентности на
            множестве $A$.
    \end{enumerate}

    Множество $Z_{as}$ всех антисимметричных бинарных отношений между элементами
    множества $A$ не является системой замыкания.
\end{lemma}

\begin{lemma}
    На множестве $P(A^2)$ всех бинарных отношений между элементами множества A
    следующие отображения являются операторами замыканий:
    \begin{enumerate}
        \item 
            $f_r(\rho) = \delta \cup \Delta_A$ --- наименьшее рефлексивное
            бинарное отношение, содержащее отношение $\rho \subset A^2$;
        \item
            $f_s(\rho) = \delta \cup \delta^{-1}$ --- наименьшее симметричное
            бинарное отношение, содержащее отношение $\rho \subset A^2$;
        \item 
            $f_t(\rho) = \bigcup_{n = 1}^\infty \rho^n$ наименьшее транзитивное
            бинарное отношение, содержащее отношение $\rho \subset A^2$;
        \item 
            $f_{eq} = f_t f_s f_r (\rho)$ наименьшее отношение эквивалентности,
            содержащее отношение $\rho \subset A^2$;
    \end{enumerate}

\end{lemma}

\section{Алгоритмы классификации бинарных отношений}

%%%
\subsection{Проверка бинарного отношения на рефлексивность}

\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
размерности $N \times N$.

\textit{Выход.} <<Отношение является рефлексивным>> или <<Отношение не является 
рефлексивным>>.

\begin{enumerate}
    \item Взять диагональ матрицы $d(M) = \{ m_{ii} | i = \overline{1, N} \}$;
    \item 
        Если $\exists a = 0 \in d(M)$, то ответ <<Отношение не является
        рефлексивным>>;
    \item Иначе ответ <<Отношение является рефлексивным>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N)$.

%%%
\subsection{Проверка бинарного отношения на антирефлексивность}

\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
размерности $N \times N$.

\textit{Выход.} <<Отношение является антирефлексивным>> или <<Отношение не
является антирефлексивным>>.

\begin{enumerate}
    \item Взять диагональ матрицы $d(M) = \{ m_{ii} | i = \overline{1, N} \}$;
    \item 
        Если $\exists a = 1 \in d(M)$, то ответ <<Отношение не является
        антирефлексивным>>;
    \item Иначе ответ <<Отношение является антирефлексивным>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N)$.

%%%
\subsection{Проверка бинарного отношения на симметричность}

\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
размерности $N \times N$.

\textit{Выход.} <<Отношение является симметричным>> или <<Отношение не
является симметричным>>.

\begin{enumerate}
    \item Вычислить транспонированную матрицу $M^T$;
    \item Если $M = M^T$, то ответ <<Отношение является симметричным>>;
    \item Иначе ответ <<Отношение не является симметричным>>.
\end{enumerate}

Транспонирование матрицы имеет трудоёмкость $O(N^{3/2} \log N)$, а сравнение
двух матриц имеет трудоёмкость $O(N^2)$. Таким образом, трудоёмкость алгоритма
--- $O(N^2) = O(N^2) + O(N^{3/2} \log N)$.

%%%
\subsection{Проверка бинарного отношения на антисимметричность}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является антисимметричным>> или <<Отношение не
является антисимметричным>>.

\begin{enumerate}
    \item Вычислить транспонированную матрицу $M^T$;
    \item Вычислить матрицу $(a_{ij}) = A = M \otimes M^T$;
    \item 
        Если $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) : i
        \ne j$ выполняется $(a_{ij} = 0)$, то ответ <<Отношение
        является антисимметричным>>;
    \item Иначе ответ <<Отношение не является антисимметричным>>.
\end{enumerate}

Транспонирование матрицы имеет трудоёмкость $O(N^{3/2} \log N)$, а поэлементное
умножение матриц --- $O(N^2)$. Таким образом, трудоёмкость алгоритма --- $O(N^2)
= O(N^2) + O(N^2) + O(N^{3/2} \log N)$.

%%%
\subsection{Проверка бинарного отношения на транзитивность}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является транзитивным>> или <<Отношение не является
транзитивным>>.

\begin{enumerate}
    \item Вычислить матрицу $A = M \times M$;
    \item Если $A \leq M$, то ответ <<Отношение является транзитивным>>;
    \item Иначе ответ <<Отношение не является транзитивным>>.
\end{enumerate}

Перемножение матриц в худшем случае имеет трудоёмкость $O(N^3)$, а сравнение
матриц имеет трудоёмкость $O(N^2)$. Таким образом, трудоёмкость алгоритма ---
$O(N^3) = O(N^3) + O(N^2)$.

%%%
\subsection{Классификация отношения как квазипорядка}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является квазипорядком>> или <<Отношение не является
квазипорядком>>.

\begin{enumerate}
    \item Присвоить булевой переменной \texttt{refl} значение алгоритма 3.1;
    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
    \item 
        Если на шагах 1 и 2 получены положительные ответы, то ответ <<Отношение
        является квазипорядком>>;
    \item Иначе ответ <<Отношение не является квазипорядком>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^3)$.

%%%
\subsection{Классификация отношения как эквивалентности}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является эквивалентностью>> или <<Отношение не
является эквивалентностью>>.

\begin{enumerate}
    \item Присвоить булевой переменной \texttt{refl} значение алгоритма 3.1;
    \item Присвоить булевой переменной \texttt{symm} значение алгоритма 3.3;
    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
    \item 
        Если значение булевого выражения $\texttt{refl} \, \land \,
        \texttt{symm} \, \land \, \texttt{tran}$ --- истина, то ответ
        <<Отношение является эквивалентностью>>;
    \item Иначе ответ <<Отношение не является эквивалентностью>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^3)$.

%%%
\subsection{Классификация отношения как частичного порядка}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является частичным порядком>> или <<Отношение не
является частичным порядком>>.

\begin{enumerate}
    \item Присвоить булевой переменной \texttt{antisymm} значение алгоритма 3.4;
    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
    \item 
        Если значение булевого выражения $\texttt{antisymm} \, \land \,
        \texttt{tran}$ --- истина, то ответ <<Отношение является частичным
        порядком>>;
    \item Иначе ответ <<Отношение не является частичным порядком>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^3)$.

%%%
\subsection{Классификация отношения как строгого порядка}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} <<Отношение является строгим порядком>> или <<Отношение не
является строгим порядком>>.

\begin{enumerate}
    \item Присвоить булевой переменной \texttt{antirefl} значение алгоритма 3.2;
    \item Присвоить булевой переменной \texttt{antisymm} значение алгоритма 3.4;
    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
    \item 
        Если значение булевого выражения $\texttt{antirefl} \, \land \,
        \texttt{antisymm} \, \land \, \texttt{tran}$ --- истина, то ответ
        <<Отношение является строгим порядком>>;
    \item Иначе ответ <<Отношение не является строгим порядком>>.
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^3)$.

\section{Алгоритмы построения основных замыканий бинарных отношений}

%%%
\subsection{Алгоритм построения рефлексивного замыкания}

\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
размерности $N \times N$.

\textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ рефлексивного замыкания.

\begin{enumerate}
    \item Пусть $M' = M$
    \item Установим $(\forall i = \overline{1, N}) ~ m'_{ii} = 1$
\end{enumerate}

Трудоёмкость алгоритма --- $O(N)$.

%%%
\subsection{Алгоритм построения симметричного замыкания}

\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
размерности $N \times N$.

\textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ симметричного замыкания.

\begin{enumerate}
    \item 
        $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ 
        m'_{ij} = \begin{cases}
            1, &m_{ij} = 1 \lor m_{ji} = 1\\
            0, &m_{ij} = 0 \land m_{ji} = 0
        \end{cases}$
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^2)$.

%%%
\subsection{Алгоритм построения транзитивного замыкания}

\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
размерности $N \times N$.

\textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ транзитивного замыкания.

\begin{enumerate}
    \item 
        $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ 
        (\forall k = \overline{1, N}) ~
        m'_{ij} = \begin{cases}
            1, &m_{ik} = 1 \land m_{kj} = 1\\
            0, &\text{в иных случаях}
        \end{cases}$;
    \item Шаг 1 необходимо повторить $N$ раз (по пункту 3 Леммы 2).
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^4)$.

%%%
\subsection{Алгоритм построения эквивалентного замыкания}

\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
$N \times N$.

\textit{Выход.} Матрица $M'(M(\rho))$ эквивалентного замыкания.

\begin{enumerate}
    \item 
        Вычислим матрицу $M_1$ применив к матрице $M$ алгоритм 4.1;
    \item
        Вычислим матрицу $M_2$ применив к матрице $M_1$ алгоритм 4.2;
    \item
        Вычислим матрицу $M'$ применив к матрице $M_2$ алгоритм 4.3;
\end{enumerate}

Трудоёмкость алгоритма --- $O(N^4)$.

\section{Программная реализация}

\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../lab1.py}

\section{Результаты тестирования}

Ниже представлены результаты запуска программы на некоторых бинарных отношениях.

\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{mat3.png}
    \caption{Ввод матрицы размерности $3 \times 3$}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{mat4.png}
    \caption{Ввод матрицы размерности $4 \times 4$}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.9\textwidth]{mat4_id.png}
    \caption{Ввод единичной матрицы размерности $4 \times 4$}
\end{figure}

\conclusion

В ходе выполнения данной лабораторной работы были изучены основные свойства
бинарных отношений, а также операций замыкания бинарных отношений. Были
разработаны алгоритмы классификации бинарных отношений, а также были произведена
оценка сложности вычисления данных алгоритмов. Также были разработаны алгоритмы
построения замыканий бинарных отношений на основе алгоритмов их классификации.
Программная реализация на языке Python с библиотекой numpy успешно прошла
тестирование.

\end{document}