Добавил первую лабораторную работу

1 files changed, 459 insertions, 0 deletions

diff --git a/lab1/report/lab1.tex b/lab1/report/lab1.tex
new file mode 100644
index 0000000..75180e4
--- /dev/null
+++ b/lab1/report/lab1.tex
@@ -0,0 +1,459 @@
+\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) M(\rho)^T$ (значения элементов вне главной диагонали
+        матрицы $M(\rho) M(\rho)^T$ равны нулю);
+    \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{Основные системы замыкания на множестве бинарных отношений}
+
+\textit{Замыканием} отношения $R$ относительно свойства $P$ называется такое
+множество $R^*$, что:
+\begin{enumerate}
+    \item $R \subset R^*$.
+    \item $R^*$ обладает свойством $P$.
+    \item 
+        $R^*$ является подмножеством любого другого отношения, содержащего $R$ и
+        обладающего свойством $P$.
+\end{enumerate}
+
+Множество Z подмножеств множества A называется \textit{системой замыканий}, если
+оно замкнуто относительно пересечений, т.е. выполняется
+\begin{equation*}
+    (\forall B \subset Z) ~ \bigcap B \in Z
+\end{equation*}
+
+\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)$ бинарного отношения $\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)$ бинарного отношения $\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)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} <<Отношение является симметричным>> или <<Отношение не
+является симметричным>>.
+
+\begin{enumerate}
+    \item Вычислить транспонированную матрицу $M^T$;
+    \item Если $M = M^T$, то ответ <<Отношение является симметричным>>;
+    \item Иначе ответ <<Отношение не является симметричным>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%%%
+\subsection{Проверка бинарного отношения на антисимметричность}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} <<Отношение является антисимметричным>> или <<Отношение не
+является антисимметричным>>.
+
+\begin{enumerate}
+    \item Вычислить транспонированную матрицу $M^T$;
+    \item Вычислить матрицу $A = M \times M^T$;
+    \item 
+        Если $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) : i
+        \ne j$ выполняется $(A_{ij} = 0)$, то ответ <<Отношение
+        является антисимметричным>>;
+    \item Иначе ответ <<Отношение не является антисимметричным>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%%%
+\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^2)$.
+
+%%%
+\subsection{Классификация отношения как квазипорядка}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} <<Отношение является квазипорядком>> или <<Отношение не является
+квазипорядком>>.
+
+\begin{enumerate}
+    \item Выяснить является ли отношение рефлексивным;
+    \item Выяснить является ли отношение транзитивным;
+    \item 
+        Если на шагах 1 и 2 получены положительные ответы, то ответ <<Отношение
+        является квазипорядком>>;
+    \item Иначе ответ <<Отношение не является квазипорядком>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%%%
+\subsection{Классификация отношения как эквивалентности}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} <<Отношение является эквивалентностью>> или <<Отношение не
+является эквивалентностью>>.
+
+\begin{enumerate}
+    \item Выяснить является ли отношение рефлексивным;
+    \item Выяснить является ли отношение симметричным;
+    \item Выяснить является ли отношение транзитивным;
+    \item 
+        Если на шагах 1, 2 и 3 получены положительные ответы, то ответ
+        <<Отношение является эквивалентностью>>;
+    \item Иначе ответ <<Отношение не является эквивалентностью>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%%%
+\subsection{Классификация отношения как частичного порядка}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} <<Отношение является частичным порядком>> или <<Отношение не
+является частичным порядком>>.
+
+\begin{enumerate}
+    \item Выяснить является ли отношение антисимметричным;
+    \item Выяснить является ли отношение транзитивным;
+    \item 
+        Если на шагах 1 и 2 получены положительные ответы, то ответ
+        <<Отношение является частичным порядком>>;
+    \item Иначе ответ <<Отношение не является частичным порядком>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%%%
+\subsection{Классификация отношения как строгого порядка}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} <<Отношение является строгим порядком>> или <<Отношение не
+является строгим порядком>>.
+
+\begin{enumerate}
+    \item Выяснить является ли отношение антирефлексивным;
+    \item Выяснить является ли отношение антисимметричным;
+    \item Выяснить является ли отношение транзитивным;
+    \item 
+        Если на шагах 1, 2 и 3 получены положительные ответы, то ответ
+        <<Отношение является строгим порядком>>;
+    \item Иначе ответ <<Отношение не является строгим порядком>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+\section{Алгоритмы построения основных замыканий бинарных отношений}
+
+%%%
+\subsection{Алгоритм построения рефлексивного замыкания}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} Матрица $M'(M(\rho))$ рефлексивного замыкания.
+
+\begin{enumerate}
+    \item 
+        $(\forall i = \overline{1, N}) ~ (\forall j = \overline{1, N}) ~ 
+        M'_{ij} = \begin{cases}
+            1, &i = j \\
+            M_{ij}, &i \ne j
+        \end{cases}$
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%%%
+\subsection{Алгоритм построения симметричного замыкания}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} Матрица $M'(M(\rho))$ симметричного замыкания.
+
+\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)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} Матрица $M'(M(\rho))$ транзитивного замыкания.
+
+\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$ раз.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^4)$.
+
+%%%
+\subsection{Алгоритм построения эквивалентного замыкания}
+
+\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+$N \times N$.
+
+\textit{Выход.} Матрица $M'(M(\rho))$ эквивалентного замыкания.
+
+\begin{enumerate}
+    \item 
+        Вычислим матрицу $M_1 = \texttt{refl}(M)$, где \texttt{refl} ---
+        алгоритм построения рефлексивного замыкания;
+    \item
+        Вычислим матрицу $M_2 = \texttt{symm}(M)$, где \texttt{symm} ---
+        алгоритм построения симметричного замыкания;
+    \item
+        Вычислим матрицу $M' = \texttt{trans}(M)$, где \texttt{trans} ---
+        алгоритм построения транзитивного замыкания;
+\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{}
+\end{figure}
+
+\begin{figure}[H]
+    \centering
+    \includegraphics[width=0.7\textwidth]{mat4.png}
+    \caption{}
+\end{figure}
+
+\begin{figure}[H]
+    \centering
+    \includegraphics[width=0.9\textwidth]{mat4_id.png}
+    \caption{}
+\end{figure}
+
+\conclusion
+
+В ходе выполнения данной лабораторной работы были изучены основные свойства
+бинарных отношений, а также операций замыкания бинарных отношений. Были
+разработаны алгоритмы классификации бинарных отношений, а также были произведена
+оценка сложности вычисления данных алгоритмов. Также были разработаны алгоритмы
+построения замыканий бинарных отношений на основе алгоритмов их классификации.
+Программная реализация на языке Python с библиотекой numpy успешно прошла
+тестирование.
+
+\end{document}