From 4304a5e64108140c7890ee034a957f7eb8208054 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Fri, 1 Apr 2022 19:33:34 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=B8=D0=BB=20=D0=BF?=
 =?UTF-8?q?=D0=BE=D0=B4=D1=80=D0=BE=D0=B1=D0=BD=D0=BE=D0=B5=20=D1=80=D0=B5?=
 =?UTF-8?q?=D1=88=D0=B5=D0=BD=D0=B8=D0=B5=20=D0=B7=D0=B0=D0=B4=D0=B0=D0=BD?=
 =?UTF-8?q?=D0=B8=D0=B9=20=D0=B8=D0=B7=20=D1=82=D1=80=D0=B5=D1=82=D1=8C?=
 =?UTF-8?q?=D0=B5=D0=B9=20=D0=BB=D0=B0=D0=B1=D1=8B?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab3/report/lab3.tex | 346 ++++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 315 insertions(+), 31 deletions(-)

(limited to 'lab3/report/lab3.tex')

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
 
-- 
cgit v1.2.3

