\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}