diff options
Diffstat (limited to 'lab3/report/lab3.tex')
| -rw-r--r-- | lab3/report/lab3.tex | 346 |
1 files changed, 315 insertions, 31 deletions
diff --git a/lab3/report/lab3.tex b/lab3/report/lab3.tex index a06a190..88ad2f2 100644 --- a/lab3/report/lab3.tex +++ b/lab3/report/lab3.tex @@ -65,10 +65,18 @@ y)$ записывается $x + y$. \end{itemize} \end{definition} +\newpage % cringe + \subsection{Основные операции над бинарными отношениями} \begin{enumerate} - \item Теоретико-множественные операции; + \item + Теоретико-множественные операции: + \begin{itemize} + \item объединение $\cup$; + \item пересечение $\cap$; + \item дополнение $\neg$. + \end{itemize} \item Обращение бинарных отношений: обратным для бинарного отношения $\rho \subset A \times B$ называется бинарное отношение $\rho^{-1} \subset B @@ -84,10 +92,42 @@ y)$ записывается $x + y$. \subsection{Основные операции над матрицами} \begin{enumerate} - \item Сложение матриц - \item Умножение матрицы на скаляр - \item Транспонирование матрицы - \item Умножение матриц + \item \textbf{Сумма и разность матриц.} + + Суммой $A + B$ матриц $A = (a_{ij})$ и $B = (b_{ij})$ размерности $N + \times M$ называется матрица $C = (c_{ij})$ размерности $N \times M$, + где $c_{ij} = a_{ij} + b_{ij} \; (\forall 0 \leq i < N) (\forall 0 \leq j < M)$. + + Разностью $A - B$ матриц $A = (a_{ij})$ и $B = (b_{ij})$ размерности $N + \times M$ называется матрица $C = (c_{ij})$ размерности $N \times M$, + где $c_{ij} = a_{ij} - b_{ij} \; (\forall 0 \leq i < N) (\forall 0 \leq j < M)$. + + \item \textbf{Произведение матрицы на скаляр.} + + Произведением матрицы $A = (a_{ij})$ размерности $N \times M$ на скаляр + $\alpha$ называется матрица $C = (c_{ij})$ размерности $N \times M$, где + $c_{ij} = \alpha \cdot a_{ij} \; (\forall 0 \leq i < N) (\forall 0 \leq j < M)$. + + \item \textbf{Транспонирование матрицы.} + + Транспонированной по отношению к матрице $A = (a_{ij})$ размерности $N + \times M$ называется матрица $A^T = (a^T_{ij})$ размерности $M \times N$ + где $a^T_{ij} = a_{ji} \; (\forall 0 \leq i < N) (\forall 0 \leq j < M)$. + + \item \textbf{Произведение матриц.} + + Произведением матрицы $A = (a_{ij})$ размерности $N \times M$ на матрицу + $B = (b_{ij})$ размерности $M \times K$ называется матрица $C = + (c_{ij})$ размерности $N \times K$, где $\displaystyle c_{ij} = + \sum_{k = 0}^{K - 1} a_{ik} + \sum_{k = 0}^{K - 1} b_{kj} \; + (\forall 0 \leq i < N) (\forall 0 \leq j < M)$ + + \item \textbf{Обращение матрицы.} + + Обратная матрица $A^{-1}$ "--- это такая матрица, при умножении которой + на исходную матрицу $A$ получается единичная матрица $E$. То есть: + \[AA^{-1} = A^{-1}A = E\] + \end{enumerate} \section{Алгоритмы проверки свойств операций} @@ -159,7 +199,7 @@ y)$ записывается $x + y$. \begin{enumerate} \item - Если $(\forall 0 \leq i, j < N) \; m_{ij} = m_{ji}$, то ответ "--- + Если $(\forall 0 \leq i, j < N) \; m_{ij} = m_{ji} = 1$, то ответ "--- <<Операция является обратимой>>; \item Иначе, ответ "--- <<Операция не является обратимой>>. \end{enumerate} @@ -169,9 +209,9 @@ y)$ записывается $x + y$. % \subsection{Проверка на дистрибутивность} -\textit{Вход.} Таблица Кэли $M^\cdot = (m^\cdot_{ij})$ размерности $N \times N$ -для операции $\cdot$ на множестве $A$, таблица Кэли $M^+ = (m^+_{ij})$ -размерности $N \times N$ для операции $+$ на множестве $A$ +\textit{Вход.} Таблица Кэли $A = (a_{ij})$ размерности $N \times N$ +для операции $\cdot$ на множестве $S$, таблица Кэли $B = (b_{ij})$ +размерности $N \times N$ для операции $+$ на множестве $S$ \textit{Выход.} <<Операция является дистрибутивной>> или <<Операция не является дистрибутивной>>. @@ -185,10 +225,10 @@ y)$ записывается $x + y$. \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}$, то ответ "--- + Если $(\forall 0 \leq i, j, k < N)$ выполняются равенства $a_{it} + = b_{pq}$ и $a_{ti} = b_{rs}$, где $t$ "--- индекс $b_{jk}$, + $p$ "--- индекс $a_{ij}$, $q$ "--- индекс $a_{ik}$, $r$ "--- + индекс $a_{ji}$, $s$ "--- индекс $a_{ki}$, то ответ "--- <<Операция является дистрибутивной>>; \item Иначе, ответ "--- <<Операция не является дистрибутивной>>. \end{enumerate} @@ -208,7 +248,7 @@ $\sigma$ размерности $N \times N$. $\rho \cup \sigma$. \begin{enumerate} - \item $(\forall 0 \leq i, j < N - 1) \; c_{ij} = a_{ij} + b_{ij}$. + \item $(\forall 0 \leq i, j < N - 1) \; c_{ij} = a_{ij} \lor b_{ij}$. \end{enumerate} Трудоёмкость алгоритма --- $O(N^2)$. @@ -224,7 +264,7 @@ $\sigma$ размерности $N \times N$. $\rho \cap \sigma$. \begin{enumerate} - \item $(\forall 0 \leq i, j < N - 1) \; c_{ij} = a_{ij} \cdot b_{ij}$. + \item $(\forall 0 \leq i, j < N - 1) \; c_{ij} = a_{ij} \land b_{ij}$. \end{enumerate} Трудоёмкость алгоритма --- $O(N^2)$. @@ -271,7 +311,7 @@ $\rho\sigma$. \begin{enumerate} \item Ответом является матрица $C = A \cdot B$, вычисленная с помощью - алгоритма 5.4 Умножения матриц. + алгоритма 5.4 Произведения матриц. \end{enumerate} Трудоёмкость алгоритма --- $O(N^3)$. @@ -279,7 +319,7 @@ $\rho\sigma$. \section{Алгоритмы выполнения операций над матрицами} % -\subsection{Сложение матриц} +\subsection{Сумма и разность матриц} \textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times M$, матрица $B = (b_{ij})$ размерности $N \times M$. @@ -289,13 +329,13 @@ $B = (b_{ij})$ размерности $N \times M$. \begin{enumerate} \item $(\forall 0 \leq i < N) (\forall 0 \leq j < M) \; - c_{ij} = a_{ij} + b_{ij}$ + c_{ij} = a_{ij} + b_{ij}$ (либо $c_{ij} = a_{ij} - b_{ij}$) \end{enumerate} -Трудоёмкость алгоритма --- $O(N^2)$. +Трудоёмкость алгоритма --- $O(N \cdot M)$. % -\subsection{Умножение матрицы на скаляр} +\subsection{Произведение матрицы на скаляр} \textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times M$, скаляр $\alpha$. @@ -307,7 +347,7 @@ $B = (b_{ij})$ размерности $N \times M$. a'_{ij} = \alpha \cdot a_{ij}$ \end{enumerate} -Трудоёмкость алгоритма --- $O(N^2)$. +Трудоёмкость алгоритма --- $O(N \cdot M)$. % \subsection{Транспонирование матрицы} @@ -320,10 +360,10 @@ $B = (b_{ij})$ размерности $N \times M$. \item $(\forall 0 \leq i < N) (\forall 0 \leq j < M) \; a^T_{ji} = a_{ij}$ \end{enumerate} -Трудоёмкость алгоритма --- $O(N^2)$. +Трудоёмкость алгоритма --- $O(N \cdot M)$. % -\subsection{Умножение матриц} +\subsection{Произведение матриц} \textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times M$, матрица $B = (b_{ij})$ размерности $M \times K$. @@ -337,6 +377,28 @@ $B = (b_{ij})$ размерности $N \times M$. c_{ij} = \sum_{k = 0}^{K - 1} a_{ik} + \sum_{k = 0}^{K - 1} b_{kj}$ \end{enumerate} +Трудоёмкость алгоритма --- $O(N \cdot M \cdot K)$. + +% +\subsection{Обращение матрицы} + +\textit{Вход.} Матрица $A = (a_{ij})$ размерности $N \times N$. + +\textit{Выход.} Матрица $A^{-1} = (a'_{ij})$ размерности $N \times N$. + +\begin{enumerate} + \item Находим определитель матрицы $|A|$; + \item + Находим матрицу $A^T$, вычисленная с помощью алгоритма 5.3 + Транспонирования матриц; + \item + Вычисляем элементы союзной матрицы $A^*$ как алгебраические дополнения + матрицы $A^T$; + \item + Ответом является матрица $A^{-1} = |A|^{-1} \cdot A^*$, вычисленная с + помощью алгоритма 5.2 Произведения матрицы на скаляр. +\end{enumerate} + Трудоёмкость алгоритма --- $O(N^3)$. \section{Программная реализация} @@ -354,7 +416,7 @@ $B = (b_{ij})$ размерности $N \times M$. \begin{figure}[H] \centering \includegraphics[width=0.8\textwidth]{test2.png} - \caption{Проверка свойства транзитивности для двух операций} + \caption{Проверка свойства дистрибутивности для двух операций} \end{figure} \begin{figure}[H] @@ -366,7 +428,7 @@ $B = (b_{ij})$ размерности $N \times M$. \begin{figure}[H] \centering \includegraphics[width=0.8\textwidth]{test4.png} - \caption{Проверка операции умножения двух матриц} + \caption{Проверка операции произведения двух матриц} \end{figure} \begin{figure}[H] @@ -375,12 +437,234 @@ $B = (b_{ij})$ размерности $N \times M$. \caption{Проверка операции транспонирования матрицы} \end{figure} -\begin{figure}[H] - \centering - \includegraphics[width=0.8\textwidth]{test6.png} - \caption{Ответы на задачи (Вариант 6)} -\end{figure} - +\section{Решение задач} + +\subsection*{Задание 1} + +Необходимо исследовать на ассоциативность бинарную операцию, заданную следующей +таблицей Кэли: +\begin{equation*} + \begin{bmatrix} + . & a & b & c & d \\ + a & a & b & a & b \\ + b & a & b & a & b \\ + c & a & b & c & d \\ + d & a & b & c & d \\ + \end{bmatrix} +\end{equation*} + +\input{task1.tex} + +Можно заметить, что условие ассоциативности $(\forall 0 \leq i, j, k < N)$ +выполнено, поэтому можно сделать вывод, что бинарная операция, заданная +данной таблицей Кэли обладает свойство ассоциативности. + +\subsection*{Задание 2} + +Необходимо вычислить значение выражения +\begin{equation*} + A^2 + \left( 10 - \frac{\lambda}{2} \right) \cdot A + \frac{\lambda}{2} \cdot E, \, + \text{где } A = \begin{pmatrix} + 1 & -2 \\ + -3 & \lambda + \end{pmatrix}, \, \lambda = 6 +\end{equation*} + +Вычислим значение $A^2 = (m_{ij})$: +\begin{align*} + m_{11} &= 1 \cdot 1 + (-2) \cdot (-3) = 7 \\ + m_{12} &= 1 \cdot (-2) + (-2) \cdot \lambda = -14 \\ + m_{21} &= (-3) \cdot 1 + 6 \cdot (-3) = -21 \\ + m_{22} &= (-3) \cdot -2 + \lambda \cdot \lambda = 42 +\end{align*} + +Получаем $A^2 = \begin{pmatrix} + 7 & -14 \\ + -21 & 42 +\end{pmatrix}$ + +$\displaystyle\left( 10 - \frac{\lambda}{2} \right) += \displaystyle\left( 10 - \frac{6}{2} \right) += \displaystyle\left( 10 - 3 \right) = 7$, поэтому +\begin{equation*} + \left( 10 - \frac{\lambda}{2} \right) \cdot A = 7 \cdot \begin{pmatrix} + 1 & -2 \\ + -3 & \lambda + \end{pmatrix} = \begin{pmatrix} + 1 \cdot 7 & -2 \cdot 7 \\ + -3 \cdot 7 & \lambda \cdot 7 + \end{pmatrix} = \begin{pmatrix} + 7 & -14 \\ + -21 & 42 + \end{pmatrix} +\end{equation*} + +Матрица $E$ "--- единичная матрица, поэтому +\begin{equation*} + \frac{\lambda}{2} \cdot E = \begin{pmatrix} + \frac{\lambda}{2} & 0 \\ + 0 & \frac{\lambda}{2} + \end{pmatrix} = \begin{pmatrix} + 3 & 0 \\ + 0 & 3 + \end{pmatrix} +\end{equation*} + +В результате получаем +\begin{align*} + A^2 &+ \left( 10 - \frac{\lambda}{2} \right) \cdot A + \frac{\lambda}{2} \cdot E = \\ + &= \begin{pmatrix} + 7 & -14 \\ + -21 & 42 + \end{pmatrix} + \begin{pmatrix} + 7 & -14 \\ + -21 & 42 + \end{pmatrix} + \begin{pmatrix} + 3 & 0 \\ + 0 & 3 + \end{pmatrix} = \\ + &= \begin{pmatrix} + 7 + 7 + 3 & -14 - 14 + 0 \\ + -21 - 21 + 0 & 42 + 42 + 3 + \end{pmatrix} = \begin{pmatrix} + 17 & -28 \\ + -42 & 87 + \end{pmatrix} +\end{align*} + +\subsection*{Задание 3} + +Необходимо вычислить произведение матриц $A \cdot B$, где +$\lambda = 6$, +\begin{equation*} + A = \begin{pmatrix} + -1 & \lambda & 3 \\ + \frac{\lambda}{3} & 2 & 8 - \frac{\lambda}{3} + \end{pmatrix} = \begin{pmatrix} + -1 & 6 & 3 \\ + 2 & 2 & 6 + \end{pmatrix} +\end{equation*} + +\begin{equation*} + B = \begin{pmatrix} + -\lambda & 2 \\ + 1 & 10 - \frac{\lambda}{2} \\ + -3 & \lambda + \end{pmatrix} = \begin{pmatrix} + -6 & 2 \\ + 1 & 7 \\ + -3 & 6 + \end{pmatrix} +\end{equation*} + +Вычислим произведение $A \cdot B = C = (c_{ij})$: +\begin{align*} + c_{11} &= (-1) \cdot (-6) + 6 \cdot 1 + 3 \cdot (-3) = 6 + 6 - 9 = 3 \\ + c_{12} &= (-1) \cdot 2 + 6 \cdot 7 + 3 \cdot 6 = -2 + 42 + 18 = 58 \\ + c_{21} &= 2 \cdot (-6) + 2 \cdot 1 + 6 \cdot (-3) = -12 + 2 - 18 = -28 \\ + c_{22} &= 2 \cdot 2 + 2 \cdot 7 + 6 \cdot 6 = 4 + 14 + 36 = 54 +\end{align*} + +В результате получаем +\begin{equation*} + A \cdot B = \begin{pmatrix} + 3 & 58 \\ + -28 & 54 + \end{pmatrix} +\end{equation*} + +\subsection*{Задание 4} + +Необходимо решить матричное уравнение $2 \cdot X + 6 \cdot A = B$, где +$\lambda = 6$, +\begin{equation*} + A = \begin{pmatrix} + -1 & \lambda & 3 \\ + -\lambda & 4 & -1 \\ + \frac{\lambda}{3} & 2 & 8 - \frac{\lambda}{3} + \end{pmatrix} = \begin{pmatrix} + -1 & 6 & 3 \\ + -6 & 4 & -1 \\ + 2 & 2 & 6 + \end{pmatrix} +\end{equation*} + +\begin{equation*} + B = \begin{pmatrix} + -\lambda & -3 & 2 \\ + 1 & \lambda + 1 & 10 - \frac{\lambda}{2} \\ + -3 & 5 & \lambda + \end{pmatrix} = \begin{pmatrix} + -6 & -3 & 2 \\ + 1 & 7 & 7 \\ + -3 & 5 & 6 + \end{pmatrix} +\end{equation*} + +Преобразуем исходное уравнение: +\begin{align*} + 2 \cdot X + 6 \cdot A &= B \\ + 2 \cdot X &= B - 6 \cdot A \\ + X &= 0.5 \cdot B - 3 \cdot A +\end{align*} + +Вычислим слагаемые в правой части: +\begin{align*} + 0.5 \cdot B &= 0.5 \cdot \begin{pmatrix} + -6 & -3 & 2 \\ + 1 & 7 & 7 \\ + -3 & 5 & 6 + \end{pmatrix} = \\ + &= \begin{pmatrix} + -6 \cdot 0.5 & -3 \cdot 0.5 & 2 \cdot 0.5 \\ + 1 \cdot 0.5 & 7 \cdot 0.5 & 7 \cdot 0.5 \\ + -3 \cdot 0.5 & 5 \cdot 0.5 & 6 \cdot 0.5 + \end{pmatrix} = \begin{pmatrix} + -3 & -1.5 & 1 \\ + 0.5 & 3.5 & 3.5 \\ + -1.5 & 2.5 & 3 + \end{pmatrix} +\end{align*} + +\begin{align*} + 3 \cdot A &= 3 \cdot \begin{pmatrix} + -1 & 6 & 3 \\ + -6 & 4 & -1 \\ + 2 & 2 & 6 + \end{pmatrix} = \\ + &= \begin{pmatrix} + -1 \cdot 3 & 6 \cdot 3 & 3 \cdot 3 \\ + -6 \cdot 3 & 4 \cdot 3 & -1 \cdot 3 \\ + 2 \cdot 3 & 2 \cdot 3 & 6 \cdot 3 + \end{pmatrix} = \begin{pmatrix} + -3 & 18 & 9 \\ + -18 & 12 & -3 \\ + 6 & 6 & 18 + \end{pmatrix} +\end{align*} + +В результате получаем: +\begin{align*} + X &= 0.5 \cdot B - 3 \cdot A = \begin{pmatrix} + -3 & -1.5 & 1 \\ + 0.5 & 3.5 & 3.5 \\ + -1.5 & 2.5 & 3 + \end{pmatrix} + \begin{pmatrix} + -3 & 18 & 9 \\ + -18 & 12 & -3 \\ + 6 & 6 & 18 + \end{pmatrix} = \\ + &= \begin{pmatrix} + -3 - 3 & -1.5 + 18 & 1 + 9 \\ + 0.5 - 18 & 3.5 + 12 & 3.5 - 3 \\ + -1.5 + 6 & 2.5 + 6 & 3 + 18 + \end{pmatrix} = \begin{pmatrix} + -6 & 16.5 & 10 \\ + -17.5 & 15.5 & 0.5 \\ + 4.5 & 8.5 & 21 + \end{pmatrix} +\end{align*} \conclusion |