path: root/lab3/report/lab3.tex

\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{Результаты тестирования}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{test1.png}
    \caption{Проверка свойств некоторой бинарной операции}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{test2.png}
    \caption{Проверка свойства транзитивности для двух операций}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{test3.png}
    \caption{Выполнение основных операций над бинарными отношениями}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{test4.png}
    \caption{Проверка операции умножения двух матриц}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{test5.png}
    \caption{Проверка операции транспонирования матрицы}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=0.8\textwidth]{test6.png}
    \caption{Ответы на задачи (Вариант 6)}
\end{figure}


\conclusion

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

\end{document}