Исправил асимптотику проверки отношения на симметричность и вызовы алгоритмов

1 files changed, 32 insertions, 28 deletions

diff --git a/lab1/report/lab1.tex b/lab1/report/lab1.tex
index b5618ff..aaf4feb 100644
--- a/lab1/report/lab1.tex
+++ b/lab1/report/lab1.tex
@@ -7,8 +7,8 @@
 
 \section{Постановка задачи}
 
-Цель работы --- изучение основных свойств бинарных отношений и операций замыкания бинарных отношений. 
-Порядок выполнения работы:
+Цель работы --- изучение основных свойств бинарных отношений и операций
+замыкания бинарных отношений. Порядок выполнения работы:
 \begin{enumerate}
     \item 
         Разобрать основные определения видов бинарных отношений и разработать
@@ -73,10 +73,10 @@ $A_1, \dots, A_n$.
         отношение $\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$ --- операция
-        поэлементного умножения матриц;
+        Это означает, что бинарное отношение $\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
@@ -118,8 +118,8 @@ $A_1, \dots, A_n$.
 \end{definition}
 
 \begin{definition}
-    Множество Z подмножеств множества A называется \textit{системой замыканий}, если
-    оно замкнуто относительно пересечений, т.е. выполняется
+    Множество Z подмножеств множества A называется \textit{системой замыканий},
+    если оно замкнуто относительно пересечений, т.е. выполняется
     \begin{equation*}
         (\forall B \subset Z) ~ \bigcap B \in Z
     \end{equation*}        
@@ -172,8 +172,8 @@ $A_1, \dots, A_n$.
 %%%
 \subsection{Проверка бинарного отношения на рефлексивность}
 
-\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$ размерности
-$N \times N$.
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
 
 \textit{Выход.} <<Отношение является рефлексивным>> или <<Отношение не является 
 рефлексивным>>.
@@ -222,8 +222,9 @@ $N \times N$.
     \item Иначе ответ <<Отношение не является симметричным>>.
 \end{enumerate}
 
-Транспонирование матрицы имеет трудоёмкость $O(N^{3/2} \log N)$. Таким образом,
-трудоёмкость алгоритма --- $O(N^{3/2} \log N)$.
+Транспонирование матрицы имеет трудоёмкость $O(N^{3/2} \log N)$, а сравнение
+двух матриц имеет трудоёмкость $O(N^2)$. Таким образом, трудоёмкость алгоритма
+--- $O(N^2) = O(N^2) + O(N^{3/2} \log N)$.
 
 %%%
 \subsection{Проверка бинарного отношения на антисимметричность}
@@ -264,8 +265,8 @@ $N \times N$.
 \end{enumerate}
 
 Перемножение матриц в худшем случае имеет трудоёмкость $O(N^3)$, а сравнение
-матриц --- $O(N^2)$. Таким образом, трудоёмкость алгоритма --- $O(N^3) = O(N^3)
-+ O(N^2)$.
+матриц имеет трудоёмкость $O(N^2)$. Таким образом, трудоёмкость алгоритма ---
+$O(N^3) = O(N^3) + O(N^2)$.
 
 %%%
 \subsection{Классификация отношения как квазипорядка}
@@ -277,8 +278,8 @@ $N \times N$.
 квазипорядком>>.
 
 \begin{enumerate}
-    \item Выяснить является ли отношение рефлексивным;
-    \item Выяснить является ли отношение транзитивным;
+    \item Присвоить булевой переменной \texttt{refl} значение алгоритма 3.1;
+    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
     \item 
         Если на шагах 1 и 2 получены положительные ответы, то ответ <<Отношение
         является квазипорядком>>;
@@ -297,11 +298,12 @@ $N \times N$.
 является эквивалентностью>>.
 
 \begin{enumerate}
-    \item Выяснить является ли отношение рефлексивным;
-    \item Выяснить является ли отношение симметричным;
-    \item Выяснить является ли отношение транзитивным;
+    \item Присвоить булевой переменной \texttt{refl} значение алгоритма 3.1;
+    \item Присвоить булевой переменной \texttt{symm} значение алгоритма 3.3;
+    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
     \item 
-        Если на шагах 1, 2 и 3 получены положительные ответы, то ответ
+        Если значение булевого выражения $\texttt{refl} \, \land \,
+        \texttt{symm} \, \land \, \texttt{tran}$ --- истина, то ответ
         <<Отношение является эквивалентностью>>;
     \item Иначе ответ <<Отношение не является эквивалентностью>>.
 \end{enumerate}
@@ -318,11 +320,12 @@ $N \times N$.
 является частичным порядком>>.
 
 \begin{enumerate}
-    \item Выяснить является ли отношение антисимметричным;
-    \item Выяснить является ли отношение транзитивным;
+    \item Присвоить булевой переменной \texttt{antisymm} значение алгоритма 3.4;
+    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
     \item 
-        Если на шагах 1 и 2 получены положительные ответы, то ответ
-        <<Отношение является частичным порядком>>;
+        Если значение булевого выражения $\texttt{antisymm} \, \land \,
+        \texttt{tran}$ --- истина, то ответ <<Отношение является частичным
+        порядком>>;
     \item Иначе ответ <<Отношение не является частичным порядком>>.
 \end{enumerate}
 
@@ -338,11 +341,12 @@ $N \times N$.
 является строгим порядком>>.
 
 \begin{enumerate}
-    \item Выяснить является ли отношение антирефлексивным;
-    \item Выяснить является ли отношение антисимметричным;
-    \item Выяснить является ли отношение транзитивным;
+    \item Присвоить булевой переменной \texttt{antirefl} значение алгоритма 3.2;
+    \item Присвоить булевой переменной \texttt{antisymm} значение алгоритма 3.4;
+    \item Присвоить булевой переменной \texttt{tran} значение алгоритма 3.5;
     \item 
-        Если на шагах 1, 2 и 3 получены положительные ответы, то ответ
+        Если значение булевого выражения $\texttt{antirefl} \, \land \,
+        \texttt{antisymm} \, \land \, \texttt{tran}$ --- истина, то ответ
         <<Отношение является строгим порядком>>;
     \item Иначе ответ <<Отношение не является строгим порядком>>.
 \end{enumerate}