Внёс исправления в первую лабораторную

3 files changed, 75 insertions, 69 deletions

diff --git a/lab1/lab1.py b/lab1/lab1.py
index bc4bd00..176ade6 100644
--- a/lab1/lab1.py
+++ b/lab1/lab1.py
@@ -30,7 +30,7 @@ def check_symmetry(relation: BinaryRelation):
 
 def check_antisymmetry(relation: BinaryRelation):
     relation.antisymmetric = True
-    multiplied = relation.matrix @ relation.matrix.T
+    multiplied = np.multiply(relation.matrix, relation.matrix.T)
     n = multiplied.shape[0]
     for i in range(n):
         for j in range(n):
diff --git a/lab1/report/lab1.tex b/lab1/report/lab1.tex
index 75180e4..b5618ff 100644
--- a/lab1/report/lab1.tex
+++ b/lab1/report/lab1.tex
@@ -74,14 +74,13 @@ $A_1, \dots, A_n$.
     \item 
         \textit{антисимметричным} $\iff$ $\rho \cap \rho^{-1} \subset \Delta_A$.
         Это означает, что бинарное отношение $\rho$ антисимметрично, если $E
-        \geq M(\rho) M(\rho)^T$ (значения элементов вне главной диагонали
-        матрицы $M(\rho) M(\rho)^T$ равны нулю);
+        \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}
 
 Классификация бинарных отношений:
@@ -93,7 +92,7 @@ $A_1, \dots, A_n$.
         Рефлексивное, симметричное и транзитивное отношение называется
         отношением \textit{эквивалентности}.
     \item
-        Рефлексивное антисимметричное транзитивное отношение называется
+        Рефлексивное, антисимметричное и транзитивное отношение называется
         отношением \textit{частичного порядка}.
     \item
         Антирефлексивное, антисимметричное и транзитивное отношение называется
@@ -102,21 +101,29 @@ $A_1, \dots, A_n$.
 
 \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{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$
@@ -165,14 +172,14 @@ $A_1, \dots, A_n$.
 %%%
 \subsection{Проверка бинарного отношения на рефлексивность}
 
-\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности
 $N \times N$.
 
 \textit{Выход.} <<Отношение является рефлексивным>> или <<Отношение не является 
 рефлексивным>>.
 
 \begin{enumerate}
-    \item Взять диагональ матрицы $d(M) = \{ M_{ii} | i = \overline{1, N} \}$;
+    \item Взять диагональ матрицы $d(M) = \{ m_{ii} | i = \overline{1, N} \}$;
     \item 
         Если $\exists a = 0 \in d(M)$, то ответ <<Отношение не является
         рефлексивным>>;
@@ -184,14 +191,14 @@ $N \times N$.
 %%%
 \subsection{Проверка бинарного отношения на антирефлексивность}
 
-\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
-$N \times N$.
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
 
 \textit{Выход.} <<Отношение является антирефлексивным>> или <<Отношение не
 является антирефлексивным>>.
 
 \begin{enumerate}
-    \item Взять диагональ матрицы $d(M) = \{ M_{ii} | i = \overline{1, N} \}$;
+    \item Взять диагональ матрицы $d(M) = \{ m_{ii} | i = \overline{1, N} \}$;
     \item 
         Если $\exists a = 1 \in d(M)$, то ответ <<Отношение не является
         антирефлексивным>>;
@@ -203,8 +210,8 @@ $N \times N$.
 %%%
 \subsection{Проверка бинарного отношения на симметричность}
 
-\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
-$N \times N$.
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
 
 \textit{Выход.} <<Отношение является симметричным>> или <<Отношение не
 является симметричным>>.
@@ -215,7 +222,8 @@ $N \times N$.
     \item Иначе ответ <<Отношение не является симметричным>>.
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Транспонирование матрицы имеет трудоёмкость $O(N^{3/2} \log N)$. Таким образом,
+трудоёмкость алгоритма --- $O(N^{3/2} \log N)$.
 
 %%%
 \subsection{Проверка бинарного отношения на антисимметричность}
@@ -228,15 +236,17 @@ $N \times N$.
 
 \begin{enumerate}
     \item Вычислить транспонированную матрицу $M^T$;
-    \item Вычислить матрицу $A = M \times 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)$, то ответ <<Отношение
+        \ne j$ выполняется $(a_{ij} = 0)$, то ответ <<Отношение
         является антисимметричным>>;
     \item Иначе ответ <<Отношение не является антисимметричным>>.
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Транспонирование матрицы имеет трудоёмкость $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{Проверка бинарного отношения на транзитивность}
@@ -253,7 +263,9 @@ $N \times N$.
     \item Иначе ответ <<Отношение не является транзитивным>>.
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Перемножение матриц в худшем случае имеет трудоёмкость $O(N^3)$, а сравнение
+матриц --- $O(N^2)$. Таким образом, трудоёмкость алгоритма --- $O(N^3) = O(N^3)
++ O(N^2)$.
 
 %%%
 \subsection{Классификация отношения как квазипорядка}
@@ -273,7 +285,7 @@ $N \times N$.
     \item Иначе ответ <<Отношение не является квазипорядком>>.
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Трудоёмкость алгоритма --- $O(N^3)$.
 
 %%%
 \subsection{Классификация отношения как эквивалентности}
@@ -294,7 +306,7 @@ $N \times N$.
     \item Иначе ответ <<Отношение не является эквивалентностью>>.
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Трудоёмкость алгоритма --- $O(N^3)$.
 
 %%%
 \subsection{Классификация отношения как частичного порядка}
@@ -314,7 +326,7 @@ $N \times N$.
     \item Иначе ответ <<Отношение не является частичным порядком>>.
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Трудоёмкость алгоритма --- $O(N^3)$.
 
 %%%
 \subsection{Классификация отношения как строгого порядка}
@@ -335,43 +347,39 @@ $N \times N$.
     \item Иначе ответ <<Отношение не является строгим порядком>>.
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Трудоёмкость алгоритма --- $O(N^3)$.
 
 \section{Алгоритмы построения основных замыканий бинарных отношений}
 
 %%%
 \subsection{Алгоритм построения рефлексивного замыкания}
 
-\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
-$N \times N$.
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
 
-\textit{Выход.} Матрица $M'(M(\rho))$ рефлексивного замыкания.
+\textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ рефлексивного замыкания.
 
 \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}$
+    \item Пусть $M' = M$
+    \item Установим $(\forall i = \overline{1, N}) ~ m'_{ii} = 1$
 \end{enumerate}
 
-Трудоёмкость алгоритма --- $O(N^2)$.
+Трудоёмкость алгоритма --- $O(N)$.
 
 %%%
 \subsection{Алгоритм построения симметричного замыкания}
 
-\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
-$N \times N$.
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
 
-\textit{Выход.} Матрица $M'(M(\rho))$ симметричного замыкания.
+\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
+        m'_{ij} = \begin{cases}
+            1, &m_{ij} = 1 \lor m_{ji} = 1\\
+            0, &m_{ij} = 0 \land m_{ji} = 0
         \end{cases}$
 \end{enumerate}
 
@@ -380,20 +388,20 @@ $N \times N$.
 %%%
 \subsection{Алгоритм построения транзитивного замыкания}
 
-\textit{Вход.} Матрица $M(\rho)$ бинарного отношения $\rho$ размерности
-$N \times N$.
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
 
-\textit{Выход.} Матрица $M'(M(\rho))$ транзитивного замыкания.
+\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\\
+        m'_{ij} = \begin{cases}
+            1, &m_{ik} = 1 \land m_{kj} = 1\\
             0, &\text{в иных случаях}
         \end{cases}$;
-    \item Шаг 1 необходимо повторить $N$ раз.
+    \item Шаг 1 необходимо повторить $N$ раз (по пункту 3 Леммы 2).
 \end{enumerate}
 
 Трудоёмкость алгоритма --- $O(N^4)$.
@@ -408,14 +416,11 @@ $N \times N$.
 
 \begin{enumerate}
     \item 
-        Вычислим матрицу $M_1 = \texttt{refl}(M)$, где \texttt{refl} ---
-        алгоритм построения рефлексивного замыкания;
+        Вычислим матрицу $M_1$ применив к матрице $M$ алгоритм 4.1;
     \item
-        Вычислим матрицу $M_2 = \texttt{symm}(M)$, где \texttt{symm} ---
-        алгоритм построения симметричного замыкания;
+        Вычислим матрицу $M_2$ применив к матрице $M_1$ алгоритм 4.2;
     \item
-        Вычислим матрицу $M' = \texttt{trans}(M)$, где \texttt{trans} ---
-        алгоритм построения транзитивного замыкания;
+        Вычислим матрицу $M'$ применив к матрице $M_2$ алгоритм 4.3;
 \end{enumerate}
 
 Трудоёмкость алгоритма --- $O(N^4)$.
@@ -431,19 +436,19 @@ $N \times N$.
 \begin{figure}[H]
     \centering
     \includegraphics[width=0.7\textwidth]{mat3.png}
-    \caption{}
+    \caption{Ввод матрицы размерности $3 \times 3$}
 \end{figure}
 
 \begin{figure}[H]
     \centering
     \includegraphics[width=0.7\textwidth]{mat4.png}
-    \caption{}
+    \caption{Ввод матрицы размерности $4 \times 4$}
 \end{figure}
 
 \begin{figure}[H]
     \centering
     \includegraphics[width=0.9\textwidth]{mat4_id.png}
-    \caption{}
+    \caption{Ввод единичной матрицы размерности $4 \times 4$}
 \end{figure}
 
 \conclusion
diff --git a/lab1/report/preamble.sty b/lab1/report/preamble.sty
index 890063f..835aef8 100644
--- a/lab1/report/preamble.sty
+++ b/lab1/report/preamble.sty
@@ -48,4 +48,5 @@
 \newcommand{\eqdef}{\stackrel {\rm def}{=}}
 \renewcommand\theFancyVerbLine{\small\arabic{FancyVerbLine}}
 \newtheorem{lemma}{Лемма}
-\newtheorem*{lemma*}{Лемма}
\ No newline at end of file
+\newtheorem*{lemma*}{Лемма}
+\newtheorem{definition}{Определение}
\ No newline at end of file