Что-то похожее на третью лабу

1 files changed, 359 insertions, 0 deletions

diff --git a/lab3/report/lab3.tex b/lab3/report/lab3.tex
new file mode 100644
index 0000000..6faca04
--- /dev/null
+++ b/lab3/report/lab3.tex
@@ -0,0 +1,359 @@
+\documentclass[spec, och, labwork2]{SCWorks}
+\usepackage{preamble}
+
+\begin{document}
+\include{titlepage.tex}
+\tableofcontents
+
+\section{Постановка задачи}
+
+Цель работы "--- изучение основных понятий универсальной алгебры и операций над
+бинарными отношениями. Порядок выполнения работы:
+\begin{enumerate}
+    \item 
+        Рассмотреть понятие алгебраической операции и классификацию свойств
+        операций. Разработать алгоритмы проверки свойств операций:
+        ассоциативность, коммутативность, идемпотентность, обратимость,
+        дистрибутивность;
+    \item
+        Рассмотреть основные операции над бинарными отношениями. Разработать
+        алгоритмы выполнения операций над бинарными отношениями;
+    \item
+        Рассмотреть основные операции над матрицами. Разработать алгоритмы
+        выполнения операций над матрицами.
+\end{enumerate}
+
+\section{Теоретические сведения}
+
+\subsection{Алгебраические операции}
+
+\begin{definition}
+    Отображение $f : A^n \to A$ называется алгебраической $n$-арной операцией
+    или просто алгебраической операцией на множестве $A$. При этом $n$
+    называется порядком или арностью алгебраической операции $f$.
+\end{definition}
+
+Далее для бинарной операции $f$ по возможности будем использовать
+мультипликативную запись с помощью символа $\cdot$, т.е. вместо $f(x, y)$ писать
+$x \cdot y$, или просто $xy$. При необходимости для бинарной операции $f$
+используется также аддитивная запись с помощью символа $+$, т.е. вместо $f(x,
+y)$ записывается $x + y$.
+
+\begin{definition}
+    Бинарная операция $\cdot$ на множестве A называется
+    \begin{itemize}
+        \item 
+            ассоциативной, если $\forall x, y, z \in A$ выполняется равенство
+            \[ x \cdot (y \cdot z) = (x \cdot y) \cdot z \]
+        \item
+            коммутативной, если $\forall x, y \in A$ выполняется равенство
+            \[ x \cdot y = y \cdot x \]
+        \item
+            идемпотентной, если $\forall x \in A$ выполняется равенство
+            \[ x \cdot x = x \]
+        \item
+            обратимой, если 
+            \[ (\forall a \in A) \; \exists b \in A : a \cdot b = b \cdot a = e \]
+            где $e \in A$ и выполняется $a \cdot e = e \cdot a = a$
+        \item
+            дистрибутивной относительно бинарной операции $+$, если 
+            $\forall x, y, z \in A$ выполняются равенства
+            \begin{align*}
+                x \cdot (y + z) &= (x \cdot y) + (x \cdot z) \\
+                (y + z) \cdot x &= (y \cdot x) + (z \cdot x)
+            \end{align*}
+    \end{itemize}
+\end{definition}
+
+\subsection{Основные операции над бинарными отношениями}
+
+\begin{enumerate}
+    \item Теоретико-множественные операции;
+    \item 
+        Обращение бинарных отношений: обратным для бинарного отношения $\rho
+        \subset A \times B$ называется бинарное отношение $\rho^{-1} \subset B
+        \times A$, определяющееся по формуле:
+        \[ \rho^{-1} = \{ (b, a): (a, b) \in \rho \} \]
+    \item
+        Композиция композицией бинарных отношений $\rho \subset A \times B$ и
+        $\sigma \subset B \times C$ называется бинарное отношение $\rho \sigma$,
+        определяющееся по формуле:
+        \[ \rho \sigma = \{ (a, c): (a, b) \in \rho \land (b, c) \in \sigma \} \]
+\end{enumerate}
+
+\subsection{Основные операции над матрицами}
+
+\begin{enumerate}
+    \item Сложение матриц
+    \item Умножение матрицы на скаляр
+    \item Транспонирование матрицы
+    \item Умножение матриц
+\end{enumerate}
+
+\section{Алгоритмы проверки свойств операций}
+
+%
+\subsection{Проверка на ассоциативность}
+
+\textit{Вход.} Таблица Кэли $M = (m_{ij})$ размерности $N \times N$
+для операции $\cdot$ на множестве $A$.
+
+\textit{Выход.} <<Операция является ассоциативной>> или <<Операция не является
+ассоциативной>>.
+
+\begin{enumerate}
+    \item
+        Если $(\forall 0 \leq i, j, k < N)$ выполняется равенство $m_{pk} =
+        m_{jq}$, где $p$ "--- индекс $m_{ji}$, а $q$ "--- индекс $m_{ik}$, то
+        ответ "--- <<Операция является ассоциативной>>;
+    \item
+        Иначе, ответ "--- <<Операция не является ассоциативной>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^3)$.
+
+%
+\subsection{Проверка на коммутативность}
+
+\textit{Вход.} Таблица Кэли $M = (m_{ij})$ размерности $N \times N$
+для операции $\cdot$ на множестве $A$.
+
+\textit{Выход.} <<Операция является коммутативной>> или <<Операция не является
+коммутативной>>.
+
+\begin{enumerate}
+    \item 
+        Если $(\forall 0 \leq i, j < N) \; m_{ij} = m_{ji}$, то ответ "---
+        <<Операция является коммутативной>>;
+    \item Иначе, ответ "--- <<Операция не является коммутативной>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Проверка на идемпотентность}
+
+\textit{Вход.} Таблица Кэли $M = (m_{ij})$ размерности $N \times N$
+для операции $\cdot$ на множестве $A$.
+
+\textit{Выход.} <<Операция является идемпотентной>> или <<Операция не является
+идемпотентной>>.
+
+\begin{enumerate}
+    \item 
+        Если $(\forall 0 \leq i < N) \; m_{ii} = a$, где $a$ "--- $i$-й элемент
+        множества $A$, то ответ "--- <<Операция является идемпотентной>>;
+    \item Иначе, ответ "--- <<Операция не является идемпотентной>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N)$.
+
+%
+\subsection{Проверка на обратимость}
+
+\textit{Вход.} Таблица Кэли $M = (m_{ij})$ размерности $N \times N$
+для операции $\cdot$ на множестве $A$.
+
+\textit{Выход.} <<Операция является обратимой>> или <<Операция не является
+обратимой>>.
+
+\begin{enumerate}
+    \item 
+        Если $(\forall 0 \leq i, j < N) \; m_{ij} = m_{ji}$, то ответ "---
+        <<Операция является обратимой>>;
+    \item Иначе, ответ "--- <<Операция не является обратимой>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Проверка на дистрибутивность}
+
+\textit{Вход.} Таблица Кэли $M^\cdot = (m^\cdot_{ij})$ размерности $N \times N$
+для операции $\cdot$ на множестве $A$, таблица Кэли $M^+ = (m^+_{ij})$
+размерности $N \times N$ для операции $+$ на множестве $A$
+
+\textit{Выход.} <<Операция является дистрибутивной>> или <<Операция не является
+дистрибутивной>>.
+
+% \begin{align*}
+%     x \cdot (y + z) &= (x \cdot y) + (x \cdot z) \\
+%     (y + z) \cdot x &= (y \cdot x) + (z \cdot x)
+% \end{align*}
+
+% i - x, j - y, k - z
+
+\begin{enumerate}
+    \item
+        Если $(\forall 0 \leq i, j, k < N)$ выполняются равенства $m^\cdot_{it}
+        = m^+_{pq}$ и $m^\cdot_{ti} = m^+_{rs}$, где $t$ "--- индекс $m^+_{jk}$,
+        $p$ "--- индекс $m^\cdot_{ij}$, $q$ "--- индекс $m^\cdot_{ik}$, $r$ "---
+        индекс $m^\cdot_{ji}$, $s$ "--- индекс $m^\cdot_{ki}$, то ответ "---
+        <<Операция является дистрибутивной>>;
+    \item Иначе, ответ "--- <<Операция не является дистрибутивной>>.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^3)$.
+
+\section{Алгоритмы выполнения операций над бинарными отношениями}
+
+%
+\subsection{Вычисление объединения бинарных отношений}
+
+\textit{Вход.} Матрица $A(\rho) = (a_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$, матрица $B(\sigma) = (b_{ij})$ бинарного отношения
+$\sigma$ размерности $N \times N$.
+
+\textit{Выход.} Матрица $C(\rho \cup \sigma) = (c_{ij})$ бинарного отношения
+$\rho \cup \sigma$.
+
+\begin{enumerate}
+    \item $(\forall 0 \leq i, j < N - 1) \; c_{ij} = a_{ij} + b_{ij}$.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Вычисление пересечения бинарных отношений}
+
+\textit{Вход.} Матрица $A(\rho) = (a_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$, матрица $B(\sigma) = (b_{ij})$ бинарного отношения
+$\sigma$ размерности $N \times N$.
+
+\textit{Выход.} Матрица $C(\rho \cap \sigma) = (c_{ij})$ бинарного отношения
+$\rho \cap \sigma$.
+
+\begin{enumerate}
+    \item $(\forall 0 \leq i, j < N - 1) \; c_{ij} = a_{ij} \cdot b_{ij}$.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Вычисление дополнения бинарного отношения}
+
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
+
+\textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ дополнения бинарного отношения
+$\rho$.
+
+\begin{enumerate}
+    \item $(\forall 0 \leq i, j < N - 1) \; m'_{ij} = 1 - m_{ij}$.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Вычисление обратного бинарного отношения}
+
+\textit{Вход.} Матрица $M(\rho) = (m_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$.
+
+\textit{Выход.} Матрица $M'(M(\rho)) = (m'_{ij})$ бинарного отношения
+$\rho^{-1}$.
+
+\begin{enumerate}
+    \item Ответом является матрица транспонированная матрица $M^T = M'$.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Вычисление композиции бинарных отношений}
+
+\textit{Вход.} Матрица $A(\rho) = (a_{ij})$ бинарного отношения $\rho$
+размерности $N \times N$, матрица $B(\sigma) = (b_{ij})$ бинарного отношения
+$\sigma$ размерности $N \times N$.
+
+\textit{Выход.} Матрица $C(\rho\sigma) = (c_{ij})$ бинарного отношения
+$\rho\sigma$.
+
+\begin{enumerate}
+    \item Ответом является матрица $C = A \cdot B$, вычисленная с помощью
+    алгоритма 5.4 Умножения матриц.
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^3)$.
+
+\section{Алгоритмы выполнения операций над матрицами}
+
+%
+\subsection{Сложение матриц}
+
+\textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times M$, матрица
+$B = (b_{ij})$ размерности $N \times M$.
+
+\textit{Выход.} Матрица $C = (c_{ij})$ размерности $N \times M$.
+
+\begin{enumerate}
+    \item 
+        $(\forall 0 \leq i < N) (\forall 0 \leq j < M) \;
+        c_{ij} = a_{ij} + b_{ij}$
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Умножение матрицы на скаляр}
+
+\textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times M$, скаляр $\alpha$.
+
+\textit{Выход.} Матрица $A' = (a'_{ij})$ размерности $N \times M$.
+
+\begin{enumerate}
+    \item 
+        $(\forall 0 \leq i < N) (\forall 0 \leq j < M) \;
+        a'_{ij} = \alpha \cdot a_{ij}$
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Транспонирование матрицы}
+
+\textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times M$.
+
+\textit{Выход.} Матрица $A^T = (a^T_{ij})$ размерности $M \times N$.
+
+\begin{enumerate}
+    \item $(\forall 0 \leq i < N) (\forall 0 \leq j < M) \; a^T_{ji} = a_{ij}$
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^2)$.
+
+%
+\subsection{Умножение матриц}
+
+\textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times M$, матрица $B =
+(b_{ij})$ размерности $M \times K$.
+
+\textit{Выход.} Матрица $C = (c_{ij}) = A \cdot B$ размерности $N \times K$.
+
+\begin{enumerate}
+    \item 
+        $ \displaystyle
+        (\forall 0 \leq i < N) (\forall 0 \leq j < M) \;
+        c_{ij} = \sum_{k = 0}^{K - 1} a_{ik} + \sum_{k = 0}^{K - 1} b_{kj}$
+\end{enumerate}
+
+Трудоёмкость алгоритма --- $O(N^3)$.
+
+\section{Программная реализация}
+
+\inputminted[fontsize=\small, breaklines=true, style=bw, linenos]{c}{../lab3.py}
+
+\section{Результаты тестирования}
+
+текст
+
+\conclusion
+
+В ходе выполнения данной лабораторной работы были изучены основные свойства
+алгебраических операций, основные операции над бинарными отношениями, основные
+операции над матрицами. Были разработаны алгоритмы для программной реализации
+данных операций, а также была произведена оценка сложности данных алгоритмов.
+Программная реализация на языке Python с библиотекой numpy успешно прошла
+тестирование.
+
+\end{document}